利用栈实现队列(C语言实现)

在上一篇优化后队列的实现(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      出队列了
请按任意键继续. . .

如有错误,望不吝指出。

利用栈实现队列(C语言实现),布布扣,bubuko.com

利用栈实现队列(C语言实现)

上一篇:Android瀑布流,解决oom


下一篇:Swift百万线程攻破单例(Singleton)模式