栈和队列 学习总结 <Java语言版> （一）栈
概述：
栈和队列是两种特殊的线性表，特殊之处在于插入和删除操作的位置受到了限制。
若插入和删除操作只允许在线性表的一端进行，则为栈，其特点是 后进先出；
若插入和删除操作分别在线性表的两端进行，则为队列，特点是 先进先出。
栈
1.1 栈抽象数据类型：
栈（Stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。
允许操作的一端称为 栈顶（Top），不允许操作的一端称为 栈底（Bottom）。栈中插入元素的操作称为 入栈（Push），删除元素的操作称为 出栈（Pop）。没有元素的栈称为 空栈。
栈的特点就像是一摞盘子，每次只能将一只盘子放在最上面；只可以从最上面取出一只盘子而不能从中间插进或抽出。
栈的基本操作有：创建栈，判断栈是否为空、入栈、出栈和取栈顶元素等，栈不支持对指定位置进行插入、删除等操作。声明栈接口 Stack<T> 如下，描述栈抽象数据类型：
public interface Stack<T>{
public abstract
public abstract boolean isEmpty();
public abstract void push(T x); // 元素 x 入栈
public abstract T peek(); // 返回栈顶元素
public abstract T pop(); // 出栈，返回栈顶元素
}
Q：为什么先要实现栈的接口而不是直接ADT定义数据类型呢？ A： 栈分为 顺序栈类 和 链式栈类，分别实现栈接口。
1.2 顺序栈类：
采用顺序存储结构的栈称为 顺序栈（Sequential Stack）。声明顺序栈类 SeqStack<T>如下，实现栈接口，使用顺序表作为成员变量实现栈，约定 null 不能入栈。
// 顺序栈类，最终类，实现栈接口，T 表示数据元素的数据类型;
public final class SeqStack<T>{
// vars:
private SeqList<T> list;
// methods:
public SeqStack(int length){
this.list = new SeqList<T>(length);
}
public SeqStack(){
this(64); // 无参则构件默认大小的空栈;
}
public boolean isEmpty(){
return this.list.isEmpty();
}
public void push(T x){ // 元素 x 入栈。
this.list.insert(x); // 顺序表尾插入元素x，自动扩充容量。
}
public T peek(){
return this.list.get(this.size() -1 ); // 若栈空，get() 返回的是 null.
}
public T pop(){ // 出栈，返回栈顶元素，若栈空则返回 null.
return list.remove(list.size() -1 ); // 若栈不空，删除顺序表尾，返回删除元素。
}
}
其中，入栈和出栈操作实现为顺序表尾插入和尾删除，时间复杂度为 O( 1 )；顺序表的插入方法已经实现了自动扩容数组，当需要扩容时，入栈时间复杂度为 O( n )。
1.3 链式栈类：
采用链式存储结构的栈称为 链式栈，设单链表（不带头结点）的头指针 top 指向第一个元素结点（即栈顶），入栈操作是头插入；出栈操作是头删除；再让 top 指向新的栈顶结点。
public final class LinkedStack<T> implements Stack<T> {
public SinglyList<T> list;
public LinkedStack(){
this.list = new SinglyList<T>();
}
@Override
public boolean isEmpty() {
return this.list.isEmpty(); // 判断栈是否为空
}
@Override
public void push(T x) {
this.list.insert(0, x); // 在表头插入元素，即 入栈
}
@Override
public T peek() {
return this.list.get(0); // 返回表头元素， 即获取 栈顶元素， 若栈空则返回 null
}
@Override
public T pop() {
return this.list.remove(0); // 若栈不空，则单链表头删除，返回删除元素，栈空 则返回 null
}
}
栈的应用：
-
栈是嵌套函数调用机制实现的基础。
比如在 main 函数中，调用 LinkedStack<T>()，其中又要调用SinglyList<T>()，此时 3个函数均在执行中，仍然都占用系统资源。根据嵌套调用规则，每个函数在执行完后返回调用语句，操作系统就是用 “栈” 结构确定应该返回哪一个函数的：
执行函数调用的时候......
| 系统栈图示： |
| ------ |
| SinglyList<T>() 当前栈顶 |
| LinkedStack<T>() |
| main() 当前栈底 | -
使用栈结构 实现括号匹配：
假设有以下一个字符串：
infix = "((1+2)*3+4)"0 1 2 3 4 5 6 7 8 9 length-1 ( ( 1 + 2 ) * 3 + 4 ) 过程如下：
- >> i = 0，'(' no.1入栈;
- >> i = 1，'(' no.2入栈;
- >> i = 5，当前指向 ')'，所以 '(' no.2 出栈；
- >> i = 10，当前指向 ')'，所以 '(' no.1 出栈；字符串infix遍历完毕，栈空，全部匹配。
下面给出 括号匹配的实现：（重点关注栈的应用）
public class Bracket{ // 检查 infix 表达式字符串中的括号是否匹配，若匹配，返回空串，否则返回错误信息。 public static String isMatched(String infix){ Stack<String> stack = new Stack<String>(infix.length()); // 声明接口对象 stack，引用实现Stack<T>接口的顺序栈类的实例，创建空栈。 for(int i =0; i<infix.length(); i++){ char ch = infix.charAt(i); switch(ch){ case '(': stack.push(ch+""); break; case ')': if(stack.isEmpty() || !stack.pop().equals("(")) return "期望\'(\';"; } } return (stack.isEmpty()?"":"期望\')\';"); } // 尝试一种会报错的情况： public static void main(String[] args) { String infix = "((1+2)*3+4)("; System.out.println(infix+"编译错误："+Bracket.isMatched(infix)); } }
