在上一篇优化后队列的实现(C语言实现) 中，虽然我们对队列的时间复杂度进行了优化，但是却让代码的可读性变差了，代码显得略微臃肿（当然，这些话你看看就好，主要是为了奉承这篇博文的）。
这里主要实现的是：利用栈来实现队列
基本思路：
1，创建两个栈
2，两个栈合并起来组装成一个队列，分别取名为instack,outstack，用于进队列，出队列
3，比如有1,2,3,4,5 需要进入队列，先将这一串数压入instack栈中，假设压入顺序为1,2,3,4,5（1为栈底），再将instack中的数据移入outstack中，出栈顺序为：5,4,3,2,1. 那么入outsatck的时候，进栈的顺序同样为 ： 5,4,3,2,1（5为栈底），那么出outstack的时候，顺序即为：1,2,3,4,5 这样就做到了入是1,2,3,4,5 出也是1,2,3,4,5 这样就跟队列是一样一样的了。
代码实现思路：
实现思路
准备两个栈用于实现队列：inStack和outStack
当有新元素入队时： ：将其压入 将其压入inStack中
当需要出队时：
当outStack为空时：
1. 将inStack中的元素逐一弹出并压入outStack中
2. 将outStack的栈顶元素弹出
当outStack不为空时：
– 直接将outStack的栈顶元素弹出
源代码入下：
这里用到了栈的代码，具体可以参阅：栈的实现与操作(C语言实现)
头文件：
#ifndef _SPQueue_H_ #define _SPQueue_H_ typedef void SPQueue; SPQueue* SPQueue_Create(); void SPQueue_Destroy(SPQueue* queue); void SPQueue_Clear(SPQueue* queue); int SPQueue_Append(SPQueue* queue, void* item); void* SPQueue_Retrieve(SPQueue* queue); void* SPQueue_Header(SPQueue* queue); int SPQueue_Length(SPQueue* queue); #endif
源文件：
// 栈实现队列.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "SPQueue.h"
#include "LinkStack.h"
#include <malloc.h>
#include <stdlib.h>
typedef struct
{
LinkStack * instack;
LinkStack * outstack;
} TSPQueue;
int _tmain(int argc, _TCHAR* argv[])
{
SPQueue* queue = SPQueue_Create();
int a[10] = {0};
int i = 0;
for(i=0; i<10; i++)
{
a[i] = i + 1;
SPQueue_Append(queue, a + i);
}
printf("第一次进队列：");
printf("Header: %d\n", *(int*)SPQueue_Header(queue));
printf("Length: %d\n", SPQueue_Length(queue));
for(i=0; i<5; i++)
{
printf("%d\t出队列了\n", *(int*)SPQueue_Retrieve(queue));
}
printf("\n第二次进队列：\n");
printf("Header: %d\n", *(int*)SPQueue_Header(queue));
printf("Length: %d\n", SPQueue_Length(queue));
for(i=0; i<10; i++) //继续尾加10个节点
{
a[i] = i + 1;
SPQueue_Append(queue, a + i);
}
while( SPQueue_Length(queue) > 0 )
{
printf("%d\t出队列了\n", *(int*)SPQueue_Retrieve(queue));
}
SPQueue_Destroy(queue);
system("pause");
return 0;
}
//创建
SPQueue* SPQueue_Create()
{
TSPQueue* ret = (TSPQueue*)malloc(sizeof(TSPQueue));
if (NULL != ret)
{
ret->instack = LinkStack_Create();
ret->outstack = LinkStack_Create();
if ((NULL == ret->instack) && (NULL == ret->outstack))
{
LinkStack_Destroy(ret->instack);
LinkStack_Destroy(ret->outstack);
free(ret);
ret = NULL;
}
}
return ret;
}
//销毁
void SPQueue_Destroy(SPQueue* queue)
{
SPQueue_Clear(queue);
free(queue);
}
//清空
void SPQueue_Clear(SPQueue* queue)
{
TSPQueue* SPQueue = (TSPQueue*)queue;
if (NULL != SPQueue)
{
LinkStack_Clear(SPQueue->instack);
LinkStack_Clear(SPQueue->outstack);
}
}
//尾加
int SPQueue_Append(SPQueue* queue, void* item)
{
TSPQueue* SPQueue = (TSPQueue*)queue;
int ret = 0;
if (NULL != SPQueue)
{
ret = LinkStack_Push(SPQueue->instack,item);
}
return ret;
}
//删除头部
void* SPQueue_Retrieve(SPQueue* queue)
{
TSPQueue* SPQueue = (TSPQueue*)queue;
void * ret = NULL;
if (NULL != SPQueue)
{
//当outstack长度为0时，把instack中的数据移入outstack
if (LinkStack_Size(SPQueue->outstack) == 0)
{
while (LinkStack_Size(SPQueue->instack) > 0)
{
LinkStack_Push(SPQueue->outstack,LinkStack_Pop(SPQueue->instack));
}
}
//取出outstack的栈顶
ret = LinkStack_Pop(SPQueue->outstack);
}
return ret ;
}
//获得头部
void* SPQueue_Header(SPQueue* queue)
{
TSPQueue* SPQueue = (TSPQueue*)queue;
void * ret = NULL;
if (NULL != SPQueue)
{
if (LinkStack_Size(SPQueue->outstack) == 0)
{
while (LinkStack_Size(SPQueue->instack) > 0)
{
LinkStack_Push(SPQueue->outstack,LinkStack_Pop(SPQueue->instack));
}
}
ret = LinkStack_Top(SPQueue->outstack);
}
return ret ;
}
//长度
int SPQueue_Length(SPQueue* queue)
{
TSPQueue* SPQueue = (TSPQueue*)queue;
int ret = 0;
if (NULL != SPQueue)
{
ret = LinkStack_Size(SPQueue->instack) + LinkStack_Size(SPQueue->outstack);
}
return ret;
}
运行结果：
第一次进队列：Header: 1 Length: 10 1 出队列了 2 出队列了 3 出队列了 4 出队列了 5 出队列了 第二次进队列： Header: 6 Length: 5 6 出队列了 7 出队列了 8 出队列了 9 出队列了 10 出队列了 1 出队列了 2 出队列了 3 出队列了 4 出队列了 5 出队列了 6 出队列了 7 出队列了 8 出队列了 9 出队列了 10 出队列了 请按任意键继续. . .
如有错误，望不吝指出。