关于栈的几道面试题目

- 日理万妓 2022-08-07 01:55 146阅读 0赞

# 1. 括号匹配 #

http://wenku.baidu.com/link?url=ExL5fVcWJJR2x\_l5AWK9znXY98YGwLSYo56ZJtju4Ql6dJKvkHWGkBNPcfGLzm57bIQFwQKFt1dRgjE27N8EMfD462UyYtjGo3d\_A8WZbna  
  
  
主要解题思想是遇到左括号，入栈；遇到右括号，出栈。当发现需要出栈的元素不匹配的时候，说明括号不能匹配，否则，括号匹配。

# 2. 表达式计算 #

http://blog.chinaunix.net/uid-26833883-id-3156975.html  
  
  
主要解题思路是使用两个栈，一个栈存放运算的数据，一个栈存放运算符，注意需要考虑运算优先级，以及是否有括号运算。

# 3. 两个栈实现队列，还有两个队列实现栈的功能 #

http://www.cppblog.com/csu-yx-2013/archive/2012/03/11/167673.aspx （先看下面的代码，有我的注释，再看这个链接）  
  
  
http://blog.csdn.net/cfan0801/article/details/7351574 （辅助）  
  
  
\#include <cstdlib>  
\#include <iostream>  
\#include <stack>  
/\*两个栈实现队列\*/  
using namespace std;  
template<class T>  
struct MyQueue  
\{  
void push(T &t)  
\{  
s1.push(t);  
\}  
T front() // 实现队列的front功能  
\{  
if(s2.empty())  
\{  
if(s1.size()==0) throw;  
while(!s1.empty())  
\{  
s2.push(s1.top()); // 先把栈s1的元素转移到s2中  
s1.pop();  
\}  
\}  
return s2.top(); // 栈s2的顶部元素，就是栈s1的底部元素，实现了队列的front功能，即取头元素  
\}  
void pop()  
\{  
if(s2.empty())  
\{  
while(!s1.empty())  
\{  
s2.push(s1.top()); // 同上  
s1.pop();  
\}  
\}  
if(!s2.empty())  
s2.pop(); // pop掉s2的顶部元素，就是pop队列的头元素  
\}  
stack<T> s1;  
stack<T> s2;  
\};  
int main(int argc, char \*argv\[\])  
\{  
MyQueue<int> mq;  
int i;  
for(i=0;i<10;++i)  
\{  
mq.push(i);  
\}  
for(i=0;i<10;++i)  
\{  
cout<<mq.front()<<endl;  
mq.pop();  
\}  
system("PAUSE");  
return EXIT\_SUCCESS;  
\}

# 4. 栈实现最小值 #

http://blog.csdn.net/puqutogether/article/details/43916945

# 5. Linux简化文件路径 #

这个比较简单，基本解题思路是以/分隔字符串,遇到 . 和 空格什么都不做，遇到..退栈,其他都进栈,最后把栈中的都用/连接起来就是简化后的路径。  
  
  
举个例子：  
path = "/a/./b/../../c/", => "/c"  
  
  
压栈a，压栈b，遇到..需要出栈b，遇到..需要出栈a，压栈c。  
结果返回栈内只有的c。