C++数据结构深入探究栈与队列

简介

栈和队列是常见的数据结构，尤其在程序设计和算法中都是不可或缺的。本文将深入讲解C++中栈和队列的实现原理和基本操作，并提供两个示例说明其应用。

栈(Stack)基本操作

栈的定义

栈是一种线性数据结构，具有后进先出(Last In First Out, LIFO)的特点。栈可以用数组或链表实现。

栈的操作

• push() 在栈顶插入元素
• pop() 弹出栈顶元素
• top() 返回栈顶元素
• empty() 判断栈是否为空
• size() 返回栈中元素个数

栈示例

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;
    s.push(1); // 在栈顶插入元素1
    s.push(2); // 在栈顶插入元素2
    s.push(3); // 在栈顶插入元素3

    cout << s.top() << endl; // 输出栈顶元素3
    s.pop(); // 弹出栈顶元素3

    cout << s.top() << endl; // 输出栈顶元素2

    return 0;
}

队列(Queue)基本操作

队列的定义

队列是一种线性数据结构，具有先进先出(First In First Out, FIFO)的特点。队列可以用数组或链表实现。

队列的操作

• push() 在队列尾部插入元素
• pop() 弹出队列头部元素
• front() 返回队列头部元素
• back() 返回队列尾部元素
• empty() 判断队列是否为空
• size() 返回队列中元素个数

队列示例

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;
    q.push(1); // 在队列尾部插入元素1
    q.push(2); // 在队列尾部插入元素2
    q.push(3); // 在队列尾部插入元素3

    cout << q.front() << endl; // 输出队列头部元素1
    q.pop(); // 弹出队列头部元素1

    cout << q.front() << endl; // 输出队列头部元素2

    return 0;
}

示例一：栈的应用

下面是一个计算后缀表达式的示例程序。后缀表达式是指运算符在后面的数学表达式，例如3 4 +表示3+4。

该程序使用栈来实现后缀表达式的计算，首先将后缀表达式转换成栈，然后依次取出并计算其中的元素，最终得到结果。

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

double evaluatePostfix(char* postfix) {
    stack<double> s;
    double result = 0;

    for(int i = 0; i < strlen(postfix); i++) {
        if(postfix[i] >= '0' && postfix[i] <= '9') {
            s.push(postfix[i] - '0');
        }
        else {
            double operand2 = s.top();
            s.pop();
            double operand1 = s.top();
            s.pop();

            switch(postfix[i]) {
                case '+':
                    result = operand1 + operand2;
                    break;

                case '-':
                    result = operand1 - operand2;
                    break;

                case '*':
                    result = operand1 * operand2;
                    break;

                case '/':
                    result = operand1 / operand2;
                    break;
            }

            s.push(result);
        }
    }

    return result;
}

int main() {
    char postfix[] = {'3', '4', '+', '5', '*'};
    cout << evaluatePostfix(postfix) << endl; // 输出27

    return 0;
}

示例二：队列的应用

下面是一个实现循环队列的示例程序。循环队列是指先进先出(FIFO)的数据结构，在头尾相连的环形数组中存储数据。

该程序使用数组实现循环队列，并演示了入队和出队操作的基本方法。

#include <iostream>
#include <queue>

using namespace std;

const int QUEUE_SIZE = 10;

void enqueue(int queue[], int& rear, int value) {
    if((rear + 1) % QUEUE_SIZE == 0) {
        cout << "队列已满" << endl;
    }
    else {
        rear = (rear + 1) % QUEUE_SIZE;
        queue[rear] = value;
    }
}

void dequeue(int queue[], int& front) {
    if(front == -1) {
        cout << "队列为空" << endl;
    }
    else {
        front = (front + 1) % QUEUE_SIZE;
    }
}

int main() {
    int queue[QUEUE_SIZE];
    int front = -1;
    int rear = -1;

    enqueue(queue, rear, 1);
    enqueue(queue, rear, 2);
    enqueue(queue, rear, 3);
    dequeue(queue, front);
    dequeue(queue, front);

    cout << queue[front] << endl; // 输出队列头部元素3

    return 0;
}