【算法篇】栈和队列专题之广度优先遍历和深度优先遍历
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法篇】栈和队列专题之广度优先遍历和深度优先遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4208字，纯文字阅读大概需要7分钟。
内容图文
前言
今天要介绍栈和队列相关算法，栈和队列这种数据结构相对简单，但是结合算法就变化莫测了，一起来看一下吧
一、栈
1、简介
栈这种数据结构可以用数组、线性表和链表等来实现，但要保证先进后出这种性质；
可能会问栈有什么应用呢？
应用非常广泛，像编辑器的撤销功能，先把“操作”入栈，然后最后入栈的，先弹出，就实现撤销功能了；
像linux内核实现的函数调用，也是把函数不断入栈，然后再弹出，还有栈和递归和密不可分的。
2、题目
LeetCode上第20号题，题目如下：
给定一个只包含字符“(”、“)”、“{”、“}”、“[”和“]”的字符串，确定输入字符串是否有效。
如果:输入字符串有效:
开括号必须用相同类型的括号括起来。
开括号必须按正确的顺序关闭。
注意，空字符串也被认为是有效的。
示例1:
输入:“()”
输出:正确
示例2:
输入:“()(){ }”
输出:正确
示例3:
输入:“(]”
输出:假
示例4:
输入:“([))”
输出:假
例5:
输入:“{[]}”
输出:正确
进行画图讲解吧，如下图： PS：依旧是全网最丑图！很努力去画，依旧很丑，看来画图的天赋了！
说明：
假如，[()]要入栈，规则：遇到“左边符号”入栈，“右边符号”弹出栈顶元素，进行比较，“()”符合要求，就是正确的，以此类推；还有一点要注意的，最后栈不是空的，说明栈里还有“左边符号”，这是不正确的。
3、代码及演示
代码如下：
#include <iostream>
#include <stack>
#include <cassert>
using namespace std;
// 20. Valid Parentheses
// https://leetcode.com/problems/valid-parentheses/description/
// 时间复杂度: O(n)
// 空间复杂度: O(n)
class Solution {
public:
bool isValid(string s) {
stack<char> stack;
for( int i = 0 ; i < s.size() ; i ++ )
if( s[i] == '(' || s[i] == '{' || s[i] == '[')
stack.push(s[i]);
else{
if( stack.size() == 0 )
return false;
char c = stack.top();
stack.pop();
char match;
if( s[i] == ')' )
match = '(';
else if( s[i] == ']' )
match = '[';
else{
assert( s[i] == '}' );
match = '{';
}
if(c != match)
return false;
}
if( stack.size() != 0 )
return false;
return true;
}
};
int main() {
if(Solution().isValid("()"))
cout << "() is valid." << endl;
else
cout << "() is invalid." << endl;
if(Solution().isValid("()[]{}"))
cout << "()[]{} is valid." << endl;
else
cout << "()[]{} is invalid." << endl;
if(Solution().isValid("(]"))
cout << "(] is valid." << endl;
else
cout << "(] is invalid." << endl;
if(Solution().isValid("([)]"))
cout << "([)] is valid." << endl;
else
cout << "([)] is invalid." << endl;
return 0;
}
View Code
我对几组数据进行了测试：()、()[]{}等，运行结果如下：
4、总结
栈的应用非常多，主要理解栈的先进后出的特性！
二、队列
1、简介
队列也是一种线性数据结构，特性是先进先出；队列有一个重要应用：广度优先遍历，相对于广度还有一种深度优先遍历，可能对于一些人还不知道广度、深度优先遍历，所以来解释一下。
对于二叉树来说：
广度优先遍历叫层序遍历更贴切，一层一层来遍历的，下面会详细讲解这种应用；
深度优先遍历就是先序、中序和后序遍历；
对图来说：就分为广度优先遍历和深度优先遍历了，图这部分之后我还会详细讲解；
2、题目
LeetCode第102题，题目如下：
给定二叉树，返回其节点值的层次顺序遍历。(例如，从左到右，逐层排列)。
例如:
给定二叉树[3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回其水平顺序遍历如下:
[
[3],
[9,20],
[15,7]
]
这是二叉树典型的层序遍历，还有二叉树的先序、中序和后序遍历，统称为深度优先遍历！不懂的老铁可以参考这篇博客：https://www.cnblogs.com/liudw-0215/p/9835691.html，讲的很详细。
用图进行讲解吧，图如下：
说明：先把根节点1入队，然后是2、3，以此类推，然后再出队，就可以实现层序遍历了。
3、代码实现
代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
/// 102. Binary Tree Level Order Traversal
/// https://leetcode.com/problems/binary-tree-level-order-traversal/description/
/// 二叉树的层序遍历
/// 时间复杂度: O(n), n为树的节点个数
/// 空间复杂度: O(n)
/// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
queue<pair<TreeNode*,int>> q;
q.push(make_pair(root, 0));
while(!q.empty()){
TreeNode* node = q.front().first;
int level = q.front().second;
q.pop();
if(level == res.size())
res.push_back(vector<int>());
assert( level < res.size() );
res[level].push_back(node->val);
if(node->left)
q.push(make_pair(node->left, level + 1 ));
if(node->right)
q.push(make_pair(node->right, level + 1 ));
}
return res;
}
};
int main() {
return 0;
}
View Code
总结
栈和队列的应用非常之多，要不断理解它们的特性：先进后出、先进先出！喜欢的欢迎随时点赞，不懂的欢迎随时留言！
内容总结
以上是互联网集市为您收集整理的【算法篇】栈和队列专题之广度优先遍历和深度优先遍历全部内容，希望文章能够帮你解决【算法篇】栈和队列专题之广度优先遍历和深度优先遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。