栈(Stack)
介绍
栈是一种特殊的线性数据结构，遵循后进先出（Last-In-First-Out，LIFO）的原则。最后添加到栈中的元素将是第一个被移除的元素。可以将栈想象为一叠盘子，我们只能从顶部添加或移除盘子。
栈的操作仅限于栈顶，即只能在一端进行插入和删除操作。
核心特性
后进先出(LIFO)：最后入栈的元素最先出栈
只允许在栈顶操作：只能在一端进行插入（压栈）和删除（弹栈）
快速访问栈顶元素：O(1)时间复杂度访问、添加和删除栈顶元素
元素访问受限：无法直接访问栈中间元素
基本操作
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
// 入栈
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
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
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
#include
#include
#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("栈已满，无法入栈
");
return;
}
stack->items[++stack->top] = item;
}
// 出栈
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("栈为空，无法出栈
");
return -1;
}
return stack->items[stack->top--];
}
// 查看栈顶元素
int peek(Stack *stack) {
if (isEmpty(stack)) {
printf("栈为空，无法查看栈顶
");
return -1;
}
return stack->items[stack->top];
}
int main() {
Stack stack;
initialize(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printf("栈顶元素: %d
", peek(&stack)); // 输出: 30
printf("弹出的元素: %d
", pop(&stack)); // 输出: 30
printf("栈大小: %d
", size(&stack)); // 输出: 2
printf("栈是否为空: %s
", isEmpty(&stack) ? "是" : "否"); // 输出: 否
return 0;
}
C++实现
使用STL的stack容器
▼C++复制代码#include
#include
int main() {
// 创建栈
std::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
#include
#include
template
class Stack {
private:
std::vector
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
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
#include
#define MAX_SIZE 100
template
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
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;
}
优缺点
优点
实现简单：栈的概念和实现都很简单直观
操作高效：所有基本操作的时间复杂度都是O(1)
内存管理：对于某些语言，会用于管理内存和跟踪函数调用
缺点
访问限制：只能访问栈顶元素，无法直接访问中间元素
没有随机访问：获取中间元素需要先弹出上面所有元素
不适合频繁搜索：查找特定值的时间复杂度为O(n)
应用场景
函数调用和递归：存储函数调用的返回地址和局部变量
表达式求值：处理中缀、前缀和后缀表达式
撤销操作：实现程序中的撤销功能
浏览器历史：实现浏览器的"后退"功能
深度优先搜索(DFS)：使用栈记录访问路径
内存分配：某些系统中使用栈来分配内存
扩展：单调栈
单调栈是特殊的栈结构，保持栈中元素单调递增或递减。当新元素破坏栈的单调性时，会弹出栈顶元素直到满足单调性。
示例
以数组 [3,6,4,6,9,2] 构建单调递增栈的过程：
初始栈为空 []
遇到3：入栈 → [3]
遇到6：大于栈顶，入栈 → [3,6]
遇到4：小于栈顶6，弹出6；4大于新栈顶3，入栈 → [3,4]
遇到6：大于栈顶，入栈 → [3,4,6]
遇到9：大于栈顶，入栈 → [3,4,6,9]
遇到2：小于栈顶，弹出9,6,4,3直至栈空；入栈 → [2]
测验
栈的主要特点是什么？
栈的push和pop操作的时间复杂度是多少？为什么？
栈和队列的主要区别是什么？
在Java中，Stack类继承自哪个类？这种设计有什么问题？
测验答案
栈的主要特点是后进先出(LIFO)，即最后入栈的元素最先出栈。
都是O(1)。因为这些操作只在栈顶进行，不需要访问或移动其他元素。
栈遵循后进先出(LIFO)原则，而队列遵循先进先出(FIFO)原则。即，栈只允许在一端（栈顶）进行操作，而队列允许在一端（队尾）插入，另一端（队头）删除。
在Java中，Stack类继承自Vector类。Vector是一个列表实现，提供了随机访问等与栈原则不符的操作，破坏了栈的封装性。
相关的LeetCode热门题目
20. 有效的括号 - 使用栈判断括号是否有效匹配。
155. 最小栈 - 设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈。
232. 用栈实现队列 - 使用两个栈来实现队列的功能。
739. 每日温度 - 使用单调栈解决的经典问题。
84. 柱状图中最大的矩形 - 单调栈的高级应用。