1.概述
比较重要，且应用广泛的两种线性结构：栈 Stack、队列 Queue。
栈和队列 与 线性表不同之处：栈和队列可被看成是两种操作受限的特殊线性表。
2.栈
2.1定义
栈是一个特殊的线性表，插入和删除只允许在栈顶Top(线性表的尾端)进行操作。
术语：
栈顶Top：允许进行插入和删除的一端。
栈底Bottom
入栈push：栈的插入操作。
出栈pop：栈的删除操作。
- 栈特点：后进先出（Last In First Out、LIFO）、先进后出（First In Last Out、FILO）。
2.2出入栈练习(卡特兰数)
- 需求：若将ABCD依次入栈，则出栈的序列是？（进出栈可以交替进行）
// 入栈个数 1/2/3/4 Ain Aout Bin Bout Cin Cout Din Dout --> ABCD Ain Aout Bin Bout Cin Din Dout Cout --> ABDC Ain Aout Bin Cin Cout Din Dout Bout --> ACDB Ain Aout Bin Cin Cout Bout Din Dout --> ACBD Ain Aout Bin Cin Din Dout Cout Bout --> ADCB Ain Bin Bout Aout Cin Cout Din Dout --> BACD Ain Bin Bout Aout Cin Din Dout Cout --> BADC Ain Bin Bout Cin Cout Aout Din Dout --> BCAD Ain Bin Bout Cin Cout Din Dout Aout --> BCDA Ain Bin Bout Cin Din Dout Cout Aout --> BDCA Ain Bin Cin Cout Din Dout Bout Aout --> CDBA Ain Bin Cin Cout Bout Din Dout Aout --> CBDA Ain Bin Cin Cout Bout Aout Din Dout --> CBAD Ain Bin Cin Din Dout Cout Bout Aout --> DCBA
进出栈是最经典的卡特兰数
3.顺序栈
3.1定义
- 顺序栈：使用数组实现的栈。
- 约定：
- 空栈：
top == 0 - 满栈：
top == stackElem.length - 长度：
top - 栈顶元素：
stackElem[top - 1]
3.2栈类
public class SqStack { private Object[] stackElem; //栈对象数组 private int top; //长度、下一个存储位置 等 }
3.3算法：入栈【重点】
- 算法1：
public void push(Object x){ if(top == stackElem.length){ throw new RuntimeException("栈满"); }else{ stackElem[top] = x; top++; } }
算法2：
public void push(Object x){ if(top == stackElem.length){ throw new RuntimeException("栈满"); }else{ stackElem[top++] = x; } }
3.4算法：出栈【重点】
算法1：
public Object pop(){ if(top == 0){ return null; }else{ top--; return statckElem[top]; } }
算法2：
public boolean isEmpty(){ return top == 0; } public Object pop(){ if(isEmpty()){ return null; }else{ return statckElem[--top]; } }
4.链栈
4.1定义
- 使用链式存储的栈，就是链栈。进行插入和删除操作在栈顶进行，也就是链表的尾端。
- 存储单元2部分组成：数据域 data 和指针域 next。
- 使用top栈顶指针用于指向栈尾。
4.2栈类
public class LinkStack { private Node top; //栈顶指针 }
4.3算法：入栈
- 需求：将新结点p，压入到栈顶
public void push(Object x){ Node p = new Node(x); p.next = top; top = p; }
4.4算法：出栈
需求：弹出栈顶元素，需要返回数据
public Object pop(){ if(top == null){ return null; }else{ Node p = top; top = top.next; return p.data; } }
