L6_06 栈和队列

一、栈

1.1 栈的定义

栈（Stack）是一种后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作。

1.2 栈的基本操作

• push：入栈，在栈顶添加元素
• pop：出栈，移除栈顶元素
• top：获取栈顶元素
• empty：判断栈是否为空
• size：获取栈的大小

1.3 栈的数组实现

template <typename T>
class Stack {
private:
    T* arr;
    int capacity;
    int topIndex;
    
public:
    Stack(int cap = 10) : capacity(cap), topIndex(-1) {
        arr = new T[capacity];
    }
    
    ~Stack() { delete[] arr; }
    
    void push(T val) {
        if (topIndex >= capacity - 1) {
            // 扩容
            T* newArr = new T[capacity * 2];
            for (int i = 0; i <= topIndex; i++) {
                newArr[i] = arr[i];
            }
            delete[] arr;
            arr = newArr;
            capacity *= 2;
        }
        arr[++topIndex] = val;
    }
    
    void pop() {
        if (!empty()) topIndex--;
    }
    
    T top() const {
        return arr[topIndex];
    }
    
    bool empty() const {
        return topIndex == -1;
    }
    
    int size() const {
        return topIndex + 1;
    }
};

1.4 栈的应用

1.4.1 括号匹配

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}

1.4.2 逆波兰表达式求值

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (string token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoi(token));
        }
    }
    return st.top();
}

二、队列

2.1 队列的定义

队列（Queue）是一种先进先出（FIFO）的数据结构，元素从队尾入队，从队头出队。

2.2 队列的基本操作

• push：入队，在队尾添加元素
• pop：出队，移除队头元素
• front：获取队头元素
• back：获取队尾元素
• empty：判断队列是否为空
• size：获取队列大小

2.3 队列的数组实现

template <typename T>
class Queue {
private:
    T* arr;
    int capacity;
    int frontIndex;
    int backIndex;
    
public:
    Queue(int cap = 10) : capacity(cap), frontIndex(0), backIndex(-1) {
        arr = new T[capacity];
    }
    
    ~Queue() { delete[] arr; }
    
    void push(T val) {
        if (backIndex >= capacity - 1) {
            T* newArr = new T[capacity * 2];
            int j = 0;
            for (int i = frontIndex; i <= backIndex; i++) {
                newArr[j++] = arr[i];
            }
            delete[] arr;
            arr = newArr;
            backIndex = j - 1;
            frontIndex = 0;
            capacity *= 2;
        }
        arr[++backIndex] = val;
    }
    
    void pop() {
        if (!empty()) frontIndex++;
    }
    
    T front() const {
        return arr[frontIndex];
    }
    
    T back() const {
        return arr[backIndex];
    }
    
    bool empty() const {
        return frontIndex > backIndex;
    }
    
    int size() const {
        return backIndex - frontIndex + 1;
    }
};

2.4 队列的应用

2.4.1 滑动窗口最大值

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;
    
    for (int i = 0; i < nums.size(); i++) {
        // 移除超出窗口的元素
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        
        // 移除比当前元素小的元素
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 窗口形成后开始记录结果
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

三、循环队列

3.1 循环队列的定义

循环队列（Circular Queue）是一种特殊的队列，首尾相连形成一个环。

3.2 循环队列的特点

• 利用取模运算实现循环
• 队满和队空需要特殊判断
• 空间利用率高

3.3 循环队列的实现

template <typename T>
class CircularQueue {
private:
    T* arr;
    int capacity;
    int frontIndex;
    int rearIndex;
    int count;
    
public:
    CircularQueue(int cap) : capacity(cap), frontIndex(0), rearIndex(0), count(0) {
        arr = new T[capacity];
    }
    
    ~CircularQueue() { delete[] arr; }
    
    bool enqueue(T val) {
        if (isFull()) return false;
        arr[rearIndex] = val;
        rearIndex = (rearIndex + 1) % capacity;
        count++;
        return true;
    }
    
    bool dequeue() {
        if (isEmpty()) return false;
        frontIndex = (frontIndex + 1) % capacity;
        count--;
        return true;
    }
    
    T front() const {
        return arr[frontIndex];
    }
    
    T rear() const {
        int idx = (rearIndex - 1 + capacity) % capacity;
        return arr[idx];
    }
    
    bool isEmpty() const {
        return count == 0;
    }
    
    bool isFull() const {
        return count == capacity;
    }
    
    int size() const {
        return count;
    }
};

四、栈和队列的对比

特性	栈	队列
顺序	LIFO（后进先出）	FIFO（先进先出）
操作端	一端（栈顶）	两端（队头/队尾）
主要操作	push, pop, top	push, pop, front, back
应用	括号匹配、表达式求值	任务排队、BFS
底层实现	数组或链表	数组或链表