程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 利用棧實現隊列(C語言實現)

利用棧實現隊列(C語言實現)

編輯:關於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 
#include 

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      出隊列了
請按任意鍵繼續. . .

如有錯誤,望不吝指出。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved