第三章：栈与队列

(一) 栈、队列和线性表有什么区别？

                1. 栈和队列可被看成是两种操作受限制的特性线性表。

                2. 其特色性体现在它们的插入和删除操作都是控制在线性表的一端或两端进行

(二) 栈

   一、 什么是栈？栈又有什么特性？

                1. 栈是特殊的线性表。栈中的数据元素及其元素之间的逻辑关系和线性表相同，逻辑结构和存储结构都相同。

                2. 栈的插入和删除操作只允许在表的尾端进行。其允许进行插入和删除的一端称为栈顶，另一端为栈底。

                3. 栈的插入操作称为入栈(push)，删除操作称为出栈(pop) 。

                4. 栈每次最先进去的元素总是最后一个出来。因此栈顶具有一种后进先出或先进后出的特性。

二、栈都有那些术语操作？

                       栈顶Top：允许进行插入和删除的一端。

                       栈底Bottom

                       入栈push：栈的插入操作。

                       出栈pop：栈的删除操作。

三、 对于四个元素ABCD它们的出栈的序列有多少种呢？

—— 对于四个元素ABCD依次入栈，那么出栈的序列有多少种呢？（进出栈可以交替进行）

// in 代表进，out代表出。例：Ain Aout 表示A进  A出

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

—— 最终结果：14种出栈序列

 四、卡特兰数

              进出栈是最经典的卡特兰数

               公式：

                 详情链接：

「算法入门笔记」卡特兰数 - 知乎

https://zhuanlan.zhihu.com/p/97619085

               解析卡特兰数的计算

------------------------------------------------------------------------------------------

         五、栈的抽象数据类型Java接口 【 IStack】

package data.linear_table.stack_queue;
//栈的抽象数据类型Java接口
public interface IStack {
    public void clear() ;   //置栈空
    public boolean isEmpty() ;  //判断栈是否为空
    public int length() ;   //栈中数据元素的个数
    public Object peek() ;  //取栈顶元素
    public   void push(Object x) throws Exception;  //入栈
    public Object pop() ;   //出栈
}

(三) 顺序栈

       一、什么是顺序栈？

                       使用数组来实现的栈。

                        入栈和出栈只能在栈顶进行。

                        假设数组名为：stackElem 。变量top表示栈顶元素。则top有两种情况：

                                一种是将top设置为指向栈顶元素的下一个元素的位置，则空栈时： top = 0

                               一种是将top设置为指向栈顶元素的位置，则空栈时，top = -1              

         二、那么顺序栈默认采用那种top情况呢？

                         约定：

                               空栈：top == 0

                               满栈：top == stackElem.length

                               长度：top

                               栈顶元素：stackElem[top - 1]

------------------------------------------------------------------------------------------

         三、顺序栈类 【SqStack】

—— 实现栈接口 IStack

package data.linear_table.stack_queue;
//顺序栈类
public class SqStack implements IStack {
    private Object[] stackElem ;    //对象数组
    private int top ;   //在非空栈中，top始终指向栈顶元素的下一个存储位置.栈为空，top = 0 ;
    //栈的构造函数，构造一个存储空间容量为maxSize个单元
    public SqStack (int maxSize) {
        top = 0 ;       //初始化top = 0
        stackElem = new Object[maxSize] ;      // 为栈分配maxSize个存储单元
    }
    @Override
    public void clear() {
        top = 0 ;
    }
    //判断是否为空
    @Override
    public boolean isEmpty() {
        return top == 0 ;
    }
    //求栈中数据元素个数
    @Override
    public int length() {
        return top ;
    }
    //取栈顶元素
    @Override
    public Object peek() {
        if (!isEmpty()) {   //如果栈不为空
            return stackElem[top -1] ;  //返回栈顶元素
        }else {
            return null ;
        }
    }
    //入栈
    @Override
    public void push(Object x) throws Exception {
        // {....}
    }
    //出栈
    @Override
    public Object pop() {
        // {....}
        return null ;
    }
    //输出栈中所有数据元素（从栈顶元素到栈底元素）
    public void display() {
        for (int i = top - 1 ; i >= 0 ; i -- ) {
            //输出
            System.out.print(stackElem[i].toString()+" ");
        }
    }
}

注： 代码中 ” {....}“ 处，会在后面单独进行讲解。

                算法：入栈

                        算法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;
    }
}

算法： 出栈

算法1：

public Object pop() {
    if(top == 0) {
        return null;      //空栈
    } else {
        top--;
        return stackElem[top];
    }
}

算法2：

public boolean isEmpty() {    //是否为空
    return top == 0;
}
public Object pop() {
    if(isEmpty()) {
        return null;      //空栈
    } else {
        return stackElem[--top];
    }
}