前言

• 个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
• 个人刷题练习系列专栏：个人CSDN牛客刷题专栏。 题目来自：牛客/题库 / 在线编程 / 剑指offer：
  

目录

• 前言
• 问题描述：
• 举例：
• 解法思路：
• 代码结果：
• 结束语

问题描述：

• 用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
• 数据范围： n≤1000
  要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是O(1)

举例：

//示例1：
//输入：
["PSH1","PSH2","POP","POP"]
//返回值：
1,2
/*
说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2
*/
//==========================
//示例2：
//输入：
["PSH2","POP","PSH1","POP"]
//返回值：
2,1

解法思路：

• 思路：先考虑栈结构，类似一个水桶，先进的元素再最下面；如果说像队列一样，先进的元素最先出去，也就是相当于将栈翻一翻，将水桶的水倒进另一个水桶。因此考虑使用栈，以及倒置栈。
• 入栈操作：正常入栈1，同时将栈1倒置，重置栈2；
• 出栈操作：从栈2中弹出一个元素，同时使用栈2倒置，重置栈1

代码结果：

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param node int整型 * @return 无** C语言声明定义全局变量请加上static，防止重复定义*/
static int stack1[1000];
static int top1=0;
static int stack2[1000];
static int top2=0;
void push(int node ) {// write code here//先入栈stack1stack1[top1++]=node;//将stack1倒入stack2top2=0;for(int i=0;istack2[top2++]=stack1[top1-1-i];}
}
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param 无 * @return int整型*/
int pop() {// write code here//先从栈2出栈int ans=stack2[top2-1];top2--;//倒置栈top1=0;for(int i=0;i