rambo

栈相关题目

2015年5月10日 ACM解题 0 Comments

Pop Sequence

描述

一列数, 只能以1, 2, …., N的push 到stack里面, 但是可以再任意时刻pop出一个数字, 问给定一个序列, 是不是一个可行的按照这样的规则可以出现的一个pop序列.

分析

根据给定的pop序列, 还原push 和 pop的过程, 因为一个pop sequence 只能对应一个唯一的push pop的操作过程, 所以到最后能还原那么这个pop sequence是可行的, 否则不可能, 比如: 3, 2, 1, 7, 5, 6, 4. 这个序列, 那么我们看第一个3, 要pop出3, 那么肯定要先push 1, push 2, push 3, pop 3, 接下来看2, 此时栈顶确实是2那么 pop 2, 接下来1类似, 好了下面一个是7, 那么我们必须要先push 4, push 5, push 6, push 7, 然后pop 7可以得到一个7, 接下来需要5,但是此时栈顶元素是6, 所以这个sequence就是不可能了。

This question actually could be generalized into any two input sequences one for push, and one for pop, and the push sequence does not have to be increasing order, and put restrict on the number of pushes/pops or the order of the push sequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdafx.h"
#include <vector>
#include <stack>
using namespace std;
 
bool validatePopStk(const std::vector<int>& vecPush, const std::vector<int>& vecPop){
if (vecPush.size() != vecPop.size()) return false;
int nCount = vecPush.size();
auto itrPush = vecPush.begin(), itrPop = vecPop.begin();
std::stack<int> stk;
while (itrPop != vecPop.end()){
if (stk.empty() || stk.top() != *itrPop){
//如果当前栈为空或者栈顶元素与Pop元素不一致,依次压栈
while (itrPush != vecPush.end() && (stk.empty() || stk.top() != *itrPop)){
//入栈
stk.push(*itrPush);
++itrPush;
}
//如果当前栈不为空而且栈顶元素与Pop元素不一致
if (!stk.empty() && stk.top() != *itrPop) break;
}
//注意，这个else是在下一次while时跳入的
else{
//如果当前栈不为空而且栈顶元素与Pop元素一致,依次出栈
stk.pop();
++itrPop;
}
}
return stk.empty() && itrPop == vecPop.end() && itrPush == vecPush.end();
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
//注意这种初始化方式只是被C++11支持，VS2010会编译错误
const std::vector<int> vecPush = { 0,1, 2, 3, 4, 5, 6, 7, 8, 9};
const std::vector<int> vecPop= { 1 ,0 ,2, 3 ,4 ,7 ,6, 5 ,9, 8 };
const std::vector<int> vecPop1 = { 3 ,2, 4,6, 1, 8, 7, 9, 5,0 };
 
bool isvalidate = validatePopStk(vecPush, vecPop);
bool isvalidate1 = validatePopStk(vecPush, vecPop1);
system("pause");
return 0;
}

用两个队列模拟栈

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
 
template<typename T> class CStack{
public:
CStack(void){};
~CStack(void){};
void CPush(const T& element);
void CPop();
T CTop();
bool empty();
 
private:
deque<T> deque1;
deque<T> deque2;
};
 
template<typename T> void CStack<T>::CPush(const T& element){
//两个队列都是空的，不妨将元素element插入deque1
if(deque1.empty()&&deque2.empty()){
deque1.push_back(element);
}
else if(!deque1.empty()&&deque2.empty()){
deque1.push_back(element);
}
else if (deque1.empty() && !deque2.empty()){  
deque2.push_back(element);  
}  
}
 
template<typename T> void CStack<T>::CPop(){
//将非空队列的前n-1个元素转移到另一个空的队列，删除非空队列的第n个元素
if(!deque1.empty()){
deque<T>::size_type size=deque1.size();
for(deque<T>::size_type i=0;i!=size-1;i++){
deque2.push_back(deque1.front());
deque1.pop_front();
}
deque1.pop_front();
}
else{
deque<T>::size_type size=deque2.size();
for(deque<T>::size_type i=0;i!=size-1;i++){
deque1.push_back(deque2.front());
deque2.pop_front();
}
deque2.pop_front();
}
}
 
//栈顶元素，将非空队列的前n-1个元素转移到另一个空的队列，将非空队列的第n个元素返回
template<typename T> T CStack<T>::CTop(){
if(!deque1.empty()){
deque<T>::size_type size=deque1.size();
for(deque<T>::size_type i=0;i!=size-1;i++){
deque2.push_back(deque1.front());
deque1.pop_front();
}
T temp=deque1.front();
deque1.pop_front();
deque2.push_back(temp);
return temp;
}
else{
deque<T>::size_type size=deque2.size();
for(deque<T>::size_type i=0;i!=size-1;i++){
deque1.push_back(deque2.front());
deque2.pop_front();
}
T temp = deque2.front();  
deque2.pop_front();  
deque1.push_back(temp);  
return temp;  
}
}
 
//栈是否为空  
template<typename T>bool CStack<T>::empty()  {  
return (deque1.empty()&&deque2.empty());  
}  
 
int _tmain(int argc, _TCHAR* argv[]){
CStack<int> mystack;
for (int i=0; i<10; i++){  
mystack.CPush(i);  
}  
while (!mystack.empty())  {  
cout<<mystack.CTop()<<" ";  
mystack.CPop();  
}  
system("pause");
return 0;
}