当前位置：首页 > news >正文

数据结构（二）队列和栈

news 2026/5/12 20:44:50

1 基本API

2 实现栈（用标准库的链表）

3 实现队列（用标准库的链表）

4 实现栈（用标准库的数组）

5 实现队列（用之前实现的环形数组）

6 双端队列

队列（先进先出FIFO）和栈（后进先出LIFO）的原理非常简单，它们底层实现就是数组或链表，只不过仅仅提供在头尾操作元素的 API，所以我们常说它们是操作受限的数据结构。

队列只能在「队尾（Rear）」插入元素，「队头（Front）」删除元素；

栈只能在「栈顶（Top）」插入和删除元素。

1 基本API

// 队列的基本 API class MyQueue<E> { // 向队尾插入元素，时间复杂度 O(1) void push(E e); // 从队头删除元素，时间复杂度 O(1) E pop(); // 查看队头元素，时间复杂度 O(1) E peek(); // 返回队列中的元素个数，时间复杂度 O(1) int size(); }

// 栈的基本 API class MyStack<E> { // 向栈顶插入元素，时间复杂度 O(1) void push(E e); // 从栈顶删除元素，时间复杂度 O(1) E pop(); // 查看栈顶元素，时间复杂度 O(1) E peek(); // 返回栈中的元素个数，时间复杂度 O(1) int size(); }

2 实现栈（用标准库的链表）

把双链表的尾部作为栈顶，在双链表尾部增删元素的时间复杂度都是 O(1)，符合要求。

package Theoretical_foundation.stack; import java.util.LinkedList; public class MyLinkedStack<E> { //stack 是栈的底层容器,从创建栈开始，stack 就固定指向这个链表，全程不会、也不能换其他容器 //很多人会误以为[加了final，stack 就不能 push、pop 了] —— 这是完全错误的！ //final 只限制「list 引用不能变」，不限制「list 内部的元素操作」 private final LinkedList<E> stack = new LinkedList<>(); public void push(E e) { stack.addLast(e); } public E pop() { return stack.removeLast(); } public E peek() { return stack.getLast(); } public int size() { return stack.size(); } public static void main(String[] args) { MyLinkedStack<Integer> stack = new MyLinkedStack<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.peek()); // 3 System.out.println(stack.pop()); // 3 System.out.println(stack.peek()); // 2 } }

3 实现队列（用标准库的链表）

把双链表的尾部作为队尾，把双链表的头部作为队头，在双链表的头删、尾增元素的复杂度都是 O(1)，符合队列 API 的要求。

package Theoretical_foundation.queue; import java.util.LinkedList; public class MyLinkedQueue<E> { private final LinkedList<E> queue = new LinkedList<>(); public void push(E e) { queue.addLast(e); } public E pop() { return queue.removeFirst(); } public E peek() { return queue.getFirst(); } public int size() { return queue.size(); } public static void main(String[] args) { MyLinkedQueue<Integer> queue = new MyLinkedQueue<>(); queue.push(1); queue.push(2); queue.push(3); System.out.println(queue.peek()); // 1 System.out.println(queue.pop()); // 1 System.out.println(queue.pop()); // 2 System.out.println(queue.peek()); // 3 } }

4 实现栈（用标准库的数组）

数组尾部增删元素的时间复杂度都是 O(1)，符合栈的要求。

package Theoretical_foundation.stack; import java.util.ArrayList; public class MyArrayStack<E> { private ArrayList<E> stack = new ArrayList<>(); public void push(E e) { stack.add(e); } public E pop() { return stack.remove(stack.size() - 1); } public E peek() { return stack.get(stack.size() - 1); } public int size() { return stack.size(); } public static void main(String[] args) { MyArrayStack<Integer> stack = new MyArrayStack<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.peek()); // 3 System.out.println(stack.pop()); // 3 System.out.println(stack.peek()); // 2 } }

5 实现队列（用之前实现的环形数组）

有了前文环形数组中实现的类CycleArray，用CycleArray作为底层数据结构实现队列就不难了，在CycleArray的头删、尾增元素的复杂度都是 O(1)，符合队列 API 的要求。

package Theoretical_foundation.queue; import Theoretical_foundation.array.CycleArray; public class MyCycleArrayQueue<E> { private CycleArray<E> queue = new CycleArray<>(); public void push(E e) { queue.addLast(e); } public void pop() { queue.removeFirst(); } public E peek() { return queue.getFirst(); } public int size() { return queue.size(); } public static void main(String[] args) { MyLinkedQueue<Integer> queue = new MyLinkedQueue<>(); queue.push(1); queue.push(2); queue.push(3); System.out.println(queue.peek()); // 1 System.out.println(queue.pop()); // 1 System.out.println(queue.pop()); // 2 System.out.println(queue.peek()); // 3 } }