栈

算法

栈是一种遵循后进先出(LIFO)原则的线性数据结构。只允许在一端(栈顶)进行插入和删除操作。适用于需要回溯的问题解决过程。

空间复杂度:O(n)

算法讲解

栈(Stack)

介绍

栈是一种特殊的线性数据结构,遵循后进先出(Last-In-First-Out,LIFO)的原则。最后添加到栈中的元素将是第一个被移除的元素。可以将栈想象为一叠盘子,我们只能从顶部添加或移除盘子。

栈的操作仅限于栈顶,即只能在一端进行插入和删除操作。

核心特性

  1. 后进先出(LIFO):最后入栈的元素最先出栈
  2. 只允许在栈顶操作:只能在一端进行插入(压栈)和删除(弹栈)
  3. 快速访问栈顶元素:O(1)时间复杂度访问、添加和删除栈顶元素
  4. 元素访问受限:无法直接访问栈中间元素

基本操作

1. 入栈(push)

  • 时间复杂度:O(1)
  • 描述:将元素添加到栈顶

2. 出栈(pop)

  • 时间复杂度:O(1)
  • 描述:移除并返回栈顶元素

3. 查看栈顶(peek)

  • 时间复杂度:O(1)
  • 描述:查看栈顶元素但不移除

4. 判断栈是否为空(isEmpty)

  • 时间复杂度:O(1)
  • 描述:检查栈中是否有元素

5. 获取栈大小(size)

  • 时间复杂度:O(1)
  • 描述:获取栈中元素的数量

基础实现

代码实现

Java

▼
Java
复制代码
import java.util.Stack; public class StackExample { public static void main(String[] args) { // 创建栈 Stack<Integer> stack = new Stack<>(); // 入栈 stack.push(10); stack.push(20); stack.push(30); System.out.println("栈: " + stack); // 输出: [10, 20, 30] // 查看栈顶元素(不移除) int topElement = stack.peek(); System.out.println("栈顶元素: " + topElement); // 输出: 30 // 出栈 int poppedElement = stack.pop(); System.out.println("弹出的元素: " + poppedElement); // 输出: 30 // 检查栈是否为空 boolean isEmpty = stack.isEmpty(); System.out.println("栈是否为空: " + isEmpty); // 输出: false // 获取栈大小 int size = stack.size(); System.out.println("栈大小: " + size); // 输出: 2 System.out.println("最终栈: " + stack); // 输出: [10, 20] } }

使用数组实现栈

▼
Java
复制代码
public class ArrayStack<T> { private static final int DEFAULT_CAPACITY = 10; private Object[] array; private int top; // 栈顶指针 public ArrayStack() { array = new Object[DEFAULT_CAPACITY]; top = -1; // 初始为-1,表示栈为空 } // 入栈 public void push(T item) { if (top == array.length - 1) { // 栈满,需要扩容 resize(); } top++; array[top] = item; } // 出栈 @SuppressWarnings("unchecked") public T pop() { if (isEmpty()) { throw new IllegalStateException("栈为空"); } T item = (T) array[top]; array[top] = null; // 避免内存泄漏 top--; return item; } // 查看栈顶 @SuppressWarnings("unchecked") public T peek() { if (isEmpty()) { throw new IllegalStateException("栈为空"); } return (T) array[top]; } // 检查栈是否为空 public boolean isEmpty() { return top == -1; } // 获取栈大小 public int size() { return top + 1; } // 扩容 private void resize() { Object[] newArray = new Object[array.length * 2]; System.arraycopy(array, 0, newArray, 0, array.length); array = newArray; } public static void main(String[] args) { ArrayStack<Integer> stack = new ArrayStack<>(); stack.push(10); stack.push(20); stack.push(30); System.out.println("栈顶元素: " + stack.peek()); // 输出: 30 System.out.println("弹出的元素: " + stack.pop()); // 输出: 30 System.out.println("栈大小: " + stack.size()); // 输出: 2 System.out.println("栈是否为空: " + stack.isEmpty()); // 输出: false } }

JavaScript 实现

▼
Javascript
复制代码
class Stack { constructor() { this.items = []; } // 入栈 push(element) { this.items.push(element); } // 出栈 pop() { if (this.isEmpty()) { throw new Error("栈为空"); } return this.items.pop(); } // 查看栈顶 peek() { if (this.isEmpty()) { throw new Error("栈为空"); } return this.items[this.items.length - 1]; } // 判断栈是否为空 isEmpty() { return this.items.length === 0; } // 获取栈大小 size() { return this.items.length; } } // 使用示例 const stack = new Stack(); stack.push(10); stack.push(20); stack.push(30); console.log("栈顶元素:", stack.peek()); // 输出: 30 console.log("弹出的元素:", stack.pop()); // 输出: 30 console.log("栈大小:", stack.size()); // 输出: 2 console.log("栈是否为空:", stack.isEmpty()); // 输出: false

Python 实现

▼
Python
复制代码
class Stack: def __init__(self): self.items = [] # 入栈 def push(self, item): self.items.append(item) # 出栈 def pop(self): if self.is_empty(): raise Exception("栈为空") return self.items.pop() # 查看栈顶 def peek(self): if self.is_empty(): raise Exception("栈为空") return self.items[-1] # 判断栈是否为空 def is_empty(self): return len(self.items) == 0 # 获取栈大小 def size(self): return len(self.items) # 使用示例 if __name__ == "__main__": stack = Stack() stack.push(10) stack.push(20) stack.push(30) print("栈顶元素:", stack.peek()) # 输出: 30 print("弹出的元素:", stack.pop()) # 输出: 30 print("栈大小:", stack.size()) # 输出: 2 print("栈是否为空:", stack.is_empty()) # 输出: False

Go 实现

▼
Go
复制代码
package main import ( "errors" "fmt" ) // Stack 结构体 type Stack struct { items []interface{} } // 创建新栈 func NewStack() *Stack { return &Stack{ items: []interface{}{}, } } // Push 入栈 func (s *Stack) Push(item interface{}) { s.items = append(s.items, item) } // Pop 出栈 func (s *Stack) Pop() (interface{}, error) { if s.IsEmpty() { return nil, errors.New("栈为空") } n := len(s.items) item := s.items[n-1] s.items = s.items[:n-1] return item, nil } // Peek 查看栈顶 func (s *Stack) Peek() (interface{}, error) { if s.IsEmpty() { return nil, errors.New("栈为空") } return s.items[len(s.items)-1], nil } // IsEmpty 判断栈是否为空 func (s *Stack) IsEmpty() bool { return len(s.items) == 0 } // Size 获取栈大小 func (s *Stack) Size() int { return len(s.items) } func main() { stack := NewStack() stack.Push(10) stack.Push(20) stack.Push(30) top, _ := stack.Peek() fmt.Println("栈顶元素:", top) // 输出: 30 popped, _ := stack.Pop() fmt.Println("弹出的元素:", popped) // 输出: 30 fmt.Println("栈大小:", stack.Size()) // 输出: 2 fmt.Println("栈是否为空:", stack.IsEmpty()) // 输出: false }

C 实现

▼
C
复制代码
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int items[MAX_SIZE]; int top; } Stack; // 初始化栈 void initialize(Stack *stack) { stack->top = -1; } // 判断栈是否为空 bool isEmpty(Stack *stack) { return stack->top == -1; } // 判断栈是否已满 bool isFull(Stack *stack) { return stack->top == MAX_SIZE - 1; } // 获取栈大小 int size(Stack *stack) { return stack->top + 1; } // 入栈 void push(Stack *stack, int item) { if (isFull(stack)) { printf("栈已满,无法入栈\n"); return; } stack->items[++stack->top] = item; } // 出栈 int pop(Stack *stack) { if (isEmpty(stack)) { printf("栈为空,无法出栈\n"); return -1; } return stack->items[stack->top--]; } // 查看栈顶元素 int peek(Stack *stack) { if (isEmpty(stack)) { printf("栈为空,无法查看栈顶\n"); return -1; } return stack->items[stack->top]; } int main() { Stack stack; initialize(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); printf("栈顶元素: %d\n", peek(&stack)); // 输出: 30 printf("弹出的元素: %d\n", pop(&stack)); // 输出: 30 printf("栈大小: %d\n", size(&stack)); // 输出: 2 printf("栈是否为空: %s\n", isEmpty(&stack) ? "是" : "否"); // 输出: 否 return 0; }

C++实现

使用STL的stack容器

▼
C++
复制代码
#include <iostream> #include <stack> int main() { // 创建栈 std::stack<int> stack; // 入栈 stack.push(10); stack.push(20); stack.push(30); // 查看栈顶元素(不移除) std::cout << "栈顶元素: " << stack.top() << std::endl; // 输出: 30 // 出栈 stack.pop(); std::cout << "弹出元素后的栈顶: " << stack.top() << std::endl; // 输出: 20 // 检查栈是否为空 std::cout << "栈是否为空: " << (stack.empty() ? "是" : "否") << std::endl; // 输出: 否 // 获取栈大小 std::cout << "栈大小: " << stack.size() << std::endl; // 输出: 2 return 0; }

自定义栈实现

▼
C++
复制代码
#include <iostream> #include <vector> #include <stdexcept> template <typename T> class Stack { private: std::vector<T> items; public: // 入栈 void push(T item) { items.push_back(item); } // 出栈 T pop() { if (isEmpty()) { throw std::runtime_error("栈为空"); } T item = items.back(); items.pop_back(); return item; } // 查看栈顶 T peek() { if (isEmpty()) { throw std::runtime_error("栈为空"); } return items.back(); } // 判断栈是否为空 bool isEmpty() { return items.empty(); } // 获取栈大小 size_t size() { return items.size(); } }; int main() { Stack<int> stack; stack.push(10); stack.push(20); stack.push(30); std::cout << "栈顶元素: " << stack.peek() << std::endl; // 输出: 30 std::cout << "弹出的元素: " << stack.pop() << std::endl; // 输出: 30 std::cout << "栈大小: " << stack.size() << std::endl; // 输出: 2 std::cout << "栈是否为空: " << (stack.isEmpty() ? "是" : "否") << std::endl; // 输出: 否 return 0; }

使用数组实现栈

▼
C++
复制代码
#include <iostream> #include <stdexcept> #define MAX_SIZE 100 template <typename T> class ArrayStack { private: T items[MAX_SIZE]; int top; public: ArrayStack() { top = -1; } // 入栈 void push(T item) { if (top >= MAX_SIZE - 1) { throw std::overflow_error("栈已满"); } items[++top] = item; } // 出栈 T pop() { if (isEmpty()) { throw std::underflow_error("栈为空"); } return items[top--]; } // 查看栈顶 T peek() { if (isEmpty()) { throw std::underflow_error("栈为空"); } return items[top]; } // 判断栈是否为空 bool isEmpty() { return top == -1; } // 获取栈大小 int size() { return top + 1; } }; int main() { ArrayStack<int> stack; stack.push(10); stack.push(20); stack.push(30); std::cout << "栈顶元素: " << stack.peek() << std::endl; // 输出: 30 std::cout << "弹出的元素: " << stack.pop() << std::endl; // 输出: 30 std::cout << "栈大小: " << stack.size() << std::endl; // 输出: 2 std::cout << "栈是否为空: " << (stack.isEmpty() ? "是" : "否") << std::endl; // 输出: 否 return 0; }

优缺点

优点

  1. 实现简单:栈的概念和实现都很简单直观
  2. 操作高效:所有基本操作的时间复杂度都是O(1)
  3. 内存管理:对于某些语言,会用于管理内存和跟踪函数调用

缺点

  1. 访问限制:只能访问栈顶元素,无法直接访问中间元素
  2. 没有随机访问:获取中间元素需要先弹出上面所有元素
  3. 不适合频繁搜索:查找特定值的时间复杂度为O(n)

应用场景

  1. 函数调用和递归:存储函数调用的返回地址和局部变量
  2. 表达式求值:处理中缀、前缀和后缀表达式
  3. 撤销操作:实现程序中的撤销功能
  4. 浏览器历史:实现浏览器的"后退"功能
  5. 深度优先搜索(DFS):使用栈记录访问路径
  6. 内存分配:某些系统中使用栈来分配内存

扩展:单调栈

单调栈是特殊的栈结构,保持栈中元素单调递增或递减。当新元素破坏栈的单调性时,会弹出栈顶元素直到满足单调性。

示例

以数组 [3,6,4,6,9,2] 构建单调递增栈的过程:

  1. 初始栈为空 []
  2. 遇到3:入栈 → [3]
  3. 遇到6:大于栈顶,入栈 → [3,6]
  4. 遇到4:小于栈顶6,弹出6;4大于新栈顶3,入栈 → [3,4]
  5. 遇到6:大于栈顶,入栈 → [3,4,6]
  6. 遇到9:大于栈顶,入栈 → [3,4,6,9]
  7. 遇到2:小于栈顶,弹出9,6,4,3直至栈空;入栈 → [2]

测验

  1. 栈的主要特点是什么?
  2. 栈的push和pop操作的时间复杂度是多少?为什么?
  3. 栈和队列的主要区别是什么?
  4. 在Java中,Stack类继承自哪个类?这种设计有什么问题?

测验答案

  1. 栈的主要特点是后进先出(LIFO),即最后入栈的元素最先出栈。
  2. 都是O(1)。因为这些操作只在栈顶进行,不需要访问或移动其他元素。
  3. 栈遵循后进先出(LIFO)原则,而队列遵循先进先出(FIFO)原则。即,栈只允许在一端(栈顶)进行操作,而队列允许在一端(队尾)插入,另一端(队头)删除。
  4. 在Java中,Stack类继承自Vector类。Vector是一个列表实现,提供了随机访问等与栈原则不符的操作,破坏了栈的封装性。

相关的LeetCode热门题目

  1. 20. 有效的括号 - 使用栈判断括号是否有效匹配。
  2. 155. 最小栈 - 设计一个支持push、pop、top操作,并能在常数时间内检索到最小元素的栈。
  3. 232. 用栈实现队列 - 使用两个栈来实现队列的功能。
  4. 739. 每日温度 - 使用单调栈解决的经典问题。
  5. 84. 柱状图中最大的矩形 - 单调栈的高级应用。