《栈与队列数据结构：核心原理与实战应用深度解析》

栈和队列作为基础而重要的线性数据结构，在计算机科学中有着广泛应用。它们虽然结构简单，但却是构建复杂系统的关键组件，理解其工作原理对算法设计和系统开发至关重要。

**栈的基本定义与实现**

栈遵循后进先出（LIFO）原则，其操作限定在栈顶进行：

```cpp

template<typename T>

class Stack {

private:

    vector<T> data;

    int topIndex;

    int capacity;

    

public:

    // 构造函数

    Stack(int size = 100) : capacity(size), topIndex(-1) {

        data.resize(capacity);

    }

    

    // 入栈操作

    void push(const T& element) {

        if (isFull()) {

            throw runtime_error("栈已满");

        }

        data[++topIndex] = element;

    }

    

    // 出栈操作

    T pop() {

        if (isEmpty()) {

            throw runtime_error("栈为空");

        }

        return data[topIndex--];

    }

    

    // 查看栈顶元素

    T peek() const {

        if (isEmpty()) {

            throw runtime_error("栈为空");

        }

        return data[topIndex];

    }

    

    // 判断栈是否为空

    bool isEmpty() const {

        return topIndex == -1;

    }

    

    // 判断栈是否已满

    bool isFull() const {

        return topIndex == capacity - 1;

    }

    

    // 获取栈大小

    int size() const {

        return topIndex + 1;

    }

    

    // 清空栈

    void clear() {

        topIndex = -1;

    }

};

```

**链式栈实现**

```cpp

template<typename T>

class LinkedStack {

private:

    struct Node {

        T data;

        Node* next;

        Node(const T& val) : data(val), next(nullptr) {}

    };

    

    Node* top;

    int stackSize;

    

public:

    LinkedStack() : top(nullptr), stackSize(0) {}

    

    ~LinkedStack() {

        clear();

    }

    

    // 入栈操作

    void push(const T& element) {

        Node* newNode = new Node(element);

        newNode->next = top;

        top = newNode;

        stackSize++;

    }

    

    // 出栈操作

    T pop() {

        if (isEmpty()) {

            throw runtime_error("栈为空");

        }

        

        Node* temp = top;

        T value = temp->data;

        top = top->next;

        delete temp;

        stackSize--;

        

        return value;

    }

    

    // 查看栈顶元素

    T peek() const {

        if (isEmpty()) {

            throw runtime_error("栈为空");

        }

        return top->data;

    }

    

    bool isEmpty() const {

        return top == nullptr;

    }

    

    int size() const {

        return stackSize;

    }

    

    void clear() {

        while (!isEmpty()) {

            pop();

        }

    }

};

```

**队列的基本定义与实现**

队列遵循先进先出（FIFO）原则：

```cpp

template<typename T>

class ArrayQueue {

private:

    vector<T> data;

    int frontIndex;

    int rearIndex;

    int queueSize;

    int capacity;

    

public:

    ArrayQueue(int size = 100) : capacity(size), frontIndex(0), 

                                rearIndex(-1), queueSize(0) {

        data.resize(capacity);

    }

    

    // 入队操作

    void enqueue(const T& element) {

        if (isFull()) {

            throw runtime_error("队列已满");

        }

        

        rearIndex = (rearIndex + 1) % capacity;

        data[rearIndex] = element;

        queueSize++;

    }

    

    // 出队操作

    T dequeue() {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        

        T value = data[frontIndex];

        frontIndex = (frontIndex + 1) % capacity;

        queueSize--;

        

        return value;

    }

    

    // 查看队首元素

    T front() const {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        return data[frontIndex];

    }

    

    // 查看队尾元素

    T rear() const {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        return data[rearIndex];

    }

    

    bool isEmpty() const {

        return queueSize == 0;

    }

    

    bool isFull() const {

        return queueSize == capacity;

    }

    

    int size() const {

        return queueSize;

    }

    

    void clear() {

        frontIndex = 0;

        rearIndex = -1;

        queueSize = 0;

    }

};

```

**链式队列实现**

```cpp

template<typename T>

class LinkedQueue {

private:

    struct Node {

        T data;

        Node* next;

        Node(const T& val) : data(val), next(nullptr) {}

    };

    

    Node* frontPtr;

    Node* rearPtr;

    int queueSize;

    

public:

    LinkedQueue() : frontPtr(nullptr), rearPtr(nullptr), queueSize(0) {}

    

    ~LinkedQueue() {

        clear();

    }

    

    // 入队操作

    void enqueue(const T& element) {

        Node* newNode = new Node(element);

        

        if (isEmpty()) {

            frontPtr = rearPtr = newNode;

        } else {

            rearPtr->next = newNode;

            rearPtr = newNode;

        }

        queueSize++;

    }

    

    // 出队操作

    T dequeue() {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        

        Node* temp = frontPtr;

        T value = temp->data;

        frontPtr = frontPtr->next;

        

        if (frontPtr == nullptr) {

            rearPtr = nullptr;

        }

        

        delete temp;

        queueSize--;

        return value;

    }

    

    // 查看队首元素

    T front() const {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        return frontPtr->data;

    }

    

    // 查看队尾元素

    T rear() const {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        return rearPtr->data;

    }

    

    bool isEmpty() const {

        return frontPtr == nullptr;

    }

    

    int size() const {

        return queueSize;

    }

    

    void clear() {

        while (!isEmpty()) {

            dequeue();

        }

    }

};

```

**栈的经典应用**

1. **表达式求值**

```cpp

class ExpressionEvaluator {

public:

    double evaluateInfix(const string& expression) {

        stack<double> operands;

        stack<char> operators;

        

        for (int i = 0; i < expression.length(); i++) {

            char ch = expression[i];

            

            if (ch == ' ') continue;

            

            if (isdigit(ch) || ch == '.') {

                string numStr;

                while (i < expression.length() && 

                       (isdigit(expression[i]) || expression[i] == '.')) {

                    numStr += expression[i++];

                }

                i--;

                operands.push(stod(numStr));

            }

            else if (ch == '(') {

                operators.push(ch);

            }

            else if (ch == ')') {

                while (!operators.empty() && operators.top() != '(') {

                    applyOperator(operands, operators.top());

                    operators.pop();

                }

                operators.pop(); // 弹出 '('

            }

            else if (isOperator(ch)) {

                while (!operators.empty() && 

                       precedence(operators.top()) >= precedence(ch)) {

                    applyOperator(operands, operators.top());

                    operators.pop();

                }

                operators.push(ch);

            }

        }

        

        while (!operators.empty()) {

            applyOperator(operands, operators.top());

            operators.pop();

        }

        

        return operands.top();

    }

    

private:

    bool isOperator(char ch) {

        return ch == '+' || ch == '-' || ch == '*' || ch == '/';

    }

    

    int precedence(char op) {

        if (op == '+' || op == '-') return 1;

        if (op == '*' || op == '/') return 2;

        return 0;

    }

    

    void applyOperator(stack<double>& operands, char op) {

        if (operands.size() < 2) {

            throw runtime_error("表达式错误");

        }

        

        double b = operands.top(); operands.pop();

        double a = operands.top(); operands.pop();

        double result;

        

        switch (op) {

            case '+': result = a + b; break;

            case '-': result = a - b; break;

            case '*': result = a * b; break;

            case '/': 

                if (b == 0) throw runtime_error("除零错误");

                result = a / b; 

                break;

            default: throw runtime_error("未知操作符");

        }

        

        operands.push(result);

    }

};

```

2. **括号匹配检查**

```cpp

class BracketChecker {

public:

    bool isValid(const string& s) {

<"f5.j9k5.org.cn"><"z1.j9k5.org.cn"><"j8.j9k5.org.cn">

        stack<char> stk;

        unordered_map<char, char> pairs = {

            {')', '('},

            {']', '['},

            {'}', '{'}

        };

        

        for (char ch : s) {

            if (ch == '(' || ch == '[' || ch == '{') {

                stk.push(ch);

            }

            else if (ch == ')' || ch == ']' || ch == '}') {

                if (stk.empty() || stk.top() != pairs[ch]) {

                    return false;

                }

                stk.pop();

            }

        }

        

        return stk.empty();

    }

    

    // 增强版：输出错误位置

    pair<bool, int> checkWithPosition(const string& s) {

        stack<pair<char, int>> stk; // 存储字符和位置

        

        for (int i = 0; i < s.length(); i++) {

            char ch = s[i];

            

            if (ch == '(' || ch == '[' || ch == '{') {

                stk.push({ch, i});

            }

            else if (ch == ')' || ch == ']' || ch == '}') {

                if (stk.empty()) {

                    return {false, i};

                }

                

                char expected;

                switch (ch) {

                    case ')': expected = '('; break;

                    case ']': expected = '['; break;

                    case '}': expected = '{'; break;

                }

                

                if (stk.top().first != expected) {

                    return {false, i};

                }

                stk.pop();

            }

        }

        

        if (!stk.empty()) {

            return {false, stk.top().second};

        }

        

        return {true, -1};

    }

};

```

**队列的经典应用**

1. **广度优先搜索**

```cpp

class GraphBFS {

private:

    vector<vector<int>> adjacencyList;

    

public:

    GraphBFS(int vertices) {

        adjacencyList.resize(vertices);

    }

    

    void addEdge(int u, int v) {

        adjacencyList[u].push_back(v);

        adjacencyList[v].push_back(u); // 无向图

    }

    

    vector<int> bfs(int start) {

        vector<int> result;

        vector<bool> visited(adjacencyList.size(), false);

        queue<int> q;

        

        q.push(start);

        visited[start] = true;

        

        while (!q.empty()) {

            int current = q.front();

            q.pop();

            result.push_back(current);

            

            for (int neighbor : adjacencyList[current]) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    q.push(neighbor);

                }

            }

        }

        

        return result;

    }

    

    // 计算最短路径（无权图）

    vector<int> shortestPath(int start, int end) {

        if (start == end) return {start};

        

        vector<bool> visited(adjacencyList.size(), false);

        vector<int> parent(adjacencyList.size(), -1);

        queue<int> q;

        

        q.push(start);

        visited[start] = true;

        

        while (!q.empty()) {

            int current = q.front();

            q.pop();

            

            if (current == end) break;

            

            for (int neighbor : adjacencyList[current]) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    parent[neighbor] = current;

                    q.push(neighbor);

                }

            }

        }

        

        // 重构路径

        if (parent[end] == -1) return {}; // 无路径

        

        vector<int> path;

        for (int v = end; v != -1; v = parent[v]) {

            path.push_back(v);

        }

        reverse(path.begin(), path.end());

        

        return path;

    }

};

```

2. **循环队列实现**

```cpp

template<typename T>

class CircularQueue {

private:

    vector<T> data;

    int front;

    int rear;

    int count;

    int capacity;

    

public:

    CircularQueue(int size) : capacity(size), front(0), rear(0), count(0) {

        data.resize(capacity);

    }

    

    bool enqueue(const T& item) {

        if (isFull()) return false;

        

        data[rear] = item;

        rear = (rear + 1) % capacity;

        count++;

        return true;

    }

    

    bool dequeue(T& item) {

        if (isEmpty()) return false;

        

        item = data[front];

        front = (front + 1) % capacity;

        count--;

        return true;

    }

    

    T peekFront() const {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        return data[front];

    }

    

    T peekRear() const {

        if (isEmpty()) {

            throw runtime_error("队列为空");

        }

        int lastIndex = (rear - 1 + capacity) % capacity;

        return data[lastIndex];

    }

    

    bool isEmpty() const {

        return count == 0;

    }

    

    bool isFull() const {

        return count == capacity;

    }

    

    int size() const {

        return count;

    }

    

    void clear() {

        front = rear = count = 0;

    }

    

    void display() const {

        cout << "队列内容: ";

        if (isEmpty()) {

            cout << "空" << endl;

            return;

        }

        

        int current = front;

        for (int i = 0; i < count; i++) {

            cout << data[current] << " ";

            current = (current + 1) % capacity;

        }

        cout << endl;

    }

};

```

**双端队列实现**

```cpp

template<typename T>

class Deque {

private:

    struct Node {

        T data;

        Node* prev;

        Node* next;

        Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}

    };

    

    Node* front;

    Node* rear;

    int dequeSize;

    

public:

    Deque() : front(nullptr), rear(nullptr), dequeSize(0) {}

    

    ~Deque() {

        clear();

    }

    

    // 前端插入

    void pushFront(const T& element) {

        Node* newNode = new Node(element);

        

        if (isEmpty()) {

            front = rear = newNode;

        } else {

            newNode->next = front;

            front->prev = newNode;

            front = newNode;

        }

        dequeSize++;

    }

    

    // 后端插入

    void pushRear(const T& element) {

        Node* newNode = new Node(element);

        

        if (isEmpty()) {

            front = rear = newNode;

        } else {

            newNode->prev = rear;

            rear->next = newNode;

            rear = newNode;

        }

        dequeSize++;

    }

    

    // 前端删除

    T popFront() {

        if (isEmpty()) {

            throw runtime_error("双端队列为空");

        }

        

        Node* temp = front;

        T value = temp->data;

        

        if (front == rear) { // 只有一个元素

            front = rear = nullptr;

        } else {

            front = front->next;

            front->prev = nullptr;

        }

        

        delete temp;

        dequeSize--;

        return value;

    }

    

    // 后端删除

    T popRear() {

        if (isEmpty()) {

            throw runtime_error("双端队列为空");

        }

        

        Node* temp = rear;

        T value = temp->data;

        

        if (front == rear) {

            front = rear = nullptr;

        } else {

            rear = rear->prev;

            rear->next = nullptr;

        }

        

        delete temp;

        dequeSize--;

        return value;

    }

    

    // 获取前端元素

    T getFront() const {

        if (isEmpty()) {

            throw runtime_error("双端队列为空");

        }

        return front->data;

    }

    

    // 获取后端元素

    T getRear() const {

        if (isEmpty()) {

            throw runtime_error("双端队列为空");

        }

        return rear->data;

    }

    

    bool isEmpty() const {

        return dequeSize == 0;

    }

    

    int size() const {

        return dequeSize;

    }

    

    void clear() {

        while (!isEmpty()) {

            popFront();

        }

    }

    

    // 从前向后遍历

    void traverseForward() const {

        Node* current = front;

        while (current) {

            cout << current->data << " ";

            current = current->next;

        }

        cout << endl;

    }

    

    // 从后向前遍历

    void traverseBackward() const {

        Node* current = rear;

        while (current) {

            cout << current->data << " ";

            current = current->prev;

        }

        cout << endl;

    }

};

```

**优先级队列实现**

```cpp

template<typename T>

<"n0.j9k5.org.cn"><"w4.j9k5.org.cn">

class PriorityQueue {

private:

    vector<pair<T, int>> heap; // (元素, 优先级)

    

    void heapifyUp(int index) {

        while (index > 0) {

            int parent = (index - 1) / 2;

            if (heap[parent].second >= heap[index].second) break;

            

            swap(heap[parent], heap[index]);

            index = parent;

        }

    }

    

    void heapifyDown(int index) {

        int size = heap.size();

        while (true) {

            int left = 2 * index + 1;

            int right = 2 * index + 2;

            int largest = index;

            

            if (left < size && heap[left].second > heap[largest].second) {

                largest = left;

            }

            

            if (right < size && heap[right].second > heap[largest].second) {

                largest = right;

            }

            

            if (largest == index) break;

            

            swap(heap[index], heap[largest]);

            index = largest;

        }

    }

    

public:

    void enqueue(const T& element, int priority) {

        heap.emplace_back(element, priority);

        heapifyUp(heap.size() - 1);

    }

    

    T dequeue() {

        if (isEmpty()) {

            throw runtime_error("优先级队列为空");

        }

        

        T result = heap[0].first;

        heap[0] = heap.back();

        heap.pop_back();

        

        if (!heap.empty()) {

            heapifyDown(0);

        }

        

        return result;

    }

    

    T peek() const {

        if (isEmpty()) {

            throw runtime_error("优先级队列为空");

        }

        return heap[0].first;

    }

    

    bool isEmpty() const {

        return heap.empty();

    }

    

    int size() const {

        return heap.size();

    }

    

    void clear() {

        heap.clear();

    }

    

    // 更新元素优先级

    bool updatePriority(const T& element, int newPriority) {

        for (int i = 0; i < heap.size(); i++) {

            if (heap[i].first == element) {

                int oldPriority = heap[i].second;

                heap[i].second = newPriority;

                

                if (newPriority > oldPriority) {

                    heapifyUp(i);

                } else {

                    heapifyDown(i);

                }

                return true;

            }

        }

        return false;

    }

};

```

**栈与队列实战应用**

1. **浏览器历史记录**

```cpp

class BrowserHistory {

private:

    stack<string> backStack;

    stack<string> forwardStack;

    string currentUrl;

    

public:

    BrowserHistory(const string& homepage) {

        currentUrl = homepage;

        backStack.push(homepage);

    }

    

    void visit(const string& url) {

        backStack.push(currentUrl);

        currentUrl = url;

        

        // 清空前向历史记录

        while (!forwardStack.empty()) {

            forwardStack.pop();

        }

    }

    

    string back(int steps) {

        while (steps > 0 && backStack.size() > 1) {

            forwardStack.push(currentUrl);

            currentUrl = backStack.top();

            backStack.pop();

            steps--;

        }

        return currentUrl;

    }

    

    string forward(int steps) {

        while (steps > 0 && !forwardStack.empty()) {

<"g6.j9k5.org.cn"><"q3.j9k5.org.cn"><"t7.j9k5.org.cn">

            backStack.push(currentUrl);

            currentUrl = forwardStack.top();

            forwardStack.pop();

            steps--;

        }

        return currentUrl;

    }

    

    vector<string> getHistory() const {

        vector<string> history;

        stack<string> temp = backStack;

        stack<string> reverseStack;

        

        while (!temp.empty()) {

            reverseStack.push(temp.top());

            temp.pop();

        }

        

        while (!reverseStack.empty()) {

            history.push_back(reverseStack.top());

            reverseStack.pop();

        }

        

        history.push_back(currentUrl);

        

        return history;

    }

};

```

2. **任务调度系统**

```cpp

class TaskScheduler {

private:

    struct Task {

        int id;

        string name;

        int priority; // 0: 最高优先级

        time_t arrivalTime;

        

        bool operator<(const Task& other) const {

            if (priority != other.priority) {

                return priority > other.priority; // 值越小优先级越高

            }

            return arrivalTime > other.arrivalTime; // 先到达的优先

        }

    };

    

    PriorityQueue<Task> taskQueue;

    int nextTaskId;

    

public:

    TaskScheduler() : nextTaskId(1) {}

    

    void addTask(const string& name, int priority) {

        Task task{nextTaskId++, name, priority, time(nullptr)};

        taskQueue.enqueue(task, -priority); // 负号使优先级值小的先出队

    }

    

    Task executeNextTask() {

        if (taskQueue.isEmpty()) {

            throw runtime_error("没有待执行任务");

        }

        return taskQueue.dequeue();

    }

    

    void displayTasks() const {

        cout << "待执行任务列表:" << endl;

        cout << "ID\t名称\t优先级" << endl;

        

        // 注意：这里需要复制队列来遍历

        // 实际实现中可能需要维护额外的列表

    }

    

    int pendingTasks() const {

        return taskQueue.size();

    }

};

```

**性能分析与优化**

```cpp

class PerformanceBenchmark {

public:

    static void benchmarkStack(int operations) {

        cout << "栈性能测试 (" << operations << " 次操作)" << endl;

        cout << "=" << 40 << endl;

        

        // 数组栈测试

        auto start = chrono::high_resolution_clock::now();

        Stack<int> arrayStack(operations + 10);

        

        for (int i = 0; i < operations; i++) {

            arrayStack.push(i);

        }

        

        for (int i = 0; i < operations; i++) {

            arrayStack.pop();

        }

        

        auto end = chrono::high_resolution_clock::now();

        auto arrayTime = chrono::duration_cast<chrono::milliseconds>(end - start);

        

        // 链式栈测试

        start = chrono::high_resolution_clock::now();

        LinkedStack<int> linkedStack;

        

        for (int i = 0; i < operations; i++) {

            linkedStack.push(i);

        }

        

        for (int i = 0; i < operations; i++) {

            linkedStack.pop();

        }

        

        end = chrono::high_resolution_clock::now();

        auto linkedTime = chrono::duration_cast<chrono::milliseconds>(end - start);

        

        cout << "数组栈: " << arrayTime.count() << "ms" << endl;

        cout << "链式栈: " << linkedTime.count() << "ms" << endl;

    }

    

    static void benchmarkQueue(int operations) {

        cout << "\n队列性能测试 (" << operations << " 次操作)" << endl;

        cout << "=" << 40 << endl;

        

        // 循环队列测试

        auto start = chrono::high_resolution_clock::now();

        CircularQueue<int> circularQueue(operations + 10);

        

        for (int i = 0; i < operations; i++) {

            circularQueue.enqueue(i);

        }

        

        int value;

        for (int i = 0; i < operations; i++) {

            circularQueue.dequeue(value);

        }

        

        auto end = chrono::high_resolution_clock::now();

        auto circularTime = chrono::duration_cast<chrono::milliseconds>(end - start);

        

        // 链式队列测试

        start = chrono::high_resolution_clock::now();

        LinkedQueue<int> linkedQueue;

        

        for (int i = 0; i < operations; i++) {

            linkedQueue.enqueue(i);

        }

        

        for (int i = 0; i < operations; i++) {

            linkedQueue.dequeue();

        }

        

        end = chrono::high_resolution_clock::now();

        auto linkedTime = chrono::duration_cast<chrono::milliseconds>(end - start);

        

        cout << "循环队列: " << circularTime.count() << "ms" << endl;

        cout << "链式队列: " << linkedTime.count() << "ms" << endl;

    }

};

```

**总结与最佳实践**

栈和队列的选择与应用建议：

1. **选择原则**：

   - 需要LIFO行为时选择栈（如函数调用、撤销操作）

   - 需要FIFO行为时选择队列（如任务调度、消息传递）

   - 数据量固定且已知时使用数组实现

   - 数据量动态变化时使用链式实现

2. **性能考虑**：

   - 数组实现缓存友好，访问速度快

   - 链式实现动态性好，无容量限制

   - 循环队列减少内存浪费

3. **实战建议**：

   - 栈适合解决递归问题、括号匹配、表达式求值

   - 队列适合解决BFS、缓存系统、任务调度

   - 双端队列提供更大灵活性

   - 优先级队列处理带优先级的任务

4. **常见错误避免**：

   - 栈溢出（递归过深或数组越界）

   - 队列空时执行出队操作

   - 忘记处理边界条件

   - 内存泄漏（链式实现）

理解栈和队列的核心原理并掌握其实现方法，能够帮助开发者在面对不同问题时选择合适的数据结构。这两种基础结构虽然简单，但正确使用能够显著提升算法的效率和系统的可靠性。