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

数据结构---栈（Stack）

news 2025/8/13 5:10:14

1. 简介

栈（Stack）是计算机科学中的一种抽象数据类型，它遵循特定的操作顺序，即后进先出（Last In First Out，LIFO）。这意味着最后添加到栈中的元素将是第一个被移除的。栈的基本操作通常包括：

压栈（Push）：将一个元素添加到栈的顶部。
弹栈（Pop）：移除栈顶部的元素，并返回该元素的值。
查看栈顶（Peek）：返回栈顶部的元素，但不将其从栈中移除。
检查栈空（IsEmpty）：检查栈是否为空，通常用于在执行操作前确保栈中至少有一个元素。
获取栈大小（Size）：返回栈中元素的数量。

栈可以用数组或链表来实现。数组实现的栈具有固定的大小，而链表实现的栈可以动态调整大小。

2. 实例

2.1 基于数组实现

public class StackUsingArray {private int[] stack;private int top;private int capacity;public StackUsingArray(int capacity) {this.capacity = capacity;stack = new int[capacity];top = -1;}// Push element onto the stackpublic void push(int item) {if (top == capacity - 1) {System.out.println("Stack is full!");} else {stack[++top] = item;}}// Pop element from the stackpublic int pop() {if (top == -1) {System.out.println("Stack is empty!");return -1;} else {return stack[top--];}}// Peek the top element of the stackpublic int peek() {if (top == -1) {System.out.println("Stack is empty!");return -1;} else {return stack[top];}}// Check if stack is emptypublic boolean isEmpty() {return top == -1;}// Get the size of the stackpublic int size() {return top + 1;}public static void main(String[] args) {StackUsingArray stack = new StackUsingArray(5);stack.push(10);stack.push(20);stack.push(30);System.out.println("Top element: " + stack.peek()); // Output: 30System.out.println("Popped element: " + stack.pop()); // Output: 30System.out.println("Stack size: " + stack.size()); // Output: 2}
}

可以增加扩容机制---》ArrayDeque源码中扩容规则：如果数小则翻倍，否则增加50%。

private void grow(int needed) {// overflow-conscious codefinal int oldCapacity = elements.length;int newCapacity;// Double capacity if small; else grow by 50%int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);if (jump < needed|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)newCapacity = newCapacity(needed, jump);final Object[] es = elements = Arrays.copyOf(elements, newCapacity);// Exceptionally, here tail == head needs to be disambiguatedif (tail < head || (tail == head && es[head] != null)) {// wrap around; slide first leg forward to end of arrayint newSpace = newCapacity - oldCapacity;System.arraycopy(es, head,es, head + newSpace,oldCapacity - head);for (int i = head, to = (head += newSpace); i < to; i++)es[i] = null;}
}

2.2 基于链表实现

public class StackUsingLinkedList {private Node top;private class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}}// Push element onto the stackpublic void push(int item) {Node newNode = new Node(item);newNode.next = top;top = newNode;}// Pop element from the stackpublic int pop() {if (top == null) {System.out.println("Stack is empty!");return -1;} else {int poppedData = top.data;top = top.next;return poppedData;}}// Peek the top element of the stackpublic int peek() {if (top == null) {System.out.println("Stack is empty!");return -1;} else {return top.data;}}// Check if stack is emptypublic boolean isEmpty() {return top == null;}// Get the size of the stackpublic int size() {int size = 0;Node current = top;while (current != null) {size++;current = current.next;}return size;}public static void main(String[] args) {StackUsingLinkedList stack = new StackUsingLinkedList();stack.push(10);stack.push(20);stack.push(30);System.out.println("Top element: " + stack.peek()); // Output: 30System.out.println("Popped element: " + stack.pop()); // Output: 30System.out.println("Stack size: " + stack.size()); // Output: 2}
}

2.3 基于Deque实现类实现

Java中的Deque接口提供了一个双端队列实现，可以非常方便地用来实现栈。

import java.util.Deque;
import java.util.LinkedList;public class StackUsingDeque {private Deque<Integer> stack;public StackUsingDeque() {stack = new LinkedList<>();}// Push element onto the stackpublic void push(int item) {stack.push(item);}// Pop element from the stackpublic int pop() {if (stack.isEmpty()) {System.out.println("Stack is empty!");return -1;} else {return stack.pop();}}// Peek the top element of the stackpublic int peek() {if (stack.isEmpty()) {System.out.println("Stack is empty!");return -1;} else {return stack.peek();}}// Check if stack is emptypublic boolean isEmpty() {return stack.isEmpty();}// Get the size of the stackpublic int size() {return stack.size();}public static void main(String[] args) {StackUsingDeque stack = new StackUsingDeque();stack.push(10);stack.push(20);stack.push(30);System.out.println("Top element: " + stack.peek()); // Output: 30System.out.println("Popped element: " + stack.pop()); // Output: 30System.out.println("Stack size: " + stack.size()); // Output: 2}
}