九度OJ 1512 用两个栈实现队列

谁践踏了优雅 2022-09-30 11:50 4阅读 0赞

**题目描述：**

用两个栈来实现一个队列，完成队列的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

题意分析：
    　　用两个栈实现一个队列。栈(stack)的特点是先进后出，是反的；而队列(queue)的特点是先进先出，是正的。因此用两个栈，反两次就能正过来。接下来咱看看怎么个反法。
    　　咱们从例子入手：四个数1， 2， 3， 4进入队列，如果这时想pop的话，应当是1出队。两个栈s1，s2如下(左边代表栈顶)：
    　　　　s1 = [4, 3, 2, 1]
    　　　　s2 = []
    　　但是1， 2， 3， 4进栈时，栈顶元素是4。要想取出1的话，必须先pop掉4，3，2。pop出来的元素又不能扔掉，就扔另一个栈里去吧，于是就成了这样：
    　　　　s1 = [1]
    　　　　s2 = [2, 3, 4]
    　　因为进站后顺序又反了一次，所以s2中存储的顺序就是正确的出队顺序，这时直接从s1中pop出元素‘1’即可。如果要继续pop元素的话，s2栈不为空，直接pop就能得到正确的结果。
    　　于是有了下面的思路：
    　　　　　1. 初始化s1、s2为空。
    　　　　　2. 当进队时，直接将元素push进s1。
    　　　　　3. 当出队时，
    　　　　　　　若s2不为空，直接pop s2的元素即可出队；
    　　　　　　　若s2为空，则将s1中元素pop出来，并push到s2中，直到s1只剩一个元素。剩的那个元素pop出来就是出队的元素。
    　　　　　　　当然，两个栈都为空的话pop操作是无效的。
    　　这题应该算是很经典的面试题了，挺巧妙的。以下是ac的代码。push入队时间复杂度O(1)，pop出队时间复杂度O(1)或O(n)，均摊下来仍是O(1)。

![复制代码][copycode.gif]

1 // 651425    zhuli19901106    1512    Accepted    点击此处查看所有case的执行结果    1184KB    1415B    70MS
     2 // 201311142215
     3 #include <cstdio>
     4 #include <cstring>
     5 #include <stack>
     6 using namespace std;
     7 
     8 class MyQueue{
     9 public:
    10     MyQueue()
    11     {
    12     }
    13     
    14     ~MyQueue()
    15     {
    16         while(!s1.empty()){
    17             s1.pop();
    18         }
    19         while(!s2.empty()){
    20             s1.pop();
    21         }
    22     }
    23     
    24     void push(int n)
    25     {
    26         s1.push(n);
    27     }
    28     
    29     int pop()
    30     {
    31         if(s1.size() <= 0 && s2.size() <= 0){
    32             // The queue is empty, return -1 to signal an error.
    33             return -1;
    34         }
    35         if(s2.size() > 0){
    36             int res = s2.top();
    37             s2.pop();
    38             return res;
    39         }else{
    40             int res;
    41             while(s1.size() > 1){
    42                 res = s1.top();
    43                 s1.pop();
    44                 s2.push(res);
    45             }
    46             res = s1.top();
    47             s1.pop();
    48             return res;
    49         }
    50     }
    51     
    52     void clear()
    53     {
    54         while(s1.size() > 0){
    55             s1.pop();
    56         }
    57         while(s2.size() > 0){
    58             s2.pop();
    59         }
    60     }
    61     
    62     int size()
    63     {
    64         return s1.size() + s2.size();
    65     }
    66 private:
    67     stack<int> s1, s2;
    68 };
    69 
    70 int main()
    71 {
    72     char s[100];
    73     int n;
    74     int i;
    75     int tmp;
    76     MyQueue queue;
    77     
    78     while(scanf("%d", &n) == 1){
    79         for(i = 0; i < n; ++i){
    80             scanf("%s", s);
    81             if(strcmp(s, "PUSH") == 0){
    82                 scanf("%d", &tmp);
    83                 queue.push(tmp);
    84             }else if(strcmp(s, "POP") == 0){
    85                 printf("%d\n", queue.pop());
    86             }
    87         }
    88         queue.clear();
    89     }
    90     
    91     return 0;
    92 }

[copycode.gif]: /images/20220706/a590a80e09c041f292d759f0fcbb12d6.png