栈和队列.

目录

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）