首页 > 代码库 > 用两个栈实现队列

用两个栈实现队列

2024-07-04 22:32:20   228人阅读

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。

 

输入：

每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。

 

输出：

对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。

 

样例输入：
3
PUSH 10
POP
POP
样例输出：
10
-1
 1 #include<iostream>
 2 #include<stack>
 3 #include<vector>
 4 #include<string>
 5 using namespace std;
 6 class MyQueue
 7 {
 8 public:
 9     MyQueue(){}
10     ~MyQueue(){}
11     void push(int);
12     int pop();
13 private:
14     stack<int> stack_one;
15     stack<int> stack_two;
16 };
17 void MyQueue::push(int item)
18 {
19     stack_one.push(item);
20 }
21 int MyQueue::pop()
22 {
23     if(stack_two.size()<=0)
24     {
25         while(stack_one.size()>0)
26         {
27             int item = stack_one.top();
28             stack_one.pop();
29             stack_two.push(item);
30         }
31     }
32     if(stack_two.size()==0)
33         return -1;
34     int data =http://www.mamicode.com/ stack_two.top();
35     stack_two.pop();
36     return data;
37 }
38 int main(int argc,char **argv)
39 {
40     vector<int> result;
41     string kind;
42     MyQueue mq;
43     int value;
44     int step=0;
45     cin>>step;
46     while(step>0)
47     {
48         cin>>kind;
49         if(!(kind.compare(string("PUSH"))))
50         {
51             cin>>value;
52             mq.push(value); 
53         }
54         else
55         {
56             result.push_back(mq.pop());
57         }
58         step--;
59     }
60     vector<int>::iterator begin = result.begin();
61     for (;begin != result.end(); begin++)
62     {
63         cout<<*begin<<endl;
64     }
65     return 0;
66 }
67 /**************************************************************
68     Problem: 1512
69     User: xuebintian
70     Language: C++
71     Result: Accepted
72     Time:530 ms
73     Memory:2048 kb
74 ****************************************************************/

 


联系
我们