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

两个栈实现一个队列

2024-07-13 04:39:56   231人阅读

原理：

假设有两个栈分别叫stack1，stack2。那么入队操作就是向stack1中push元素，出队操作就是将stack1中的所有元素pop出来，然后push到stack2中，对stack2进行pop操作。


题目：
题目描述：

用两个栈来实现一个队列，完成队列的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 
实现：
/*********************************
两个栈实现队列
by Rowandjj
2014/7/21
*********************************/
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *next;
}Node,*pNode;
typedef struct _STACK_
{
	pNode head;
	int size;
}Stack,*pStack;
typedef struct _QUEUE_
{
	Stack s1;
	Stack s2;
}Queue,*pQueue;
void InitStack(pStack ps)
{
	ps->head = (pNode)malloc(sizeof(Node));
	if(!ps->head)
	{
		exit(-1);
	}
	ps->size = 0;
	ps->head->next = NULL;
}
void push(pStack ps, int data)
{
	if(ps == NULL)
	{
		return;
	}
	pNode pNew = (pNode)malloc(sizeof(Node));
	if(!pNew)
	{
		return;
	}
	pNew->data = http://www.mamicode.com/data;>


联系
我们