在C++标准库中,stack
(栈)和queue
(队列)是两种重要的容器适配器,它们分别遵循后进先出(LIFO)和先进先出(FIFO)的操作原则。通过这些容器,我们可以高效地管理元素的插入、删除和访问,适用于多种实际编程场景。本文将详细介绍stack
和queue
的概念、底层实现、常用成员函数,以及它们在不同容器适配器中的应用,以帮助您深入理解并灵活运用这些数据结构。
栈(Stack)是一种后进先出(LIFO - Last In, First Out)的数据结构。它类似于一叠盘子,最新放上去的盘子最先被拿走。栈的数据存取总是从同一端进行,这个端口被称为**栈顶(Top),而栈的另一端则称为栈底(Bottom)。
栈有两个主要操作:
除此之外,还有一些辅助操作,例如:
栈可以用数组或链表实现:
假设有一个栈 S
,最初为空。我们进行如下操作:
push(5)
:将元素 5 压入栈中。栈内容为 [5]
。push(10)
:将元素 10 压入栈中。栈内容为 [5, 10]
。pop()
:弹出栈顶元素 10。栈内容变为 [5]
。peek()
:查看栈顶元素。结果是 5
,但不移除它。通过这些操作可以看出栈的“后进先出”特性。
图示
栈底 <- [5] <- 栈顶
栈底 <- [5, 10] <- 栈顶
pop()
操作后:
栈底 <- [5] <- 栈顶
栈是操作系统中非常重要的基础数据结构之一,它在管理内存、递归调用、表达式求解等方面有广泛应用。
栈的底层容器可以通过不同的数据结构来实现,最常见的实现方式包括数组和链表。这两种实现方式各有优缺点,具体选择哪种取决于使用场景的需求,如存储效率、空间管理以及操作的复杂度。
栈可以通过数组来实现,数组提供了一个连续的内存空间来存储元素,通过索引定位来实现操作。
数组实现的步骤
N
。top
指向当前栈顶元素的位置,初始时设置为 -1
,表示栈为空。top
增加 1,然后在对应的位置插入新元素。top
所指向的元素移除,同时将 top
减少 1。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)
,因为可以通过索引快速定位。栈也可以通过链表来实现,这种方式可以实现动态的栈,即栈的大小可以根据需求动态调整,不受固定大小的限制。
链表实现的步骤
top
来指向栈顶节点。next
指向当前栈顶,然后将 top
更新为新节点。top
节点移除,并将 top
更新为其 next
指针所指向的节点。代码示例(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;
}
}
链表实现的优缺点
不同的实现方式针对的场景各不相同,选择合适的底层容器取决于应用程序的特定需求和使用模式。
在C++标准库中,stack
(栈)是一个后进先出(LIFO, Last In First Out)的数据结构,栈的操作只能在顶端进行,元素的插入和删除都是从栈顶完成的。stack
与queue
一样,也是一个容器适配器,它的底层可以是deque
(默认)、vector
或list
。
下面详细介绍stack
的成员函数:
成员函数 | 作用 |
---|---|
push() | 向栈的顶端添加元素 |
pop() | 移除栈顶元素 |
top() | 获取栈顶元素的引用 |
empty() | 检查栈是否为空 |
size() | 返回栈中的元素个数 |
构造函数 | 创建栈实例并初始化 |
析构函数 | 销毁栈实例并释放资源 |
push(const T& value)
/ push(T&& value)
std::stack<int> s;
s.push(10); // 向栈顶添加元素10
s.push(20); // 向栈顶添加元素20
pop()
pop()
之前使用top()
。s.pop(); // 移除栈顶元素20,栈顶现在是10
top()
top()
可以访问栈顶的元素,但不能移除元素。如果需要修改栈顶元素,可以通过top()
的引用来实现。top()
之前,确保栈不为空,否则行为未定义。std::cout << "栈顶元素: " << s.top() << std::endl; // 输出 10
s.top() = 30; // 修改栈顶元素为30
std::cout << "修改后的栈顶元素: " << s.top() << std::endl; // 输出 30
empty()
true
;否则返回false
。if (s.empty()) {
std::cout << "栈为空" << std::endl;
} else {
std::cout << "栈不为空" << std::endl; // 输出栈不为空
}
size()
std::cout << "栈的大小: " << s.size() << std::endl; // 输出 1
stack
对象来初始化新的栈。std::stack<int> s1; // 默认构造函数,创建空栈
std::stack<int> s2(s1); // 复制构造函数
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;
}
#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;
}
在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;
}
在C++标准库的queue
和其他类似容器适配器中,底层容器的选择和实现是非常关键的,它影响了容器的性能和操作的特性。
C++中的queue
并不是一种独立的容器,它是容器适配器的一种。这意味着,queue
不直接管理元素的存储,而是依赖于其他容器来完成实际的存储操作。queue
提供了一个**先进先出(FIFO)**的操作接口,而将实际数据的管理交给它所适配的底层容器。
queue
的底层容器可以是以下几种常见的标准容器:
deque
(双端队列):这是queue
的默认底层容器。deque
提供了双端插入和删除操作,适合在队列头部和尾部进行高效的操作。list
(链表):可以自定义使用链表作为底层容器,链表在插入和删除元素时非常高效,尤其是在队列头部和尾部进行操作。vector
:虽然不常用,但理论上也可以作为底层容器,但vector
在头部插入和删除时效率较低,因为这些操作需要移动大量的元素。选择不同的底层容器主要是为了适应不同的需求场景。容器适配器(如queue
)通过操作底层容器来实现功能,因此底层容器的性能特性会直接影响queue
的整体性能和适用性。
deque
(默认)vector
,deque
在队列头部删除元素时更加高效。deque
提供了随机访问的能力(但不如vector
快),因此它可以在不牺牲太多性能的情况下满足队列的需求。queue
默认使用deque
作为底层容器,因为它可以高效地在队列头部删除元素和在尾部插入元素。list
list
是双向链表,它的特点是可以在任意位置进行常数时间的插入和删除操作,特别适合队列这种频繁在头部和尾部进行插入删除操作的场景。list
作为底层容器时,虽然插入和删除性能好,但list
不支持随机访问,所以相较于deque
在访问元素时性能较差。vector
vector
也可以作为底层容器,但由于vector
在头部进行插入和删除操作需要移动大量元素,这种操作代价较高,因此它并不适合作为queue
的底层容器。vector
的优势是它支持随机访问和连续的内存布局,但这些特性对queue
的操作并不是必须的。在C++中,我们可以通过模板参数来指定queue
的底层容器。以下是使用不同容器作为queue
底层容器的示例:
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;
}
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;
}
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;
}
deque
:非常适合queue
的操作模式,因为它允许在两端进行高效的插入和删除操作。随机访问性能尚可,内存布局较为灵活。list
:适合需要大量插入和删除操作的场景,但不支持随机访问。相比deque
,其随机访问性能较差,但在频繁的插入删除场景中效率更高。vector
:虽然提供了快速的随机访问,但由于头部插入和删除操作开销较大,不适合作为queue
的底层容器。queue
**是容器适配器,依赖于底层容器(如deque
或list
)来实现其功能。deque
**作为底层容器,适合在两端高效进行插入和删除。list
或vector
作为底层容器,具体选择取决于使用场景的需求。C++标准库中的queue
容器适配器提供了一组用于操作队列的成员函数。这些成员函数允许我们向队列中添加、访问、删除元素,并检查队列的状态。下面是queue
常用的成员函数以及它们的作用。
成员函数 | 作用 |
---|---|
push() | 向队列的末尾添加元素 |
pop() | 移除队列的队首元素 |
front() | 获取队列的队首元素 |
back() | 获取队列的队尾元素 |
empty() | 检查队列是否为空 |
size() | 返回队列中的元素个数 |
构造函数 | 创建队列实例并初始化 |
析构函数 | 销毁队列实例并释放资源 |
push(const T& value)
/ push(T&& value)
std::queue<int> q;
q.push(10); // 插入元素10到队列末尾
q.push(20); // 插入元素20到队列末尾
pop()
pop()
之前使用front()
获取队首元素的值。q.pop(); // 移除队首元素10,队列现在为20
front()
front()
之前,应该确保队列不为空,否则行为是未定义的。std::cout << "队首元素: " << q.front() << std::endl; // 输出队首元素20
back()
std::cout << "队尾元素: " << q.back() << std::endl; // 输出队尾元素20
empty()
true
,否则返回false
。if (q.empty()) {
std::cout << "队列为空" << std::endl;
} else {
std::cout << "队列不为空" << std::endl;
}
size()
std::cout << "队列中元素个数: " << q.size() << std::endl;
queue
的构造函数可以通过不同方式初始化队列: std::queue<int> q1; // 默认构造函数,创建空队列
std::queue<int> q2(q1); // 使用复制构造函数
#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前进的动力!