CCI题目3-5:Queue using Two Stacks

By | 2012 年 11 月 20 日

用两个stack来模拟queue。
一个叫做instack,一个叫做outstack。
当push的时候,将所有的item导入instack,然后push into instack。
当pop的时候,将所有的item导入outstack,然后outstack.pop()。
这样就可以先进先出了。



题目
Implement a MyQueue class which implements a queue using two stacks.



Code

<

pre>

//
// main.cpp
// CCI.3.5.Queue using Two Stacks
//
// Created by Qiu Xiangyu on 12-11-20.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;

//stacks like:
// instack: [old , … , new
// outstack: old, … , new]
template
class StackQueue {
stack _inStack;
stack _outStack;
void dumpToInStack() {
while (_outStack.size()) {
_inStack.push(_outStack.top());
_outStack.pop();
}
}
void dumpToOutStack() {
while (_inStack.size()) {
_outStack.push(_inStack.top());
_inStack.pop();
}
}
public:
void push(T val) {
dumpToInStack();
_inStack.push(val);
}
void pop() {
dumpToOutStack();
_outStack.pop();
}
T *top() {
dumpToOutStack();
if (_outStack.size()) {
return &_outStack.top();
}
return NULL;
}
size_t size() {
return _inStack.size() + _outStack.size();
}
};
int main(int argc, const char * argv[])
{

// insert code here...
std::cout << "Hello, World!\n";
StackQueue<int> qu;
for (int i = 0; i < 10; ++i) {
    qu.push(i);
}
while (qu.size()) {
    int v = *qu.top();
    cout<<v<<endl;
    qu.pop();
}
return 0;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注