剑指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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

day02_js学习笔记_01_js的简介、js的基本语法

12520
来自专栏码云1024

python简明笔记

通过 for 语句我们可以使用 for 循环。Python 里的 for 循环与 C 语言中的不同。这里的 for 循环遍历任何序列(比如列表和字符串)中的每一...

63290
来自专栏数据分析

char varchar nchar nvarcharar到底有多大区别

首先说明下,ASP.NET MVC系列还在龟速翻译中。 工作好多年,基础知识甚是薄弱,决定以后在coding(cv操作)的时候尽量多google下,然后总结下来...

32260
来自专栏闪电gogogo的专栏

Python初学基础

初入坑Python,打算跟着沫凡小哥的学习视频打个基础,此篇文章做一些简单的学习记录,加油加油加油啦 沫凡小哥的学习网站:https://morvanzhou....

46070
来自专栏web前端教室

重学javascript 红皮高程(2)

为了送礼三八女王节,今晚跟同学一起喝酒去了。更新的有点晚,哈哈。。 让我们继续重新温习JS高程,今天来复习下基本概念。 JS它的语法是区分大小写地,并且函数名不...

20980
来自专栏上善若水

0x15Java引用赋值,是原子操作吗? 线程安全吗?

所谓原子操作,就是该操作绝不会在执行完毕前被任何其他任务或事件打断,也就说,它的最小的执行单位,不可能有比它更小的执行单位,因此这里的原子实际是使用了物理学里的...

37020
来自专栏编程思想之异常处理

Java编程思想之通过异常处理错误

1.     异常分为被检查的异常和运行时异常,被检查的异常在编译时被强制要求检查。异常被用来错误报告和错误恢复,但很大一部分都是用作错误报告的。

7810
来自专栏木木玲

Reference 、ReferenceQueue 详解

37570
来自专栏增长技术

Swift体验2

使用if和switch做条件判断,使用for-in,for,while,do-while做循环 操作。括号中的条件或循环变量是可选的。括号的身体是必需的。

13330
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.5节栈布局之-fomit-frame-pointer编译选项

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

8220

扫码关注云+社区

领取腾讯云代金券