数据结构学习成果栈、队列学习成果分享：
此博客共分为两个部分：栈与队列
栈
基本概念：栈（stack）是限制插入和删除只能在一个位置上进行的表，即一种操作受限的特殊线性表。
图解：
栈顶：允许进行插入和删除的一端
栈底：固定的不允许进行插入和删除的一端
空栈：不含任何元素的空表
特性：后进栈的元素先出栈，栈又被称为后进先出表（LIFO——Last in , First out）
Java实现：
public class Stackextends Vector { public Stack() { } //将一个元素压进栈中 public E push(E item) { addElement(item); return item; } //将栈顶元素弹出 public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } //返回栈顶元素但不移除该元素 public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); } //判断是否为空栈 public boolean empty() { return size() == 0; } //将给定对象搜索到栈上，并在给定对象存在时返回其位置。 public synchronized int search(Object o) { int i = lastIndexOf(o); if (i >= 0) { return size() - i; } return -1; } @java.io.Serial private static final long serialVersionUID = 1224463164541339165L; }
以上是栈的源码，栈继承了Vector类。
数组实现：
public class Stack{
private int size;//栈的大小
private int top;//栈顶元素的下标
private E[] stackArray;//栈的容器
public Stack(int size){
stackArray = new E[size];
top = -1; //初始化栈的时候由于栈内没有元素，栈顶下标设为-1
this.size = size;
}
//入栈,栈顶的下标+1
public void push(E item){
stackArray[++top] = item;
}
//出栈，删除栈顶元素，栈顶元素的下标-1
public int pop(){
return stackArray[top--];
}
//查看栈顶元素，不删除
public E find(){
return stackArray[top];
}
//判空
public boolean isEmpty(){
return (top == -1);
}
//判满
public boolean isFull(){
return (top == size - 1);
}
}
链表实现：
class Node{
public E data;
public Node next;
public Node(E data){
this.data = data;
}
}
public class Stack2 {
Node head;
public int size;//栈的大小
public int top;//栈顶元素的下标
public static E[] stackArray;//栈的容器
public void push(E data){
if(head == null){
head = new Node(data);
}else{
Node node = new Node(data);
node.next = head;
head = node;
}
}
public void pop(){
if(head == null){
throw new EmptyStackException();
}else{
E dat = head.data;
head = head.next;
}
}
public int top(){
if(head == null){
return 0;
}else{
return head.data;
}
}
public boolean isEmpty(){
if(head == null) return true;
return false;
}
}
应用：
要求：判断一个字符串是否为回文字符串
public boolean isPalindrome01(ListNode head) {
Stack stack = new Stack<>();
ListNode cur = head;
while(cur!=null){
stack.push(cur);
cur = cur.next;
}
while(head!=null){
if(head.val!=stack.pop().val){
return false;
}
head = head.next;
}
return true;
}
分析：利用出栈的顺序与进栈的顺序相反的特性进行首尾比较
队列
基本概念：也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
图解：
队头：允许删除的一端
队尾：允许插入一端
空队列：不含任何元素的空表
特性：先进队列的元素先出队列，队列又被称为先进先出表（FIFO—First in , First out）
Java实现：
public interface Queueextends Collection { //将指定的元素插入入此队列 boolean add(E e); // 将指定的元素插入此队列（有容量限制时优于add方法） boolean offer(E e); //移除并获取队列的头 E remove(); //移除并获取队列的头 E poll(); //获取但不移除队列的头 E element(); //获取但不移除队列的头 E peek(); }
以上为队列(Queue)的源码。
两个堆栈实现：
//两个堆栈实现一个队列
class queue {
Stack stackA = new Stack();
Stack stackB = new Stack();
//入队
public void in(E n) {
stackA.push(n);
}
//出队 我们把A里面的元素遍历拿出放入B中 再拿出B中的第一个元素
public E out() {
//判断b栈有没有元素 有返回false 无返回真
if(stackB.isEmpty()) {
while(!stackA.isEmpty()) {
stackB.push(stackA.pop());
}
}
return stackB.pop();
}
}
应用：
要求：用队列实现栈
class MyStack {
Queue in;
Queue out;
public MyStack() {
in = new LinkedList<>();
out = new LinkedList<>();
}
public void push(int x) {
in.offer(x);
while(!out.isEmpty()){
in.offer(out.poll());
}
Queue temp = in;
in = out;
out = temp;
}
public int pop() {
return out.poll();
}
public int top() {
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}
分析：LinkedList类实现了Queue接口,队列与栈的方法相似。
