首页 > 代码库 > 剑指OFFER之用两个栈实现队列(九度OJ1512)

剑指OFFER之用两个栈实现队列(九度OJ1512)

题目描述:

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

 

解题思路:

首先题目要求,两个栈表示队列。那么最好就用两个栈喽,虽然不知道OJ是怎么检测的,但是应该用一个队列是不行的。
那么我们想起了汉诺塔,栈本身是后进后出,队列是先进先出。这样如何来设计呢?
使用两个栈,第一个栈用来PUSH,第二个栈用来POP。
要注意的问题是,两个栈中间的到处元素的顺序不能乱。只要栈2中还有元素存在,栈1就不能往栈2中压元素。比如
栈1新进元素3
栈2中元素为 2 1,
那么两个栈的列表为:
3
2 1 
此时如果要出栈的顺序必须是
1 2 3
如果此时把栈1压入栈2,出栈的顺序就成为
3 1 2
因此,切忌要保证栈2中的元素为空时,再向栈2内压入栈1的元素

代码:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#define MAX 100001
int stack1[MAX],stack2[MAX],top1,top2;
int main(void){
    int n,i,m;
    char input1[10];
    while(scanf("%d",&n)!=EOF && n<=100000 && n>= 1){
        top1 = top2 = 0;
        memset(&stack1,0,sizeof(int)*MAX);
        memset(&stack2,0,sizeof(int)*MAX);
        for(i=0;i<n;i++){
            scanf("%s",input1);
            if(strcmp(input1,"PUSH") == 0){
                scanf("%d",&m);
                stack1[top1++] = m;
            }else{
                if(top2 == 0){//判断栈2是否还存在元素
                    while(top1){
                        stack2[top2++] = stack1[--top1];
                    }
                }
                if(top2)//如果栈2中有元素,则弹出,否则,表示两个栈都没有元素
                    printf("%d\n",stack2[--top2]);
                else{
                    printf("-1\n");
                }
            }
        }
    }
    return 0;
}