用两个栈实现队列

实现了简单的栈和队列之后，我们可以考虑玩点花样：怎么用两个栈实现一个队列的功能

用两个栈实现队列说起来也不是很困难，我们根据栈的特性：后进先出，也就是先进后出，相当于把数据倒过来了，这样我们用两个栈颠倒了两次，也就是实现了队列的功能：先进先出。
对这个用两个栈S1和S2形成的队列进行操作时，我们该怎么样操作呢？
数据入队列：数据录入相当简单，直接把数据录入栈S1即可。
数据出队列：数据出队相对麻烦，我们把栈S1的数据依次录入栈S2,弹出栈S1，这样S2的内容就符合出队要求了。
只需要对S2进行出栈操作就行。
思路：入栈进S1，出栈由S2完成，如果S2无数据，把S1的数据压入S2。
工具：VS2013
语言：C
代码如下：
头文件QueueByTwoStack.h

#pragma once
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

typedef int DataType;

typedef struct Stack
{
	DataType* data;
	int top;		// 栈顶
	int capacity;  // 容量
}Stack;

// 两个栈实现一个队列
typedef struct QueueByTwoStack
{
	Stack s1;
	Stack s2;
}QueueByTwoStack;

void QueueInit(QueueByTwoStack* pq);
void QueueDestory(QueueByTwoStack* pq);
void QueuePush(QueueByTwoStack* pq, DataType x);
void QueuePop(QueueByTwoStack* pq);
DataType QueueFront(QueueByTwoStack* pq);
int QueueEmpty(QueueByTwoStack* pq);
int QueueSize(QueueByTwoStack* pq);
void TestQueue();




void StackInit(Stack* ps);
void StackDestory(Stack* ps);

void StackPush(Stack* ps, DataType x);
void StackPop(Stack* ps);
DataType StackTop(Stack* ps);
int StackEmpty(Stack* ps);
int StackSize(Stack* ps);

源文件Stack.c

#include "QueueByTwoStack.h"
void StackInit(Stack* ps)
{
	assert(ps);
	ps->data = (DataType*)malloc(sizeof(Stack)* 3);
	ps->capacity = 3;
	ps->top = 0;
}
void StackDestory(Stack* ps)
{
	assert(ps);
	if (ps->data)
		free(ps->data);
	ps->capacity = 0;
	ps->top = 0;
}
void StackPush(Stack* ps, DataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ps->data = (DataType*)realloc(ps->data, sizeof(Stack)*(ps->capacity * 2));
		if (ps->data)
			ps->capacity *= 2;
		else perror("capacity realloc");
	}
	*(ps->data + ps->top++) = x;
}
void StackPop(Stack* ps)
{
	assert(ps&&ps->data);
	if (ps->top)
		ps->top--;
}
DataType StackTop(Stack* ps)
{
	assert(ps&&ps->data&&ps->top);
	return *(ps->data + ps->top - 1);
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top != 0;
}
int StackSize(Stack* ps)
{
	assert(ps&&ps->data);
	return ps->top;
}

QueueByTwoStack.c

#include"QueueByTwoStack.h"
void QueueInit(QueueByTwoStack* pq)
{
	assert(pq);
	StackInit(&pq->s1);
	StackInit(&pq->s2);
}
void QueueDestory(QueueByTwoStack* pq)
{
	assert(pq);
	StackDestory(&pq->s1);
	StackDestory(&pq->s2);
}
void QueuePush(QueueByTwoStack* pq, DataType x)
{
	assert(pq);
	StackPush(&pq->s1, x);
}
void QueuePop(QueueByTwoStack* pq)
{
	assert(pq);
	if (StackEmpty(&pq->s2))
		StackPop((&pq->s2));
	else if (StackEmpty(&pq->s1))
	{
		while (StackEmpty(&pq->s1))
		{
			StackPush(&pq->s2, StackTop(&pq->s1));
			StackPop(&pq->s1);
		}
	}
}
DataType QueueFront(QueueByTwoStack* pq)
{
	assert(pq);
	if (StackEmpty(&pq->s2) == 0)
	{
		while (StackEmpty(&pq->s1))
		{
			StackPush(&pq->s2, StackTop(&pq->s1));
			StackPop(&pq->s1);
		}
	}
	return StackTop(&pq->s2);
}
int QueueEmpty(QueueByTwoStack* pq)
{
	assert(pq);
	return StackEmpty(&pq->s1) || StackEmpty(&pq->s1);
}
int QueueSize(QueueByTwoStack* pq)
{
	assert(pq);
	return StackSize(&pq->s1) + StackSize(&pq->s2);
}
void TestQueue()
{
	QueueByTwoStack q;
	int i;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	printf("Size:%d\n", QueueSize(&q));
	printf("empty:%d\n", QueueEmpty(&q));
	for (i = 0; i < 6; i++)
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\nSize:%d", QueueSize(&q));
	printf("\nempty:%d", QueueEmpty(&q));
	QueueDestory(&q);
}

Test.c

#include"QueueByTwoStack.h"
#include<windows.h>
int main()
{
	TestQueue();
	system("pause");
	return 0;
}