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

两个栈实现一个队列

2024-07-03 04:33:44   237人阅读

转载请注明出处：http://blog.csdn.net/ns_code/article/details/25068625

    剑指offer上的第七题，之前在Cracking the Coding interview上做过该题，这次把原来的程序搬了过来，并根据九度OJ的测试系统写了测试代码，在九度OJ上AC。

时间限制：1 秒

内存限制：128 兆


题目描述：

用两个栈来实现一个队列，完成队列的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
  AC代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

typedef struct Node
{
	int data;
	struct Node *pNext;
}NODE,*PNODE;

typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK,*PSTACK;

PSTACK create_stack();
void push_stack(PSTACK,int);
void traverse_stack(PSTACK);
bool pop_stack(PSTACK,int *);
bool is_empty(PSTACK);
void clear_stack(PSTACK);
void enter_Queue(PSTACK,int);
bool delete_Queue(PSTACK,PSTACK,int *);

int main()
{	
	int n;		//保存操纵的个数
	int data;	//保存输入的要push的元素
	int pData;	//保存pop出来的元素
	char *push = "PUSH";
	char *pop = "POP";
	char input[5];
	int data_pop;

	//创建两个空栈
	PSTACK pS1 = create_stack();
	PSTACK pS2 = create_stack();
	scanf("%d",&n);
	while(n-->0)
	{
		scanf("%s",input);
		if(strcmp(input,push) == 0)
		{
			scanf("%d",&data);
			enter_Queue(pS1,data);
		}
		if(strcmp(input,pop) == 0)
		{
			if(delete_Queue(pS1,pS2,&pData))
				printf("%d\n",pData);
			else
				printf("-1\n");
		}
	}

	clear_stack(pS1);
	clear_stack(pS2);
	return 0;
}

/*
创建一个空栈,并返回指向该栈的指针
*/
PSTACK create_stack()
{
	PSTACK pS = (PSTACK)malloc(sizeof(STACK));
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if(NULL==pS || NULL==pS->pTop)
	{
	   printf("malloc failed");
	   exit(-1);
	}	
	else
	{
	   pS->pBottom = pS->pTop;
	   pS->pBottom->pNext = NULL;
	}
	
	return pS;
}

/*
判断该栈是否为空
*/
bool is_empty(PSTACK pS)
{
	if(pS->pTop == pS->pBottom)
	   return true;
    else
	   return false;
}

/*
向pS指针指向的栈中压入数据val
*/
void push_stack(PSTACK pS,int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL==pNew)
	{
	   printf("malloc failed");
	   exit(-1);
	}	
	else
	{
	   pNew->data = http://www.mamicode.com/val;>
/**************************************************************
    Problem: 1512
    User: mmc_maodun
    Language: C
    Result: Accepted
    Time:80 ms
    Memory:1836 kb
****************************************************************/


联系
我们