栈与队列的相互实现

注：这里用的都是c语言，栈和队列都是我自己写的，想知道可以看我之前写的线性表综合讲述，会c++的可以直接使用库中模板。

目录

一、用两个栈实现队列

二、两个队列实现栈

---

一、用两个栈实现队列

#pragma once
#include"Stack.h"
typedef int QUD;
typedef struct Queue
{
	S in;
	S out;
}Queue;
void QueueInit(Queue*p)
{
	InitStack(&p->in);
	InitStack(&p->out);
}
void QueuePush(Queue*p, QUD n)
{
	StackPush(&p->in, n);
}
void transfer(Queue*p)//输入栈数据转输出栈
{
	if (StackEmpty(&p->out))
	{
		while (StackSize(&p->in) > 0)
		{
			StackPush(&p->out, StackTop(&p->in));
			StackPop(&p->in);
		}
	}
}
void QueuePop(Queue*p)
{
	transfer(p);
	StackPop(&p->out);
}
QUD QueueFront(Queue*p)
{
	transfer(p);
	return StackTop(&p->out);
}
QUD QueueBack(Queue*p)
{
	if (StackEmpty(&p->in))
		return p->out.base[0];
	else
		return StackTop(&p->in);
}
bool QueueEmpty(Queue*p)
{
	return StackEmpty(&p->in) && StackEmpty(&p->out);
}
QUD QueueSize(Queue*p)
{
	if (StackEmpty(&p->in))
		return StackSize(&p->out);
	else
		return StackSize(&p->in);
}
void QueueDestory(Queue*p)
{
	StackDestory(&p->in);
	StackDestory(&p->out);
}

二、两个队列实现栈

#pragma once
#include"Queue.h"
typedef int STD;
typedef struct Stack
{
	Queue q1;
	Queue q2;
}Stack;
void InitStack(Stack*p)
{
	QueueInit(&p->q1);
	QueueInit(&p->q2);
}
void StackPush(Stack*p, STD n)
{
	if (QueueEmpty(&p->q1))
		QueuePush(&p->q2, n);
	else
		QueuePush(&p->q1, n);
}
STD StackPop(Stack*p)
{
	Queue*emptyQ = &p->q1;//设置空与非空队列
	Queue*notemptyQ = &p->q2;
	if (!QueueEmpty(&p->q1))
	{
		emptyQ = &p->q2;
		notemptyQ = &p->q1;
	}
	while (QueueSize(notemptyQ)>1)
	{
		QueuePush(emptyQ, QueueFront(notemptyQ));//将队头数据转入另一队列中
		QueuePop(notemptyQ);
	}
	STD top= QueueFront(notemptyQ);
	QueuePop(notemptyQ);
	return top;
}
STD StackTop(Stack*p)
{
	if (QueueEmpty(&p->q1))
		return QueueBack(&p->q2);//队尾即为栈顶
	else
		return QueueBack(&p->q1);
}
bool StackEmpty(Stack*p)
{
	return QueueEmpty(&p->q1) && QueueEmpty(&p->q2);
}
void StackFree(Stack*p)
{
	QueueDestory(&p->q1);
	QueueDestory(&p->q2);
}

这属于数据结构的灵活运用，希望对大家能有所帮助。