跳转至

栈与队列

📖 章节简介

本章将介绍C++的栈和队列数据结构，包括栈的实现、队列的实现和循环队列。

栈与队列操作示意

上图直观展示了栈的 LIFO 与队列的 FIFO 行为，以及 push/pop、enqueue/dequeue 的操作方向。

📚 栈

1. 栈的实现

C++
// 栈的实现
#include <iostream>
#include <vector>
using namespace std;

class Stack {
private:
    vector<int> data;
    int top;

public:
    Stack(int size = 10) {
        data.resize(size);
        top = -1;
    }

    void push(int value) {
        if (top >= (int)data.size() - 1) {
            cout << "栈已满！" << endl;
            return;
        }
        data[++top] = value;
    }

    // ⚠️ 注意：空栈时返回 -1 作为哨兵值存在缺陷——当 -1 是合法数据时会产生歧义。
    // 更健壮的做法：抛出异常 (throw std::underflow_error("stack is empty"))
    // 或使用 std::optional<int> 作为返回类型（C++17）。
    int pop() {
        if (top < 0) {
            cout << "栈为空！" << endl;
            return -1;
        }
        return data[top--];
    }

    int peek() const {
        if (top < 0) {
            cout << "栈为空！" << endl;
            return -1;
        }
        return data[top];
    }

    bool isEmpty() const {
        return top == -1;
    }

    bool isFull() const {
        return top >= (int)data.size() - 1;
    }

    int size() const {
        return top + 1;
    }
};

int main() {
    Stack stack(5);

    // 入栈
    stack.push(10);
    stack.push(20);
    stack.push(30);

    cout << "栈大小: " << stack.size() << endl;

    // 查看栈顶元素
    cout << "栈顶元素: " << stack.peek() << endl;

    // 出栈
    while (!stack.isEmpty()) {
        cout << "出栈: " << stack.pop() << endl;
    }

    return 0;
}

2. 栈的应用

C++
// 栈的应用：括号匹配
#include <iostream>
#include <stack>
using namespace std;

// 括号匹配算法：左括号入栈，遇右括号时弹栈检查是否配对
bool isValidExpression(const string& expr) {
    stack<char> s;

    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c); // 左括号入栈
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) {
                return false; // 没有对应的左括号
            }

            char top = s.top();
            s.pop();

            // 检查左右括号是否匹配
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }

    return s.empty(); // 栈为空说明所有括号都已配对
}

int main() {
    string expr1 = "{[()()]}";
    string expr2 = "{[(])}";

    cout << "表达式1: " << expr1 << endl;
    cout << "是否有效: " << (isValidExpression(expr1) ? "是" : "否") << endl;

    cout << "\n表达式2: " << expr2 << endl;
    cout << "是否有效: " << (isValidExpression(expr2) ? "是" : "否") << endl;

    return 0;
}

📋 队列

1. 队列的实现

C++
// 队列的实现
#include <iostream>
#include <vector>
using namespace std;

class Queue {
private:
    vector<int> data;
    int front;
    int rear;
    int count;
    int maxSize;

public:
    Queue(int size = 10) {
        data.resize(size);
        front = 0;
        rear = -1;
        count = 0;
        maxSize = size;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "队列已满！" << endl;
            return;
        }

        rear = (rear + 1) % maxSize; // 取模实现环形回绕
        data[rear] = value;
        count++;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "队列为空！" << endl;
            return -1;
        }

        int value = data[front];
        front = (front + 1) % maxSize; // front也取模回绕
        count--;
        return value;
    }

    int peek() const {
        if (isEmpty()) {
            cout << "队列为空！" << endl;
            return -1;
        }
        return data[front];
    }

    bool isEmpty() const {
        return count == 0;
    }

    bool isFull() const {
        return count == maxSize;
    }

    int size() const {
        return count;
    }
};

int main() {
    Queue queue(5);

    // 入队
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    cout << "队列大小: " << queue.size() << endl;

    // 查看队首元素
    cout << "队首元素: " << queue.peek() << endl;

    // 出队
    while (!queue.isEmpty()) {
        cout << "出队: " << queue.dequeue() << endl;
    }

    return 0;
}

2. 队列的应用

C++
// 队列的应用：任务调度
#include <iostream>
#include <queue>
using namespace std;

struct Task {
    string name;
    int priority;

    Task(string n, int p) : name(n), priority(p) {}
};

class TaskScheduler {
private:
    queue<Task> tasks;

public:
    void addTask(const Task& task) {
        tasks.push(task);
        cout << "任务添加: " << task.name << endl;
    }

    Task getNextTask() {
        if (tasks.empty()) {
            cout << "没有待处理任务" << endl;
            return Task("", 0);
        }

        Task task = tasks.front();
        tasks.pop();
        return task;
    }

    bool hasTasks() const {
        return !tasks.empty();
    }

    int getTaskCount() const {
        return tasks.size();
    }
};

int main() {
    TaskScheduler scheduler;

    // 添加任务
    scheduler.addTask(Task("任务1", 1));
    scheduler.addTask(Task("任务2", 2));
    scheduler.addTask(Task("任务3", 3));

    cout << "任务总数: " << scheduler.getTaskCount() << endl;

    // 处理任务
    while (scheduler.hasTasks()) {
        Task task = scheduler.getNextTask();
        cout << "执行任务: " << task.name
             << ", 优先级: " << task.priority << endl;
    }

    return 0;
}

🔄 循环队列

1. 循环队列的实现

C++
// 循环队列
#include <iostream>
using namespace std;

// ⚠️ 注意：本类违反了「三/五法则（Rule of Three/Five）」！
// 类中有裸指针 data 和手动 delete[]，但未定义拷贝构造函数和拷贝赋值运算符。
// 若发生拷贝（如传值、赋值），两个对象会共享同一块内存，析构时会 double-free。
// 修复方案：① 删除拷贝操作（如下所示）；② 或正确实现深拷贝；③ 或改用 std::vector。
class CircularQueue {
private:
    int* data;
    int front;
    int rear;
    int count;
    int maxSize;

public:
    CircularQueue(const CircularQueue&) = delete;            // 禁止拷贝
    CircularQueue& operator=(const CircularQueue&) = delete; // 禁止拷贝赋值

    CircularQueue(int size) {
        maxSize = size;
        data = new int[maxSize];
        front = 0;
        rear = -1;
        count = 0;
    }

    ~CircularQueue() {
        delete[] data;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "队列已满！" << endl;
            return;
        }

        rear = (rear + 1) % maxSize; // 取模实现环形回绕，到达末尾后回到数组起点
        data[rear] = value;
        count++;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "队列为空！" << endl;
            return -1;
        }

        int value = data[front];
        front = (front + 1) % maxSize; // front同样取模回绕，保持环形结构
        count--;
        return value;
    }

    int peek() const {
        if (isEmpty()) {
            cout << "队列为空！" << endl;
            return -1;
        }
        return data[front];
    }

    bool isEmpty() const {
        return count == 0;
    }

    bool isFull() const {
        return count == maxSize;
    }

    int size() const {
        return count;
    }
};

int main() {
    CircularQueue queue(5);

    // 入队
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    queue.enqueue(40);
    queue.enqueue(50);

    cout << "队列大小: " << queue.size() << endl;

    // 出队
    queue.dequeue();
    queue.enqueue(60);  // 可以继续入队

    cout << "队列大小: " << queue.size() << endl;

    return 0;
}

💡 最佳实践

1. 内存管理

C++
// 内存管理
#include <iostream>
using namespace std;

int main() {
    // ✅ 好的做法：使用RAII
    class Resource {
    private:
        int* data;
    public:
        Resource(int size) {
            data = new int[size];
            cout << "资源分配" << endl;
        }
        ~Resource() {
            delete[] data;
            cout << "资源释放" << endl;
        }
    };

    {
        Resource res(100);
        // 自动释放
    }

    // ❌ 不好的做法：忘记释放内存
    int* ptr = new int[100];
    // delete[] ptr;  // 容易忘记

    return 0;
}

2. 异常处理

C++
// 异常处理
#include <iostream>
#include <new>
using namespace std;

int main() {
    // ✅ 好的做法：处理异常
    try {
        int* arr = new int[1000000000];
        delete[] arr;
    } catch (const bad_alloc& e) {
        cout << "内存分配失败" << endl;
    }

    // ❌ 不好的做法：不处理异常
    // int* arr = new int[1000000000];
    // delete[] arr;

    return 0;
}

📝 练习题

基础题

  1. 栈和队列有什么区别？
  2. 如何实现栈和队列？
  3. 栈和队列有哪些应用场景？

进阶题

  1. 实现循环队列。
  2. 使用栈实现表达式求值。
  3. 使用队列实现任务调度。

实践题

  1. 创建一个简单的浏览器历史记录。
  2. 实现一个打印队列系统。
  3. 构建一个任务调度器。

📚 推荐阅读

🔗 下一章

树 - 学习C++的树数据结构。