栈与队列

Posted 2024-09-20 Updated 2024-09- 23

By nbb

8~10 min read

栈与队列

速通栈

核心：先进后出的容器

image_20240409_222758_409

这次主要掌握C++中栈的相关操作
在C++中，栈的最常用操作如下表：

操作	返回值类型	描述
`push()`	`void`	向栈顶添加一个元素，无返回值
`pop()`	`void`	移除栈顶的元素，无返回值
`top()`	`T&`	返回栈顶元素的引用，其中`T`是栈中元素的类型
`empty()`	`bool`	如果栈为空返回`true`，否则返回`false`
`size()`	`size_type`	返回栈中元素的数量，`size_type`通常是无符号整数类型

请注意，top()函数返回的是一个引用，这意味着你可以查看但也可以修改栈顶元素的值。而empty()和size()函数则提供了栈的状态信息。push()和pop()函数用于修改栈的内容，但它们不返回任何值。

速通队列

核心：先进先出

image_20240409_223627_110

同样的，了解C++中队列的用法：

操作	描述	返回值类型
`push()`	在队列尾部插入一个元素	`void`
`pop()`	移除队列头部的一个元素	`void`
`front()`	返回队列头部的元素	`T&`
`back()`	返回队列尾部的元素	`T&`
`empty()`	如果队列为空返回`true`，否则返回`false`	`bool`
`size()`	返回队列中元素的数量	`size_type`

这些操作都是通过C++标准库中的std::queue容器适配器来实现的。

而C++中，queue默认是双向队列，除了这些函数，还有其他的。

一个例子：

/* 初始化双向队列 */
deque<int> deque;
/* 元素入队 */
deque.push_back(2);   // 添加至队尾
deque.push_front(3);  // 添加至队首
/* 访问元素 */
int front = deque.front(); // 队首元素
int back = deque.back();   // 队尾元素
/* 元素出队 */
deque.pop_front();  // 队首元素出队
deque.pop_back();   // 队尾元素出队
/* 获取双向队列的长度 */
int size = deque.size();
/* 判断双向队列是否为空 */
bool empty = deque.empty();

参考资料：Hello算法

算法

License: CC BY 4.0