数据结构-栈与队列-数组和链表的推广运用-第六天
hello算法
1.数组和队列作为最基础的两种数据结构，区别主要在于：
1.数组是连续存储，因此可以利用一个开始节点的地址直接确定其他的节点地址。
2.链表未绑定的存储顺序，具有更灵活快捷的增删改查。
3.为了解决存储的问题，数组发展了动态数组的概念。
2.栈和队列的定义
总结：
1.栈是一种先入后出的数据结构，类似于“铁饼堆叠游戏”。
2.队列是一种先入先出的数据结构，类似于“数据进入不能回头的管道”。
3.栈和队列的操作（c++标准库STL）
stack库：
#include <stack>// 声明队列
std::stack<Type> stack;
/* 初始化栈 */
stack<int> stack;/* 元素入栈 */
stack.push(1);
/* 访问栈顶元素 */
int top = stack.top();/* 元素出栈 */
stack.pop(); // 无返回值/* 获取栈的长度 */
int size = stack.size();/* 判断是否为空 */
bool empty = stack.empty();
queue库：
#include <queue>// 声明队列
std::queue<Type> queue;
//定义一个队列
queue<int> queue;
// 元素入队
queue.push(1);
/* 访问队首元素 */
int front = queue.front();/* 元素出队 */
queue.pop();/* 获取队列的长度 */
int size = queue.size();/* 判断队列是否为空 */
bool empty = queue.empty();
下面列举了一些常见的应用场景：
4.栈 (Stack) 的应用
-
函数调用和返回:
- 在程序执行过程中，每当一个函数被调用时，系统会将调用信息压入栈中；当函数返回时，这些信息会被弹出栈。这种机制保证了函数调用的正确顺序。
-
表达式求值:
- 用于解析和求值后缀表达式（逆波兰表示法）。例如，编译器和计算器使用栈来处理括号匹配和操作符优先级。
-
括号匹配:
- 栈可以用来检查括号是否正确匹配。例如，当遇到左括号时将其压入栈中，遇到右括号时从栈中弹出对应的左括号进行匹配。
-
撤销操作:
- 在许多应用程序中，如文本编辑器、图形编辑软件等，栈可以用来实现撤销 (Undo) 功能。
-
浏览器历史记录:
- 浏览器使用栈来保存用户访问过的网页的历史记录，从而实现前进和后退的功能。
-
递归调用:
- 递归算法通常依赖于栈来保存每次递归调用的信息。
-
回溯算法:
- 在搜索问题的解空间时，使用栈来保存中间状态，以便在搜索失败时能够回退到上一个状态。
队列 (Queue) 的应用
-
任务调度:
- 操作系统中使用队列来管理进程的执行顺序，如就绪队列。
-
消息队列:
- 在分布式系统中，消息队列用于异步通信，确保消息按照发送的顺序被处理。
-
打印机队列:
- 打印机使用队列来管理打印任务，确保文档按照提交的顺序被打印。
-
缓冲区:
- 在网络通信中，队列用于缓冲输入和输出数据，确保数据包的有序传输。
-
事件处理:
- 在图形界面应用程序中，队列用于管理用户事件（如鼠标点击、键盘输入等）的处理顺序。
-
缓存管理:
- 在缓存系统中，使用队列来实现最近最少使用 (LRU) 缓存替换策略。
-
广度优先搜索 (BFS):
- 在图论中，广度优先搜索算法通常使用队列来保存待访问的节点。
示例代码
下面是一个简单的示例，展示了栈和队列在解决实际问题中的应用：
使用栈解决括号匹配问题
#include <iostream>
#include <stack>
#include <string>bool isValidParentheses(const std::string& s) {std::stack<char> stack;for (char c : s) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else if (!stack.empty()) {char top = stack.top();if ((c == ')' && top == '(') ||(c == ']' && top == '[') ||(c == '}' && top == '{')) {stack.pop();} else {return false;}} else {return false;}}return stack.empty();
}int main() {std::string s = "{[()]}";std::cout << "Is valid: " << (isValidParentheses(s) ? "Yes" : "No") << std::endl;return 0;
}
使用队列实现广度优先搜索 (BFS)
假设我们有一个简单的图，使用邻接列表表示：
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>void bfs(const std::vector<std::vector<int>>& graph, int start) {std::queue<int> q;std::unordered_set<int> visited;q.push(start);visited.insert(start);while (!q.empty()) {int node = q.front();q.pop();std::cout << "Visited " << node << std::endl;for (int neighbor : graph[node]) {if (visited.find(neighbor) == visited.end()) {q.push(neighbor);visited.insert(neighbor);}}}
}int main() {std::vector<std::vector<int>> graph = {{1, 2},{0},{0, 3},{2}};bfs(graph, 0);return 0;
}
这些例子展示了栈和队列在不同领域的应用。根据具体问题的特点，可以选择合适的数据结构来解决问题。如果你有更具体的问题或需要进一步的帮助，请随时告诉我！