Java中栈的实现---Stack、Deque、自定义实现

栈(Stack)是一种经典的后进先出(LIFO)数据结构，在Java中有多种实现方式。本文将详细介绍Java中栈的三种主要实现方式：使用遗留的Stack类、更现代的Deque接口以及自定义实现。

1. 使用Stack类实现

import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();// 压栈操作stack.push(1);stack.push(2);stack.push(3);// 查看栈顶元素System.out.println("栈顶元素: " + stack.peek()); // 输出3// 出栈操作System.out.println("出栈: " + stack.pop()); // 输出3System.out.println("出栈: " + stack.pop()); // 输出2// 判断栈是否为空System.out.println("栈是否为空: " + stack.empty()); // 输出false// 搜索元素位置(从栈顶开始为1)System.out.println("元素1的位置: " + stack.search(1)); // 输出1}
}

所有方法都是同步的，这在单线程环境下会造成不必要的性能开销

2. 使用Deque接口实现

import java.util.ArrayDeque;
import java.util.Deque;public class DequeStackExample {public static void main(String[] args) {Deque<Integer> stack = new ArrayDeque<>();// 压栈操作stack.push(1);stack.push(2);stack.push(3);// 查看栈顶元素System.out.println("栈顶元素: " + stack.peek()); // 输出3// 出栈操作System.out.println("出栈: " + stack.pop()); // 输出3System.out.println("出栈: " + stack.pop()); // 输出2// 判断栈是否为空System.out.println("栈是否为空: " + stack.isEmpty()); // 输出false// 注意：Deque没有search方法}
}

ArrayDeque基于数组实现，比Stack更高效

3. 自定义栈实现

package com.zsy.collections;public class ArrayStack<E> {private Object [] stackArray;private int top;private int capacity;public ArrayStack() {this(10);}public ArrayStack(int capacity) {stackArray = new Object[capacity];top = -1;this.capacity = capacity;}// 入栈public void push(E element) {if (isFull()) {//扩容resize();}stackArray[++top] = element;}private void resize() {int newCapacity = capacity * 2;Object[] newElements = new Object[newCapacity];System.arraycopy(stackArray, 0, newElements, 0, top);stackArray = newElements;capacity = newCapacity;}// 出栈public E pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return (E)stackArray[top--];}// 查看栈顶元素public E peek() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return (E)stackArray[top];}// 判断栈是否为空public boolean isEmpty() {return top == -1;}// 栈中有多少元素public int size() {return top + 1;}// 判断栈是否已满public boolean isFull() {return top == stackArray.length - 1;}
}

更加定制化，我增加了一个扩容机制

还有一个基于链表的栈实现

package com.zsy.collections;public class ListStack {private StackNode top;// 入栈public void push(int element) {StackNode newNode = new StackNode(element);newNode.next = top;top = newNode;}// 出栈public int pop() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}int popped = top.data;top = top.next;return popped;}// 查看栈顶元素public int peek() {if (isEmpty()) {throw new RuntimeException("Stack is empty");}return top.data;}// 判断栈是否为空public boolean isEmpty() {return top == null;}class StackNode {int data;StackNode next;public StackNode(int data) {this.data = data;this.next = null;}}
}