用栈实现其它数据结构或者函数
用栈实现队列
描述
用两个栈来实现一个队列，使用n个元素来完成 n
次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。
队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
数据范围： n*≤1000
要求：存储n个元素的空间复杂度为 O(n)
，插入与删除的时间复杂度都是 O(1)
解题思路
借助栈的先进后出规则模拟实现队列的先进先出
1、当插入时，直接插入 stack1
2、当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2
为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2
栈顶元素
注意一定要将2用空再将1的倒入并且是全部倒入
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
| class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int ret=stack2.top();
stack2.pop();
return ret;
}
private:
stack<int> stack1;
stack<int> stack2;
};
|
复杂度分析：
时间复杂度：对于插入和删除操作，时间复杂度均为
O(1)。插入不多说，对于删除操作，虽然看起来是O(n)
的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2
一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。
空间复杂度O(N)：辅助栈的空间，最差的情况下两个栈共存储N个元素
用栈实现min函数
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
| #include <climits>
class Solution {
public:
void push(int value) {
if(stackdata.empty()){
mindata=value;
stackmin.push(mindata);
}
else {
if(mindata>=value){
mindata=value;
stackmin.push(mindata);
}
}
stackdata.push(value);
}
void pop() {
int top=stackdata.top();
if(top==mindata){
stackmin.pop();
if(!stackmin.empty())
mindata=stackmin.top();
else
mindata=INT_MAX;
}
stackdata.pop();
}
int top() {
return stackdata.top();
}
int min() {
return mindata;
}
private:
stack<int> stackdata;
stack<int> stackmin;
int mindata;
};
|
栈压入弹出序列
JZ31
栈的压入、弹出序列
思路
题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。如果能按照这个次序将两个序列都访问完，那说明是可以匹配入栈出栈次序的。
代码
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
| class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack <int> mystack1;
int j=0;
for(int i=0;i<pushV.size();i++){
mystack1.push(pushV[i]);
while(!mystack1.empty()&&j<popV.size()&&mystack1.top()==popV[j]){
mystack1.pop();
j++;
}
}
while (!mystack1.empty()) {
int tmp=mystack1.top();
mystack1.pop();
if(tmp!=popV[j])
return false;
j++;
}
if(j!=popV.size())
return false;
return true;
}
};
|
翻转单词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
string ReverseSentence(string str) {
stack<string> mystack;
for(int i=0;i<str.size();i++){
int j=i;
while(j<str.size()&&str[j]!=' ')
j++;
mystack.push(str.substr(i,j-i));
i=j;
}
string strret="";
while(!mystack.empty()){
strret+=mystack.top();
mystack.pop();
if(!mystack.empty())
strret += " ";
}
return strret;
}
};
|