用兩個棧實現佇列（c語言程式碼）

棧的程式碼詳見：stack的陣列實現和測試

佇列的陣列實現：佇列的陣列實現（c語言程式碼）

思想：棧 先進後出，佇列先進先出。

/*利用兩個棧實現佇列*/

typedef struct QueueStack
{
	stack* st1;
	stack* st2;
}queuestack;

佇列尾部新增新元素：st1的棧頂push新元素（因此st1的棧頂是最新寫到佇列的元素）；

佇列頭部刪除元素：

1. 如果棧st2中沒元素，則棧st1中棧底是最早寫入元素，將棧st1中的元素依次pop出來，寫入st2中，則此時，棧st2的棧頂元素是最早寫入佇列元素，棧st2的棧底是最近寫入元素；

2.如果棧st2中有元素，則由1可以知道，st2的棧頂是最早寫入佇列元素，刪除st2的棧頂元素即可。

queue_st.h

#ifndef  __QUEUEST_H_
#define  __QUEUEST_H_

/*利用兩個棧實現佇列*/

typedef struct QueueStack
{
	stack* st1;
	stack* st2;
}queuestack;

queuestack* CreateQueueWithStack();
void DeleteQS(queuestack* qs);
int AppendTail(queuestack* qs);
int DeleteHead(queuestack* qs);
void Qs_showdata_int(queuestack* qs);
#endif

 

queue_st.c

#include "public.h"
#include "stack.h"
#include "queue_st.h"


queuestack* CreateQueueWithStack()\
{
	queuestack* qs = NULL;
	qs = (queuestack*)malloc(sizeof(queuestack));
	if(NULL == qs)
	{
		printf("Malloc erron.\n");
		return NULL;
	}
	qs->st1 = createStack();
	qs->st2 = createStack();
	return qs;
}
void DeleteQS(queuestack* qs)
{
	Destroy(qs->st1);
	Destroy(qs->st2);
}
void Qs_showdata_int(queuestack* qs)
{
	int i = 0;


	if(!StackIsEmpty(qs->st2))
	{
		printf("st2 has:\n");
		for(i = qs->st2->top -1 ; i >= 0; --i)
		{
			printf("%d	", qs->st2->data[i]);
		}
		printf("\n");
	}
	if(!StackIsEmpty(qs->st1))
	{
		printf("st1 has:\n");
		for(i = 0 ; i < qs->st1->top; ++i)
		{
			printf("%d	", qs->st1->data[i]);
		}
		printf("\n");
	}

	printf("---------------------------\n\n");
}
int AppendTail(queuestack* qs, DataType data)
{
	if(StackIsFull(qs->st1))
	{
		printf("Queue which is completed with two stack is FULLLLL...\n");
		return -1;
	}
	push(qs->st1, data);
	return 0;
}

int DeleteHead(queuestack* qs)
{
	DataType top_val;
	if(!StackIsEmpty(qs->st2))
	{
		pop(qs->st2);
	}
	else
	{
		if(!StackIsEmpty(qs->st1))
		{
			while(!StackIsEmpty(qs->st1))
			{
				top_val = GetTop(qs->st1);
				push(qs->st2, top_val);
				pop(qs->st1);
			}
			pop(qs->st2);
		}
		else
		{
			printf("the QueusStack is empty and has no element to delete.\n");
			return -1;
		}
	}
	return 0;
}

test.c

#include"public.h"
#include"stack.h"
#include"queue.h"
#include "queue_st.h"



#if 1
int main()
{
	queuestack *qs = NULL;
	int i = 0,size = 0,j = 0;

	qs = CreateQueueWithStack();

	size = 101;
	for(i = 0; i < size; ++i)
	{
		AppendTail(qs, (i+1));
	}
	printf("tail append 100 numbers.\n");
	Qs_showdata_int(qs);

	size = 50;
	for(j = 0; j < size; ++j)
	{
		DeleteHead(qs);
	}
	printf("head delete 50 numbers.\n");
	Qs_showdata_int(qs);

	size = 30;
	for(j = 0; j < size; ++j)
	{
		AppendTail(qs, (101+j));
	}
	printf("tail append 30 numbers\n");
	Qs_showdata_int(qs);
	
	size = 20;
	for(j = 0; j < size; ++j)
	{
		DeleteHead(qs);
	}
	printf("head delete 20 numbers.\n");
	Qs_showdata_int(qs);

	size = 30;
	for(j = 0; j < size; ++j)
	{
		AppendTail(qs, (131+j));
	}
	printf("tail append 30 numbers\n");
	Qs_showdata_int(qs);

	size = 92;
	for(j = 0; j < size; ++j)
	{
		DeleteHead(qs);
	}
	printf("head delete 90 numbers.\n");
	Qs_showdata_int(qs);
	return 0;
}
#endif