栈的定义
栈是一种先进后出的数据结构。它的操作受限。
栈，是一种先进后出，或者后进先出的数据结构。跟数组和链表相比，有一定的限制性。毕竟，它也有自己的适用场景，比如：函数调用，表达式求值等等。栈有2个操作，入栈，出栈。时间复杂度都是O(1)。
实现一个栈
实现一个栈：怎么实现呢，有2种方式，用数组实现或者用链表实现。用数组实现的叫做顺序栈，用链表实现的叫做链式栈。
用数组实现栈
先用数组实现，不考虑扩容的情况，代码如下：
class Stack: def __init__(self): self.stack = [] # 入栈操作 def push(self, item): self.stack.append(item) # 出栈操作 def pop(self): if not self.is_empty(): return self.stack.pop() else: return None # 查看栈顶元素 def peek(self): if not self.is_empty(): return self.stack[-1] else: return None # 判断栈是否为空 def is_empty(self): return len(self.stack) == 0 # 获取栈的大小 def size(self): return len(self.stack)
这是python的实现方式。可以再看下java的实现方式，如下图：
public class Stack { private int[] elements; private int top; private int capacity; // 初始化栈，设置初始容量 public Stack(int capacity) { this.capacity = capacity; elements = new int[capacity]; top = -1; // 初始时栈顶为-1，表示栈为空 } // 入栈操作 public void push(int item) { if (!isFull()) { top++; elements[top] = item; } else { System.out.println("栈已满，无法添加元素"); } } // 出栈操作 public int pop() { if (!isEmpty()) { return elements[top--]; } else { System.out.println("栈为空，无法删除元素"); return -1; // 或者可以抛出一个异常 } } // 查看栈顶元素 public int peek() { if (!isEmpty()) { return elements[top]; } else { System.out.println("栈为空，没有元素可查看"); return -1; // 或者可以抛出一个异常 } } // 检查栈是否为空 public boolean isEmpty() { return top == -1; } // 检查栈是否已满 private boolean isFull() { return top == capacity - 1; } // 获取栈的大小 public int size() { return top + 1; } // 展示栈的内容（可选） public void displayStack() { if (isEmpty()) { System.out.println("栈为空"); } else { for (int i = top; i >= 0; i--) { System.out.print(elements[i] + " "); } System.out.println(); } } // 主函数，用于测试栈的实现 public static void main(String[] args) { Stack stack = new Stack(5); // 创建一个容量为5的栈 stack.push(1); stack.push(2); stack.push(3); stack.displayStack(); // 显示栈的内容 System.out.println("栈顶元素: " + stack.peek()); stack.pop(); stack.pop(); stack.displayStack(); // 再次显示栈的内容 System.out.println("栈的大小: " + stack.size()); System.out.println("栈是否为空: " + stack.isEmpty()); } }
用链表实现栈
用数组实现完了，再用链表实现，如下图：
class Node: def __init__(self, data=None): self.data = data self.next = None class Stack: def __init__(self): self.top = None # 入栈操作 def push(self, data): if self.top is None: self.top = Node(data) else: new_node = Node(data) new_node.next = self.top self.top = new_node # 出栈操作 def pop(self): if self.top is None: return None else: popped = self.top.data self.top = self.top.next return popped # 查看栈顶元素 def peek(self): return self.top.data if self.top else None # 判断栈是否为空 def is_empty(self): return self.top is None # 测试代码 s = Stack() s.push(1) s.push(2) s.push(3) print(s.pop()) # 输出：3 print(s.peek()) # 输出：2 print(s.is_empty()) # 输出：False
java的实现方式，如下图：
public class Node<T> { private T data; private Node<T> next; public Node(T data) { this.data = data; this.next = null; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } } public class LinkedListStack<T> { private Node<T> top; public LinkedListStack() { this.top = null; } // 入栈操作 public void push(T data) { Node<T> newNode = new Node<>(data); newNode.setNext(top); top = newNode; } // 出栈操作 public T pop() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } T data = top.getData(); top = top.getNext(); return data; } // 查看栈顶元素 public T peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return top.getData(); } // 判断栈是否为空 public boolean isEmpty() { return top == null; } // 获取栈的大小 public int size() { int size = 0; Node<T> current = top; while (current != null) { size++; current = current.getNext(); } return size; } // 测试代码 public static void main(String[] args) { LinkedListStack<Integer> stack = new LinkedListStack<>(); stack.push(200); stack.push(300); stack.push(600); System.out.println(stack.pop()); System.out.println(stack.peek()); System.out.println(stack.isEmpty()); System.out.println(stack.size()); } }
好了，实现方式就是这样的。再来看看动态扩容的栈是怎么实现的。
支持动态扩容的栈
这个跟普通的栈有一个不同的地方，在入栈的时候栈满了会进行扩容，然后复制之前的数据，再进行入栈操作。用java实现，如下图：
public class DynamicArrayStack<T> { private static final int DEFAULT_CAPACITY = 10; private static final int RESIZE_FACTOR = 2; private Object[] elements; private int top; public DynamicArrayStack() { elements = new Object[DEFAULT_CAPACITY]; top = -1; } // 入栈操作 public void push(T item) { ensureCapacity(); elements[++top] = item; } // 出栈操作 public T pop() { if (isEmpty()) { throw new EmptyStackException(); } return (T) elements[top--]; } // 查看栈顶元素 public T peek() { if (isEmpty()) { throw new EmptyStackException(); } return (T) elements[top]; } // 判断栈是否为空 public boolean isEmpty() { return top == -1; } // 获取栈的大小 public int size() { return top + 1; } // 确保数组有足够的容量 private void ensureCapacity() { if (top == elements.length - 1) { resize(); } } // 调整数组大小 private void resize() { int newSize = elements.length * RESIZE_FACTOR; elements = Arrays.copyOf(elements, newSize); } // 测试代码 public static void main(String[] args) { DynamicArrayStack<Integer> stack = new DynamicArrayStack<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop()); // 输出：3 System.out.println(stack.peek()); // 输出：2 System.out.println(stack.size()); // 输出：2 System.out.println(stack.isEmpty()); // 输出：false } }
栈的应用
栈应用非常多，比如，在浏览器里有个向前，向后的箭头，就可以用2个栈来存储；函数的调用，也是可以用栈的。例子就不多举了。
小结
这篇文章讲述了栈的数据结构。
主要是讲解了栈的数据结构，以及实现，目的是了解底层的数据结构及应用，还有动态扩容的栈，栈的时间复杂度，空间复杂度都是O(1)。基本上就这么多。至于实现，用什么语言不重要，原理懂了，写一个，应该都不是什么难事。
