栈和队列 学习总结 <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
    }
}

---

栈的应用：

1. 栈是嵌套函数调用机制实现的基础。

   比如在 main 函数中，调用 LinkedStack<T>()，其中又要调用SinglyList<T>()，此时 3个函数均在执行中，仍然都占用系统资源。根据嵌套调用规则，每个函数在执行完后返回调用语句，操作系统就是用 “栈” 结构确定应该返回哪一个函数的：

   执行函数调用的时候......
   | 系统栈图示： |
   | ------ |
   | SinglyList<T>() 当前栈顶 |
   | LinkedStack<T>() |
   | main() 当前栈底 |

2. 使用栈结构 实现括号匹配：

   ​ 假设有以下一个字符串：

   infix = "((1+2)*3+4)"
   

   0	1	2	3	4	5	6	7	8	9	length-1
   (	(	1	+	2	)	*	3	+	4	)

   过程如下：

   1. >> i = 0，'(' no.1入栈;
   2. >> i = 1，'(' no.2入栈;
   3. >> i = 5，当前指向 ')'，所以 '(' no.2 出栈；
   4. >> 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));    
       }
   }
   

---