栈是一种遵循后进先出(LIFO)原则的线性数据结构。只允许在一端(栈顶)进行插入和删除操作。适用于需要回溯的问题解决过程。
栈是一种特殊的线性数据结构,遵循后进先出(Last-In-First-Out,LIFO)的原则。最后添加到栈中的元素将是第一个被移除的元素。可以将栈想象为一叠盘子,我们只能从顶部添加或移除盘子。

栈的操作仅限于栈顶,即只能在一端进行插入和删除操作。
▼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复制代码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复制代码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复制代码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复制代码#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++复制代码#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; }
单调栈是特殊的栈结构,保持栈中元素单调递增或递减。当新元素破坏栈的单调性时,会弹出栈顶元素直到满足单调性。
以数组 [3,6,4,6,9,2] 构建单调递增栈的过程:
测验答案
- 栈的主要特点是后进先出(LIFO),即最后入栈的元素最先出栈。
- 都是O(1)。因为这些操作只在栈顶进行,不需要访问或移动其他元素。
- 栈遵循后进先出(LIFO)原则,而队列遵循先进先出(FIFO)原则。即,栈只允许在一端(栈顶)进行操作,而队列允许在一端(队尾)插入,另一端(队头)删除。
- 在Java中,Stack类继承自Vector类。Vector是一个列表实现,提供了随机访问等与栈原则不符的操作,破坏了栈的封装性。