Java版的数据结构——栈和队列

1. 栈（Stack）

1.1 概念

1.2 栈的使用

1.3 栈的模拟实现

1.4 栈的应用场景

1.4.1 改变元素的序列

1.4.2 将递归转化为循环

2. 队列（Queue）

2.1 概念

2.2 队列的使用

2.3 队列模拟实现

2.4 循环队列

3. 双端队列（Deque）

1. 栈（Stack）

1.1 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

1.2 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());  // 获取栈中有效元素个数---> 4System.out.println(s.peek());  // 获取栈顶元素---> 4s.pop();  // 4出栈，栈中剩余1  2  3，栈顶元素为3System.out.println(s.pop());  // 3出栈，栈中剩余1 2  栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}
}

1.3 栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

import java.util.Arrays;public class MyStack {//创建一个顺序栈public int[] elem;public int usedSize;public MyStack(){this.elem = new int[10];}//压栈public void push(int val){//首先判断栈是不是满了if(isFull()){//扩容elem = Arrays.copyOf(elem,elem.length * 2);}elem[usedSize++] = val;}//出栈public int pop(){if (isEmpty()){throw new EmptyException("栈是空的！");}return elem[--usedSize];}//查看栈顶public int peek(){if(isEmpty()){throw new EmptyException("栈是空的！");}return elem[usedSize - 1];}//判断栈是不是空了public boolean isEmpty(){return usedSize == 0;}//栈的大小public int size(){return usedSize;}//判断栈是不是满了public boolean isFull(){return usedSize == elem.length;}
}

1.4 栈的应用场景

1.4.1 改变元素的序列

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（C）。
A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

1.4.2 将递归转化为循环

// 递归方式
void printList(Node head){if(null != head){printList(head.next);}System.out.print(head.val + " ");
}

Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}

2. 队列（Queue）

2.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First
In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头
（Head/Front）

2.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中的有效元素个数
boolean isEmpty()	检测队列是否为空

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);          // 从队尾入队列System.out.println(q.size());System.out.println(q.peek());  // 获取队头元素q.poll();System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

2.3 队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。

小伙伴们思考下：队列的实现使用顺序结构还是链式结构好？【在下列的循环队列解释】

//链式队列
public class MyQueue {//首先创建结点，用内部类实现static class Node{public int val;public Node next;//构造方法public Node(int val){this.val = val;}}//有个队头指针和队尾指针public Node head;public Node last;//队列的大小public int usedSize;//入队public void offer(int val){Node node = new Node(val);if(head == null){//证明队列为空head = node;last = node;}else{//如果有元素了last.next = node;last = node;}usedSize++;}//出队public int poll() {//判断队列是否为空if (empty()) {throw new EmptyException("队列为空");//自定义异常类}int ret = head.val;head = head.next;if (head == null) {last = null;//只有一个结点时，那么last也要置空。因为如果last不置空，出队的结点还是有引用指向它，它就不会被gc回收}usedSize--;return ret;}//判断队列是否为空public boolean empty() {return usedSize == 0;}//查看队头元素public int peek(){//判断队列是否为空if (empty()) {throw new EmptyException("队列为空");//自定义异常类}return head.val;}//获得队列大小public int getUsedSizeize(){return usedSize;}}

2.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

如果是普通的顺序队列，就会导致队头标记跑到了数组的末尾，导致存储空间的浪费，这也就是上面的队列实现要使用链式队列的原因

数组下标循环的小技巧
1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

如何区分空与满

1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记

代码实现：

//循环队列
public class MyCircularQueue {private int elem[];private int front;//表示队列的头private int rear;//表示队列的尾//创建循环队列public MyCircularQueue(int k) {//如果是浪费空间，这里必须多加一个1this.elem = new int[k + 1];}//判断队列是否为满public boolean isFull() {return (rear + 1) % elem.length == front;}//入队列public boolean enQueue(int value) {//1. 检查是否队列是满的if (isFull()) {return false;}rear = (rear + 1) % elem.length;elem[rear] = value;return true;}//出队列public boolean deQueue() {//队列为空if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}//得到队头元素public int Front() {if (isEmpty()) {return -1;}return elem[front];}//得到队尾元素public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length - 1 : rear-1;return elem[index];}//判读队列是否为空public boolean isEmpty() {return front == rear;}
}