栈和队列

栈和队列是操作受到限制的线性表

栈的定义

  • 栈（stack）又称堆栈，它是运算受限的线性表
  • 只能在表的一端进行插入和删除操作， 不容许在其余任何地位进行插入、查找、删除等操作
  • 表中进行插入和删除操作的一端称为栈顶（top），另一端称为栈底（bottom）
  • 当栈中没有数据元素时称为空栈
  • 向一个栈中插入元素称为入栈
  • 从一个栈中删除元素称为出栈
  • 因为栈的插入和删除操作仅在栈顶进行，后进栈的元素必然先出栈，所以又把堆栈称为后进先出表（Last In First Out，简称LIFO）


栈的业余词汇：push入栈、pop出栈、peek获取栈顶元素

栈的存储构造

和线性表相似，堆栈也有两种根本的存储构造：顺序存储构造和链式存储构造

  • 程序栈
  • 链栈

队列定义

  • 队列（queue）简称队，它同堆栈一样，也是一种运算受限的线性表
  • 仅容许在表的一端进行插入，而在表的另一端进行删除
  • 在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）
  • 向队尾插入元素称为入队，新元素入队后称为新的队尾元素
  • 从队列中删除元素称为出队，元素出队后，其后续元素成为新的队首元素
  • 因为队列的插入和删除操作别离在队尾和队首进行，每个元素必然依照进入的秩序归队，也就是说先进队的元素必然先归队，所以称队列为先进先出表（First In First Out，FIFO）

队列的存储构造

  • 程序队列

    • 办法一：应用数组作为存储构造

      • 毛病：通过出队操作将数据弹出队列后，front之前的空间不能再次失去，会导致大量空间失落

    • 办法二：应用循环数组作为存储构造

      • 在循环数组中，开端元素的下一个元素不是数组外，而是数组的头元素，这样就能再次应用front之前的存储空间了

  • 链式队列

    • 能够应用单链表实现（带头节点）
    • 链表的头部作为队首，链表的尾部作为队尾
    • 一共设置两个指针，一个队首指针和一个队尾指针
    • 队首指针指向队首元素的前一个结点，即始终指向链表中空的头结点；队尾指针指向队列以后队尾元素所在结点
    • 当队列为空时，队首指针和队尾指针都指向空的头结点

  • 双端队列（double ended queue）

    • 双端队列指两端都能够进行出队和入队操作的队列，将队列的两端别离称为前端和后端
    • 双端队列进队时，前端进的元素排在队列中后端进的元素的后面，后端进的元素排在队列中前端进的元素的前面
    • 双端队列出队时，无论前端出还是后端出，先出的元素排在后出的元素的后面

    • 输入受限的双端队列，即一个端点能够插入和删除，另一个端点只能插入

    • 输出受限的双端队列，即一个端点能够插入和删除，另一个端点只能删除

    • 双端队列既能够用来实现队列，也能够用来实现栈（只操作一端就是栈了，Java中就是这样做的）

Java中的栈和队列类

  • Stack类：栈类，过期，因为他的父类Vector过期
  • Queue类：队列类（接口）

  • Deque类：双端队列（接口，栈操作应用，当成栈）

    • LinkedList即能够当线性表，又能够当栈，还能够当队列
  • Java中实现栈和队列操作都能够通过应用LinkedList类实现，底层应用的是链表

借助栈实现十进制转换二进制

public class TestConvert {    public static void main(String[] args) {        int t = 13;        int n = t;        //定义空栈，寄存余数        Deque deque = new LinkedList();        do {            int mod = n % 2;            //余数入栈            deque.push(mod);            n = n / 2;        }while (n != 0);        //打印后果        System.out.print(t+"---->");        while (!deque.isEmpty()){            System.out.print(deque.pop());        }    }}