数据结构---栈（Stack）

1. 简介

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

1. 压栈（Push）：将一个元素添加到栈的顶部。

2. 弹栈（Pop）：移除栈顶部的元素，并返回该元素的值。

3. 查看栈顶（Peek）：返回栈顶部的元素，但不将其从栈中移除。

4. 检查栈空（IsEmpty）：检查栈是否为空，通常用于在执行操作前确保栈中至少有一个元素。

5. 获取栈大小（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}
}

2.4 总结

• 数组实现：适用于栈大小已知且不频繁改变大小的情况。push和pop操作的时间复杂度为O(1)，但如果栈满时，扩展数组会带来一定的性能开销。

• 链表实现：适用于栈大小不固定的情况。链表实现的栈无需考虑容量问题，但每次操作时需要额外的内存空间来存储节点指针。

• Deque实现：这是最推荐的实现方式，因为它提供了高效的push和pop操作，并且实现简洁。

Deque接口可以通过LinkedList或ArrayDeque来实现。如果追求性能，ArrayDeque通常是更好的选择，因为它的底层是基于数组的，避免了链表的节点分配开销。

相关笔试题：基于栈（stack）的部分笔试题

不积跬步，无以至千里 --- xiaokai