栈和队列.
目录
1. 栈（Stack）
2. 栈的模拟实现
3. 栈的应用场景
4. 队列（Queue）
5. 队列的模拟实现
6. 循环队列
7. 双端队列（Deque）
8. 面试题
1. 栈（Stack）
栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫出栈，出数据在栈顶
2. 栈的模拟实现
import java.util.Arrays;
import java.util.Stack;public class MyStack {public int[] data;public int usedSize;public MyStack() {this.data = new int[10];this.usedSize = 0;}public void push(int x) {if (usedSize == data.length) {//扩容this.data = Arrays.copyOf(data, data.length * 2);}data[usedSize] = x;usedSize++;}public int pop() {if (empty()) {throw new EmptyStackException();}return data[--usedSize];}public int peek() {if (empty()) {throw new EmptyStackException();}return data[usedSize - 1];}public boolean empty() {return usedSize == 0;}
}
如果使用单链表来实现栈，可以采用头插法入栈和出栈
采用双向链表来实现栈，头插、尾插均可以
3. 栈的应用场景
20. 有效的括号 - 力扣（LeetCode）
150. 逆波兰表达式求值 - 力扣（LeetCode）
栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
155. 最小栈 - 力扣（LeetCode）
4. 队列（Queue）
队列：只允许在一端进行插入数据操作，另一端进行删除数据操作的特殊线性表。队列具有先进先出FIFO(First In First Out)的特点
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
在Java中，Queue是一个接口，底层是通过链表实现
5. 队列的模拟实现
单链表、双向链表都可以实现。
用双向链表来实现：
public class MyQueue {static class ListNode {public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val = val;}}public ListNode first = null;public ListNode last = null;public int usedSize = 0;public void offer(int val) {ListNode newNode = new ListNode(val);if (first == null) {first = newNode;last = newNode;usedSize++;} else {last.next = newNode;newNode.prev = last;last = last.next;usedSize++;}}public int poll() { //删除if (first == null) {return -1;}int val = first.val;first = first.next;if (first != null) {//first.prev = null;}usedSize--;return val;}public int peek() {if (first == null) {return -1;}return first.val;}public boolean isEmpty() {return first == null;}
}
6. 循环队列
环形队列通常使用数组实现。
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
622. 设计循环队列 - 力扣（LeetCode）
7. 双端队列（Deque）
双端队列是指允许两端都可以进行入队和出队操作的队列，deque是"double ended queue"的简称
说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
Deque<Integer> stack1 = new ArrayDeque<>();//双端队列的线性实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现8. 面试题
225. 用队列实现栈 - 力扣（LeetCode）
232. 用栈实现队列 - 力扣（LeetCode）