提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
队列、栈、列表是其中三个最为基础和常用的数据结构,它们在编程的世界中被广泛应用,为算法和数据处理提供了不可或缺的支持。今天来简单的介绍一下!以及他们在C++中的简单用法!
一、队列(Queue)
队列是一种常见的数据结构,它按照先进先出(FIFO)
的原则管理元素。队列通常用于在程序中保存和处理一系列任务或数据。
- 入队(enqueue): 将元素添加到队列的末尾。
- 出队(dequeue): 从队列的前端移除元素。
队列的特点是新元素总是在队列的尾部添加,而移除元素总是从队列的头部进行。队列是一个有序的集合,先进入队列的元素会先被处理。
队列常常用于解决需要按顺序处理的问题
,例如任务调度、广度优先搜索等。
C++标准库中 std::queue :
- push: 将元素添加到队列的末尾
- front: 访问队头元素
- pop: 移除队头元素
- empty: 检查队列是否为空
例子:
#include <iostream>
#include <queue>
int main() {
// 创建一个队列
std::queue<int> myQueue;
// 入队操作
myQueue.push(1);
myQueue.push(2);
// 出队操作
while (!myQueue.empty()) {
std::cout << myQueue.front() << " "; // 访问队头元素
myQueue.pop(); // 出队
}
return 0;
}
二、栈(Stack)
栈是一种基本的数据结构,具有后进先出(LIFO)
的特性。这意味着最后进入栈的元素将首先被移除。栈通常有两个主要操作:压入(Push)和弹出(Pop)。
- 压入(Push): 将元素添加到栈的顶部。
- 弹出(Pop): 从栈的顶部移除元素。
栈常常用于解决解密回文,函数调用,深度优先搜索(DFS),回溯算法,括号匹配,递归算法的非递归实现,迷宫求解,编辑器的撤销操作等等。
- 函数调用: 栈被用来存储函数调用的上下文信息,包括局部变量、返回地址等。函数调用时,局部变量等信息被压入栈,函数执行完成后再从栈中弹出
- 深度优先搜索(DFS): 在图的深度优先搜索算法中,栈可以用于追踪遍历路径。每次访问一个节点时,将其邻接节点压入栈,然后从栈中弹出下一个节点进行继续深度搜索
- 回溯算法: 回溯算法通常使用栈来保存当前的状态,并在需要时回退到之前的状态,以搜索所有可能的解空间
括号匹配: 栈可以用于检查表达式中的括号是否匹配,以及判断表达式的有效性
递归算法的非递归实现: 栈可以用于模拟递归算法的工作方式,将递归调用转化为循环结构- 迷宫求解: 在迷宫求解问题中,栈可以用于保存当前路径,如果当前路径无法到达目标点,则回退到上一个路径
- 编辑器的撤销操作: 栈可以用于实现编辑器中的撤销和重做操作,存储用户操作的历史记录
C++标准库中 std::stack:
- push: 将元素压入栈顶
- pop: 弹出栈顶元素
- top(): 访问栈顶元素,但不弹出
- empty(): 检查栈是否为空
- size(): 返回栈中元素的数量
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
// 压入元素
myStack.push(1);
myStack.push(2);
// 弹出元素
while (!myStack.empty()) {
std::cout << myStack.top() << " "; // 访问栈顶元素
myStack.pop(); // 弹出栈顶元素
}
return 0;
}
三、列表(List)
列表是一种有序、可变的数据结构,用于存储一系列的元素。列表是一种非常灵活和常用的数据类型,它可以包含不同数据类型的元素,甚至可以包含其他列表。
C++标准库中 std::list:文章来源:https://www.toymoban.com/news/detail-815665.html
- push_back(): 在列表末尾插入元素
- push_front(): 在列表开头插入元素
- insert(): 在指定位置插入元素
- remove(): 删除指定值的元素
- pop_back(): 弹出并删除最后一个元素
- front(): 访问第一个元素
- back(): 访问最后一个元素
- size(): 获取列表大小
- clear(): 清空列表
- empty(): 判断列表是否为空
- for (auto it = myList.begin(); it != myList.end(); ++it): 使用迭代器遍历列表
#include <iostream>
#include <list>
int main() {
// 创建一个空列表
std::list<int> myList;
// 在列表末尾插入元素
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
// 在列表开头插入元素
myList.push_front(0);
std::cout << "List elements: ";// 使用迭代器遍历列表并打印元素
for (auto it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
// 在指定位置插入元素
auto insertPos = std::next(myList.begin(), 2);
myList.insert(insertPos, 99);
myList.remove(2);// 删除指定值的元素
myList.pop_front();// 弹出并删除第一个元素
myList.pop_back();// 弹出并删除最后一个元素
// 访问第一个元素和最后一个元素
std::cout << "First element: " << myList.front() << std::endl;
std::cout << "Last element: " << myList.back() << std::endl;
std::cout << "List size: " << myList.size() << std::endl; // 获取列表大小
myList.clear();// 清空列表
if (myList.empty()) {// 判断列表是否为空
std::cout << "List is empty." << std::endl;
}
return 0;
}
总结
本节介绍了队列、栈、列表是其中三个最为基础和常用的数据结构,唐怡佳继续加油~
文章来源地址https://www.toymoban.com/news/detail-815665.html
到了这里,关于C++中的常见数据结构 --- 队列、栈、列表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!