深入理解C++中的栈与队列：概念、底层机制与高效操作指南

suye

发布于 2024-10-16 09:53:59

1020

发布于 2024-10-16 09:53:59

文章被收录于专栏：17的博客分享

前言

在C++标准库中，stack（栈）和queue（队列）是两种重要的容器适配器，它们分别遵循后进先出（LIFO）和先进先出（FIFO）的操作原则。通过这些容器，我们可以高效地管理元素的插入、删除和访问，适用于多种实际编程场景。本文将详细介绍stack和queue的概念、底层实现、常用成员函数，以及它们在不同容器适配器中的应用，以帮助您深入理解并灵活运用这些数据结构。

🥦一、 stack的定义与基本概念

栈（Stack）是一种后进先出（LIFO - Last In, First Out）的数据结构。它类似于一叠盘子，最新放上去的盘子最先被拿走。栈的数据存取总是从同一端进行，这个端口被称为**栈顶（Top），而栈的另一端则称为栈底（Bottom）。

1.1 基本特性

后进先出 (LIFO)： 栈的主要特点是后进入的元素先出来。这意味着最新压入栈的数据会最先被弹出。
栈顶 (Top)： 栈中最后一个被压入的元素所在的位置称为栈顶，所有的插入和删除操作都在栈顶进行。
栈底 (Bottom)： 栈中最早被压入的元素位于栈底。栈底的元素一般是最早被压入栈但最晚被弹出的。

1.2 基本操作

栈有两个主要操作：

压栈 (Push)： 将一个元素加入到栈顶。
弹栈 (Pop)： 从栈顶移除一个元素。

除此之外，还有一些辅助操作，例如：

查看栈顶元素 (Peek 或 Top)： 返回栈顶元素，但不移除它。
判断栈是否为空 (isEmpty)： 检查栈是否为空。
查看栈的大小 (size)： 返回栈中元素的数量。

1.3 栈的应用场景

函数调用管理： 在程序运行时，函数调用的返回地址、局部变量等信息都被存储在栈中。
表达式求值与语法解析： 如中缀表达式转后缀表达式、括号匹配等都使用栈。
深度优先搜索 (DFS)： 许多图和树的遍历算法都使用栈来实现递归过程的显式管理。

1.4 栈的实现

栈可以用数组或链表实现：

数组实现： 栈用一个数组来存储数据，通常会有一个指针指向栈顶位置。
链表实现： 链表可以实现动态栈，节点之间有指针指向，从而在添加或删除元素时不需要重新分配大块内存。

1.5 举个例子

假设有一个栈 S，最初为空。我们进行如下操作：

push(5)：将元素 5 压入栈中。栈内容为 [5]。
push(10)：将元素 10 压入栈中。栈内容为 [5, 10]。
pop()：弹出栈顶元素 10。栈内容变为 [5]。
peek()：查看栈顶元素。结果是 5，但不移除它。

通过这些操作可以看出栈的“后进先出”特性。

图示

栈底 <- [5] <- 栈顶
栈底 <- [5, 10] <- 栈顶

pop() 操作后：

栈底 <- [5] <- 栈顶

栈是操作系统中非常重要的基础数据结构之一，它在管理内存、递归调用、表达式求解等方面有广泛应用。

🥦二、Stack底层容器

栈的底层容器可以通过不同的数据结构来实现，最常见的实现方式包括数组和链表。这两种实现方式各有优缺点，具体选择哪种取决于使用场景的需求，如存储效率、空间管理以及操作的复杂度。

2.1 数组实现栈

栈可以通过数组来实现，数组提供了一个连续的内存空间来存储元素，通过索引定位来实现操作。

数组实现的步骤

初始化数组：首先需要声明一个固定大小的数组，假设大小为 N。
指针管理栈顶：使用一个整数 top 指向当前栈顶元素的位置，初始时设置为 -1，表示栈为空。
压栈 (Push) 操作：将元素加入数组中，先将 top 增加 1，然后在对应的位置插入新元素。
弹栈 (Pop) 操作：将 top 所指向的元素移除，同时将 top 减少 1。
查看栈顶 (Peek) 操作：直接访问数组 top 指向的索引处的元素。

代码示例(C 风格)

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 压栈
void push(Stack* s, int value) {
    if (s->top < MAX_SIZE - 1) {
        s->data[++(s->top)] = value;
    } else {
        printf("栈溢出\n");
    }
}

// 弹栈
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return -1;  // 表示栈为空的情况
    } else {
        return s->data[(s->top)--];
    }
}

数组实现的优缺点

优点：
- 快速访问：数组实现的栈在访问元素时，时间复杂度为 O(1)，因为可以通过索引快速定位。
- 空间连续：数组内存是连续的，容易管理和访问。
缺点：
- 固定大小：必须事先定义数组大小，这可能导致内存浪费或栈溢出。
- 动态性差：如果元素数量超过了数组的大小，必须重新分配数组来扩容。

2.2 链表实现栈

栈也可以通过链表来实现，这种方式可以实现动态的栈，即栈的大小可以根据需求动态调整，不受固定大小的限制。

链表实现的步骤

节点结构：链表栈中的每一个节点包含一个数据域和一个指向下一个节点的指针。
栈顶管理：使用一个指针 top 来指向栈顶节点。
压栈 (Push) 操作：创建一个新节点，将新节点的 next 指向当前栈顶，然后将 top 更新为新节点。
弹栈 (Pop) 操作：将 top 节点移除，并将 top 更新为其 next 指针所指向的节点。
查看栈顶 (Peek) 操作：直接返回栈顶节点的数据值。

代码示例(C 风格)

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = NULL;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == NULL;
}

// 压栈
void push(Stack* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

// 弹栈
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return -1;  // 表示栈为空的情况
    } else {
        Node* temp = s->top;
        int value = temp->data;
        s->top = s->top->next;
        free(temp);
        return value;
    }
}

链表实现的优缺点

优点：
- 动态大小：可以根据需求动态增加或减少栈的大小，不需要预定义大小，避免内存浪费。
- 节省空间：不会因为固定的数组大小而浪费未使用的空间。
缺点：
- 额外的指针存储：每个节点都需要一个额外的指针来指向下一个节点，增加了存储开销。
- 访问速度较慢：由于链表中的节点在内存中不一定是连续的，访问栈顶元素比数组要慢一些。

总结

数组实现适用于需要快速访问和栈大小确定的场景。
链表实现适用于栈大小动态变化的场景，并且内存使用更加灵活，但会带来存储开销增加的缺点。

不同的实现方式针对的场景各不相同，选择合适的底层容器取决于应用程序的特定需求和使用模式。

🥦三、 Stack成员函数

在C++标准库中，stack（栈）是一个后进先出（LIFO, Last In First Out）的数据结构，栈的操作只能在顶端进行，元素的插入和删除都是从栈顶完成的。stack与queue一样，也是一个容器适配器，它的底层可以是deque（默认）、vector或list。

下面详细介绍stack的成员函数：

3.1 成员函数概览

成员函数	作用
push()	向栈的顶端添加元素
pop()	移除栈顶元素
top()	获取栈顶元素的引用
empty()	检查栈是否为空
size()	返回栈中的元素个数
构造函数	创建栈实例并初始化
析构函数	销毁栈实例并释放资源

3.2 常用成员函数详细解释

1. `push(const T& value)` / `push(T&& value)`

功能：将一个元素添加到栈的顶端。
用法：可以通过传递左值或右值，将元素插入栈顶。
复杂度：摊还常数时间复杂度。

std::stack<int> s;
s.push(10);  // 向栈顶添加元素10
s.push(20);  // 向栈顶添加元素20

2. `pop()`

功能：移除栈顶元素。
用法：删除栈顶元素，但并不返回该元素的值。如果需要使用栈顶元素的值，可以在调用pop()之前使用top()。
复杂度：常数时间复杂度。

s.pop();  // 移除栈顶元素20，栈顶现在是10

3. `top()`

功能：返回栈顶元素的引用。
用法：通过top()可以访问栈顶的元素，但不能移除元素。如果需要修改栈顶元素，可以通过top()的引用来实现。
复杂度：常数时间复杂度。
注意：在调用top()之前，确保栈不为空，否则行为未定义。

std::cout << "栈顶元素: " << s.top() << std::endl;  // 输出 10
s.top() = 30;  // 修改栈顶元素为30
std::cout << "修改后的栈顶元素: " << s.top() << std::endl;  // 输出 30

4. `empty()`

功能：检查栈是否为空。
返回值：如果栈为空，则返回true；否则返回false。
复杂度：常数时间复杂度。

if (s.empty()) {
    std::cout << "栈为空" << std::endl;
} else {
    std::cout << "栈不为空" << std::endl;  // 输出栈不为空
}

5. `size()`

功能：返回栈中元素的个数。
复杂度：常数时间复杂度。

std::cout << "栈的大小: " << s.size() << std::endl;  // 输出 1

3.3 构造函数与析构函数

3.3.1 构造函数

默认构造函数：创建一个空栈。
复制构造函数：可以通过另一个stack对象来初始化新的栈。

std::stack<int> s1;  // 默认构造函数，创建空栈
std::stack<int> s2(s1);  // 复制构造函数

3.3.2 析构函数

析构函数会在栈对象销毁时自动调用，释放栈中所有元素的资源。

3.4 栈的底层容器

stack是一个容器适配器，底层容器可以是deque（默认）、vector或list。可以在模板参数中指定不同的底层容器：

#include <iostream>
#include <stack>
#include <deque>
#include <list>

int main() {
    // 使用deque作为底层容器（默认）
    std::stack<int, std::deque<int>> stack1;

    // 使用list作为底层容器
    std::stack<int, std::list<int>> stack2;

    return 0;
}

3.5 示例代码

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 向栈中添加元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 输出栈顶元素
    std::cout << "栈顶元素: " << s.top() << std::endl;  // 输出 30

    // 修改栈顶元素
    s.top() = 100;
    std::cout << "修改后的栈顶元素: " << s.top() << std::endl;  // 输出 100

    // 移除栈顶元素
    s.pop();
    std::cout << "栈顶元素在pop后: " << s.top() << std::endl;  // 输出 20

    // 栈的大小
    std::cout << "栈的大小: " << s.size() << std::endl;  // 输出 2

    // 检查栈是否为空
    if (s.empty()) {
        std::cout << "栈为空" << std::endl;
    } else {
        std::cout << "栈不为空" << std::endl;  // 栈不为空
    }

    return 0;
}

🥦四、Queue的定义和使用

在C++中，queue（队列）是一种容器，遵循**先进先出（FIFO, First In First Out）**的原则。这意味着，第一个插入到队列中的元素将是第一个被移除的元素。队列是一种常用的数据结构，在很多应用场景中用于缓冲处理顺序性任务，比如任务调度、消息传递等。

C++中的queue是通过标准模板库（STL）提供的，可以通过包含<queue>头文件来使用。标准库中的queue是基于已有的容器（如deque或list）实现的封装。

在C++中，你可以通过以下方式定义一个队列：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;  // 定义一个存储int类型的队列

    // 添加元素到队列
    q.push(10);  // 10进入队列
    q.push(20);  // 20进入队列
    q.push(30);  // 30进入队列

    // 访问队首元素
    std::cout << "Queue front: " << q.front() << std::endl;  // 输出 10

    // 移除队首元素
    q.pop();  // 移除 10

    std::cout << "Queue front after pop: " << q.front() << std::endl;  // 输出 20

    return 0;
}

🥦五、Queue的底层容器

在C++标准库的queue和其他类似容器适配器中，底层容器的选择和实现是非常关键的，它影响了容器的性能和操作的特性。

5.1 什么是底层容器？

C++中的queue并不是一种独立的容器，它是容器适配器的一种。这意味着，queue不直接管理元素的存储，而是依赖于其他容器来完成实际的存储操作。queue提供了一个**先进先出（FIFO）**的操作接口，而将实际数据的管理交给它所适配的底层容器。

5.1.1 常见的底层容器

queue的底层容器可以是以下几种常见的标准容器：

deque（双端队列）：这是queue的默认底层容器。deque提供了双端插入和删除操作，适合在队列头部和尾部进行高效的操作。
list（链表）：可以自定义使用链表作为底层容器，链表在插入和删除元素时非常高效，尤其是在队列头部和尾部进行操作。
vector：虽然不常用，但理论上也可以作为底层容器，但vector在头部插入和删除时效率较低，因为这些操作需要移动大量的元素。

5.2 为什么使用不同的底层容器？

选择不同的底层容器主要是为了适应不同的需求场景。容器适配器（如queue）通过操作底层容器来实现功能，因此底层容器的性能特性会直接影响queue的整体性能和适用性。

5.2.1 `deque`（默认）

双端队列，允许在两端进行高效的插入和删除操作。相比vector，deque在队列头部删除元素时更加高效。
deque提供了随机访问的能力（但不如vector快），因此它可以在不牺牲太多性能的情况下满足队列的需求。
queue默认使用deque作为底层容器，因为它可以高效地在队列头部删除元素和在尾部插入元素。

5.2.2 `list`

list是双向链表，它的特点是可以在任意位置进行常数时间的插入和删除操作，特别适合队列这种频繁在头部和尾部进行插入删除操作的场景。
使用list作为底层容器时，虽然插入和删除性能好，但list不支持随机访问，所以相较于deque在访问元素时性能较差。

5.2.3 `vector`

虽然vector也可以作为底层容器，但由于vector在头部进行插入和删除操作需要移动大量元素，这种操作代价较高，因此它并不适合作为queue的底层容器。
vector的优势是它支持随机访问和连续的内存布局，但这些特性对queue的操作并不是必须的。

5.3 如何指定底层容器？

在C++中，我们可以通过模板参数来指定queue的底层容器。以下是使用不同容器作为queue底层容器的示例：

5.3.1 默认使用`deque`作为底层容器：

#include <iostream>
#include <queue>  // 包含queue头文件

int main() {
    std::queue<int> q;  // 默认使用std::deque作为底层容器

    q.push(10);  // 向队列中添加元素
    q.push(20);
    q.push(30);

    std::cout << "Front element: " << q.front() << std::endl;  // 输出 10
    q.pop();  // 移除队首元素
    std::cout << "Front element after pop: " << q.front() << std::endl;  // 输出 20

    return 0;
}

5.3.2 使用`list`作为底层容器：

#include <iostream>
#include <queue>
#include <list>  // 包含list头文件

int main() {
    std::queue<int, std::list<int>> q;  // 使用std::list作为底层容器

    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "Front element: " << q.front() << std::endl;  // 输出 10
    q.pop();
    std::cout << "Front element after pop: " << q.front() << std::endl;  // 输出 20

    return 0;
}

5.3.3 使用`vector`作为底层容器（尽管不推荐）：

#include <iostream>
#include <queue>
#include <vector>  // 包含vector头文件

int main() {
    std::queue<int, std::vector<int>> q;  // 使用std::vector作为底层容器

    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "Front element: " << q.front() << std::endl;  // 输出 10
    q.pop();
    std::cout << "Front element after pop: " << q.front() << std::endl;  // 输出 20

    return 0;
}

5.4 性能比较

deque：非常适合queue的操作模式，因为它允许在两端进行高效的插入和删除操作。随机访问性能尚可，内存布局较为灵活。
list：适合需要大量插入和删除操作的场景，但不支持随机访问。相比deque，其随机访问性能较差，但在频繁的插入删除场景中效率更高。
vector：虽然提供了快速的随机访问，但由于头部插入和删除操作开销较大，不适合作为queue的底层容器。

总结

**queue**是容器适配器，依赖于底层容器（如deque或list）来实现其功能。
**默认deque**作为底层容器，适合在两端高效进行插入和删除。
可以自定义使用list或vector作为底层容器，具体选择取决于使用场景的需求。

🥦六、Queue的成员函数

C++标准库中的queue容器适配器提供了一组用于操作队列的成员函数。这些成员函数允许我们向队列中添加、访问、删除元素，并检查队列的状态。下面是queue常用的成员函数以及它们的作用。

6.1 成员函数概览

成员函数	作用
push()	向队列的末尾添加元素
pop()	移除队列的队首元素
front()	获取队列的队首元素
back()	获取队列的队尾元素
empty()	检查队列是否为空
size()	返回队列中的元素个数
构造函数	创建队列实例并初始化
析构函数	销毁队列实例并释放资源

6.2 常用成员函数详细解释

1. `push(const T& value)` / `push(T&& value)`

功能：向队列末尾插入一个元素。
用法：可以传递左值或右值，依赖于传入的参数。
复杂度：摊还常数时间复杂度。

std::queue<int> q;
q.push(10);  // 插入元素10到队列末尾
q.push(20);  // 插入元素20到队列末尾

2. `pop()`

功能：移除队列中的第一个元素（队首元素）。
用法：不会返回被移除的元素，必须在调用pop()之前使用front()获取队首元素的值。
复杂度：常数时间复杂度。

q.pop();  // 移除队首元素10，队列现在为20

3. `front()`

功能：返回队列中的第一个元素（队首元素）的引用。
用法：可以通过该函数访问队首元素，但不能移除元素。
复杂度：常数时间复杂度。
注意：在调用front()之前，应该确保队列不为空，否则行为是未定义的。

std::cout << "队首元素: " << q.front() << std::endl;  // 输出队首元素20

4. `back()`

功能：返回队列中最后一个元素（队尾元素）的引用。
用法：可以通过该函数访问队尾元素。
复杂度：常数时间复杂度。

std::cout << "队尾元素: " << q.back() << std::endl;  // 输出队尾元素20

5. `empty()`

功能：检查队列是否为空。
返回值：如果队列为空，返回true，否则返回false。
复杂度：常数时间复杂度。

if (q.empty()) {
    std::cout << "队列为空" << std::endl;
} else {
    std::cout << "队列不为空" << std::endl;
}

6. `size()`

功能：返回队列中元素的数量。
复杂度：常数时间复杂度。

std::cout << "队列中元素个数: " << q.size() << std::endl;

6.3 构造函数与析构函数

6.3.1 构造函数

queue的构造函数可以通过不同方式初始化队列：
1. 默认构造函数：创建一个空队列。
2. 复制构造函数：可以通过另一个队列对象来初始化新队列。

std::queue<int> q1;  // 默认构造函数，创建空队列
std::queue<int> q2(q1);  // 使用复制构造函数

6.3.2 析构函数

当队列对象被销毁时，其析构函数会自动调用，释放队列中所有元素的资源。

6.4 示例代码

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 输出队列的队首和队尾元素
    std::cout << "队首元素: " << q.front() << std::endl;  // 输出 10
    std::cout << "队尾元素: " << q.back() << std::endl;    // 输出 30

    // 移除队首元素
    q.pop();
    std::cout << "队首元素在pop后: " << q.front() << std::endl;  // 输出 20

    // 队列大小
    std::cout << "队列大小: " << q.size() << std::endl;  // 输出 2

    // 检查队列是否为空
    if (q.empty()) {
        std::cout << "队列为空" << std::endl;
    } else {
        std::cout << "队列不为空" << std::endl;  // 队列不为空
    }

    return 0;
}

结语

通过对C++中stack与queue的解析，我们可以看到，这些容器适配器提供了简洁且高效的接口，帮助我们处理各种元素管理任务。理解底层容器的选择和操作的性能差异，能够让我们在实际应用中做出最佳的设计选择。无论是用在算法设计还是并发任务管理中，掌握这两种容器的使用将显著提升代码的灵活性与效率。

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-08，如有侵权请联系 cloudcommunity@tencent.com 删除

数组

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！