Java中的栈与队列
站长
· 阅读数 12
已同步发布于我的博客
栈
标准库 java.util.Stack 实现
在 java.util 中封装了 Stack 类，其继承自Vector类，定义了push、pop、peek、empty、search五个操作对Vector进行了扩展，JDK源码（已省去jdoc）如下：
public class Stack<E> extends Vector<E> {
public Stack() {
}
// ...
public E push(E item) {
addElement(item);
return item;
}
// ...
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
// ...
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
// ...
public boolean empty() {
return size() == 0;
}
// ...
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
@java.io.Serial
private static final long serialVersionUID = 1224463164541339165L;
}
Deque接口实现
在Java中，栈可以使用java.util.Stack类实现，也可以使用 java.util.LinkedList 结合push和pop操作来实现自定义的栈。通常，建议使用 Deque接口中的 LinkedList 实现来代替java.util.Stack，因为后者是基于向量的数据结构，性能较差。
示例代码：
public class StackByDeque {
public static void main(String[] args) {
Deque<Integer> stack = new LinkedList<>();
stack.push(1);
stack.push(2);
int top = stack.pop();
System.out.println(top + " " + stack.size());
}
}
其中，值得注意的是 LinkedList 类。LinkedList是Java中的一个双向链表实现，它继承自AbstractSequentialList类，并实现了List和Deque接口，同时提供了双向链表的功能。JDK中的源码如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
...
LinkedList 类有以下的特点：
- 双向链表:
LinkedList是基于双向链表数据结构的实现，每个元素都被包装在一个节点中，而每个节点都包含指向前一个节点和后一个节点的引用。这使得在链表中插入和删除元素的操作非常高效，因为只需要调整节点的引用，而不需要移动其他元素。 - 实现了List接口:
LinkedList实现了List接口，这意味着它可以像ArrayList一样用于存储有序的元素集合，支持随机访问、按索引插入和删除元素。与ArrayList不同，LinkedList在插入和删除操作上通常更高效，但在随机访问上性能较差。 - 实现了Deque接口:
LinkedList还实现了Deque接口，这使得它可以被用作双端队列（double-ended queue）。您可以在队列的前端和后端进行插入和删除操作，支持先进先出（FIFO）和后进先出（LIFO）等不同的数据操作模式。 - 适合用于栈和队列: 由于
LinkedList支持双向操作，它特别适合用作栈和队列的基础数据结构。您可以使用push和pop操作来实现栈，使用offer和poll操作来实现队列。 - 非线程安全: 与
ArrayList不同，LinkedList是非线程安全的，这意味着在多线程环境下需要进行额外的同步处理，或者使用java.util.concurrent包中的并发数据结构来保证线程安全。 - 动态大小:
LinkedList的大小是动态的，它会根据需要动态分配内存。这意味着它可以容纳任意数量的元素，但需要根据实际使用情况分配和释放内存，可能会引入一些内存管理开销。
LinkedList是一个灵活的双向链表实现，适合用于需要频繁插入和删除操作的情况，以及栈和队列等数据结构的实现。但需要注意，对于需要随机访问的情况，ArrayList通常更为高效。
自定义实现
1. 使用数组
可以使用数组来实现栈，通过维护一个指向栈顶元素的指针（通常称为top），以及数组来存储栈的元素。当进行push和pop操作时，相应地更新栈顶指针和数组元素。这种实现方式的优点是简单，但需要注意数组大小的限制。
public class ArrayStack {
private int maxSize; // 栈的最大容量
private int top; // 栈顶指针
private int[] stack; // 存储元素的数组
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.stack = new int[maxSize];
this.top = -1; // 栈开始时为空
}
// 判断栈是否为空
public boolean isEmpty() {
return top == -1;
}
// 判断栈是否已满
public boolean isFull() {
return top == maxSize - 1;
}
// 入栈
public void push(int item) {
if (isFull()) {
System.out.println("栈已满，无法入栈");
return;
}
stack[++top] = item;
}
// 出栈
public int pop() {
if (isEmpty()) {
System.out.println("栈为空，无法出栈");
return -1; // 返回一个特定的值表示栈为空
}
return stack[top--];
}
// 查看栈顶元素
public int peek() {
if (isEmpty()) {
System.out.println("栈为空，无法查看栈顶元素");
return -1; // 返回一个特定的值表示栈为空
}
return stack[top];
}
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈顶元素：" + stack.peek());
while (!stack.isEmpty()) {
System.out.println("出栈元素：" + stack.pop());
}
}
}
2. 使用链表:
类似于使用数组，您可以使用链表来实现栈。链表的头节点可以充当栈顶，而push和pop操作将在链表头部进行。这种实现方式通常不会受到数组大小的限制，并且在动态大小方面更加灵活。
public class LinkedListStack<T> {
private Node<T> top; // 栈顶节点
private static class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
// 判断栈是否为空
public boolean isEmpty() {
return top == null;
}
// 入栈
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top;
top = newNode;
}
// 出栈
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("栈为空，无法出栈");
}
T data = top.data;
top = top.next;
return data;
}
// 查看栈顶元素
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("栈为空，无法查看栈顶元素");
}
return top.data;
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈顶元素：" + stack.peek());
while (!stack.isEmpty()) {
System.out.println("出栈元素：" + stack.pop());
}
}
}
3. 使用单链表节点
如果不需要支持pop操作，只需要实现push和peek，您可以使用单链表节点来创建一个简化的栈。每个节点包含数据和一个指向下一个节点的引用。
public class SingleLinkedListStack<T> {
private Node<T> top; // 栈顶节点
private static class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
// 判断栈是否为空
public boolean isEmpty() {
return top == null;
}
// 入栈
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top;
top = newNode;
}
// 出栈
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("栈为空，无法出栈");
}
T data = top.data;
top = top.next;
return data;
}
// 查看栈顶元素
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("栈为空，无法查看栈顶元素");
}
return top.data;
}
public static void main(String[] args) {
SingleLinkedListStack<Integer> stack = new SingleLinkedListStack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈顶元素：" + stack.peek());
while (!stack.isEmpty()) {
System.out.println("出栈元素：" + stack.pop());
}
}
}
4. 使用双链表节点
如果需要支持pop操作和更高效的pop和peek操作，可以使用双链表节点来实现栈。这种实现方式允许从栈顶和栈底执行pop和peek操作。
public class DoubleLinkedListStack<T> {
private Node<T> top; // 栈顶节点
private static class Node<T> {
T data;
Node<T> prev;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
// 判断栈是否为空
public boolean isEmpty() {
return top == null;
}
// 入栈
public void push(T item) {
Node<T> newNode = new Node<>(item);
if (top != null) {
newNode.next = top;
top.prev = newNode;
}
top = newNode;
}
// 出栈
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("栈为空，无法出栈");
}
T data = top.data;
top = top.next;
if (top != null) {
top.prev = null;
}
return data;
}
// 查看栈顶元素
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("栈为空，无法查看栈顶元素");
}
return top.data;
}
public static void main(String[] args) {
DoubleLinkedListStack<Integer> stack = new DoubleLinkedListStack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈顶元素：" + stack.peek());
while (!stack.isEmpty()) {
System.out.println("出栈元素：" + stack.pop());
}
}
}
自定义栈的实现方式可以根据特定需求选择，但需要注意线程安全和性能方面的考虑。
队列
java.util.Queue 接口实现
Java提供了java.util.Queue接口，是队列的标准接口。可以使用不同的实现类来创建队列，包括：
java.util.LinkedList：基于双向链表的实现，支持先进先出（FIFO）操作。java.util.PriorityQueue：优先级队列的实现，元素按照优先级顺序排列。
以下使用java.util.LinkedList来实现队列。offer方法用于将元素入队列，poll方法用于出队列。由于LinkedList实现了Queue接口，可以方便地使用它来实现队列的操作
public class QueueByLinkedList {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 入对列
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 出队列
while (!queue.isEmpty()){
System.out.println("出队元素： " + queue.poll());
}
}
}
PriorityQueue是一个优先级队列，它根据元素的优先级来排列队列中的元素。较小的元素具有较高的优先级。使用offer方法入队列，poll方法出队列，优先级较高的元素会首先被出队列。
public class QueueByPriorityQueue {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
// 入对列
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 出队列
while (!queue.isEmpty()){
System.out.println("出队元素： " + queue.poll());
}
}
}
使用 java.util.concurrent 包中的队列
Java的java.util.concurrent包提供了多线程安全的队列实现，用于多线程环境。一些常见的实现包括：
java.util.concurrent.LinkedBlockingQueue：基于链表的阻塞队列。java.util.concurrent.ArrayBlockingQueue：基于数组的阻塞队列。java.util.concurrent.PriorityBlockingQueue：多线程安全的优先级队列。
自定义队列
此外，还可以使用数组或链表等数据结构来自定义队列的实现，根据特定需求创建自己的队列类。这通常需要额外的编程工作，但可以满足特定场景的需求。
总结
本文总结了Java中栈和队列的几种实现方式:
-
栈的实现:
- 使用Java标准库中的Stack类
- 使用Deque接口中的LinkedList实现栈操作
- 自定义数组栈、链表栈、单链表栈、双链表栈
-
队列的实现:
- 使用Java标准库中的Queue接口及其实现类LinkedList、PriorityQueue
- 使用java.util.concurrent包下的阻塞队列
- 自定义使用数组或链表实现的队列