栈和队列

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

栈的定义

• 栈（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());
        }
    }
}