数据结构之队列的特别实现

た入场券 2022-05-31 07:52 169阅读 0赞

队列的特别实现

上两节讲的队列实现方式确实提高了顺序队列和链式队列的效率，可是实现过程还是比较复杂。这样就有可能导致错误，其实有即能复用之前的代码，又比较高效的队列实现算法的。

那就是用栈来实现，可能有人要说了，栈不是后入先出的吗？怎么可能实现栈呢？大家考虑一下，如果使用两个栈呢？如下图：

![SouthEast][]

大家是不是明白一点了呢？

下面做个小结：

1.组合使用两个栈的“后进先出”可以实现队列的“先进先出”；  
2.两个栈实现队列的方法复用栈数据结构，实现过程简单且高效；  
3.两个栈实现的队列其操作的时间复杂度能够达到O(1)。

**栈实现队列方案**  
实现思路：  
1.准备两个栈用于实现队列：inStack和outStack；

2.当有新元素入队时：将其压入inStack中；

3.当需要出队时：

3.1.当outStack为空时：

3.1.1.将inStack中的元素逐一弹出并压入outStack中；

3.1.2.将outStack的栈顶元素弹出；

3.2.当outStack不为空时：

3.2.1.直接将outStack的栈顶元素弹出。

![SouthEast 1][]

下面看一下具体的实现代码，栈部分参考：[栈的定义与实现][Link 1]

创建队列

// 定义队列结构体
    typedef struct _tag_SQueue
    {
        LinkStack* inStack;
        LinkStack* outStack;
    } TSQueue;
    // 创建队列
    SQueue* SQueue_Create() // O(1)
    {
    	  // 定义队列结构体变量，并申请内存
        TSQueue* ret = (TSQueue*)malloc(sizeof(TSQueue));
        // 内存申请成功
        if( ret != NULL )
        {
        		// 创建入栈或出栈
            ret->inStack = LinkStack_Create();
            ret->outStack = LinkStack_Create();
            // 创建栈失败，销毁栈，释放内存
            if( (ret->inStack == NULL) || (ret->outStack == NULL) )
            {
                LinkStack_Destroy(ret->inStack);
                LinkStack_Destroy(ret->outStack);
                
                free(ret);
                
                ret = NULL;
            }
        }
        // 返回队列地址
        return ret;
    }

销毁队列、清空队列

// 销毁队列
    void SQueue_Destroy(SQueue* queue) // O(n)
    {	
    	  // 清空队列，释放内存
        SQueue_Clear(queue);
        free(queue);
    }
    // 清空队列
    void SQueue_Clear(SQueue* queue) // O(n)
    {
    	  // 定义队列结构体变量，并强制转换入口参数
        TSQueue* sQueue = (TSQueue*)queue;
        // 参数合法，清空两个入栈和出栈
        if( sQueue != NULL )
        {
            LinkStack_Clear(sQueue->inStack);
            LinkStack_Clear(sQueue->outStack);
        }
    }

入队代码

// 入队
    int SQueue_Append(SQueue* queue, void* item) // O(1)
    {
    	  // 定义队列结构体变量，并强制转换入口参数
        TSQueue* sQueue = (TSQueue*)queue;
        
        // 参数合法，将掺入元素压入栈内
        if( sQueue != NULL )
        {
            LinkStack_Push(sQueue->inStack, item);
        }
    }

出队

// 出队
    void* SQueue_Retrieve(SQueue* queue) // O(1)
    {
    	  // 定义队列结构体变量，并强制转换入口参数
        TSQueue* sQueue = (TSQueue*)queue;
        void* ret = NULL;
        
        // 参数合法，将掺入元素压入栈内
        if( sQueue != NULL )
        {
        	  // 出栈元素为空
            if( LinkStack_Size(sQueue->outStack) == 0 )
            {
            	  // 将入栈所有元素压入出栈中
                while( LinkStack_Size(sQueue->inStack) > 0 )
                {
                    LinkStack_Push(sQueue->outStack, LinkStack_Pop(sQueue->inStack));
                }
            }
            // 返回弹出的出栈栈顶元素
            ret = LinkStack_Pop(sQueue->outStack);
        }
        
        return ret;
    }

获取队首元素

// 获取队头元素
    void* SQueue_Header(SQueue* queue) // O(1)
    {
    	  // 定义队列结构体变量，并强制转换入口参数
        TSQueue* sQueue = (TSQueue*)queue;
        void* ret = NULL;
        
        // 参数合法
        if( sQueue != NULL )
        {
        	  // 出栈元素为空
            if( LinkStack_Size(sQueue->outStack) == 0 )
            {
            	  // 将入栈所有元素压入出栈中
                while( LinkStack_Size(sQueue->inStack) > 0 )
                {
                    LinkStack_Push(sQueue->outStack, LinkStack_Pop(sQueue->inStack));
                }
            }
            // 返回出栈栈顶元素
            ret = LinkStack_Top(sQueue->outStack);
        }
        
        return ret;
    }

获取队长度

// 获取队长度
    int SQueue_Length(SQueue* queue) // O(1)
    {
    	  // 定义队列结构体变量，并强制转换入口参数
        TSQueue* sQueue = (TSQueue*)queue;
        int ret = -1;
        // 参数合法，返回入栈和出栈的长度和
        if( sQueue != NULL )
        {
            ret = LinkStack_Size(sQueue->inStack) + LinkStack_Size(sQueue->outStack);
        }
        
        return ret;
    }

头文件

#ifndef _SQUEUE_H_
    #define _SQUEUE_H_
    
    typedef void SQueue;
    // 创建队列
    SQueue* SQueue_Create();
    // 销毁队列
    void SQueue_Destroy(SQueue* queue);
    // 清空队列
    void SQueue_Clear(SQueue* queue);
    // 入队
    int SQueue_Append(SQueue* queue, void* item);
    // 出队
    void* SQueue_Retrieve(SQueue* queue);
    // 获取队头元素
    void* SQueue_Header(SQueue* queue);
    // 获取队长度
    int SQueue_Length(SQueue* queue);
    
    #endif

测试代码

#include <stdio.h>
    #include <stdlib.h>
    #include "SQueue.h"
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    int main(int argc, char *argv[]) 
    {
        SQueue* queue = SQueue_Create();
        int a[10] = {0};
        int i = 0;
        
        for(i=0; i<10; i++)
        {
            a[i] = i + 1;
            
            SQueue_Append(queue, a + i);
        }
        
        printf("Header: %d\n", *(int*)SQueue_Header(queue));
        printf("Length: %d\n", SQueue_Length(queue));
        
        for(i=0; i<5; i++)
        {
            printf("Retrieve: %d\n", *(int*)SQueue_Retrieve(queue));
        }
        
        printf("Header: %d\n", *(int*)SQueue_Header(queue));
        printf("Length: %d\n", SQueue_Length(queue));
        
        for(i=0; i<10; i++)
        {
            a[i] = i + 1;
            
            SQueue_Append(queue, a + i);
        }
        
        while( SQueue_Length(queue) > 0 )
        {
            printf("Retrieve: %d\n", *(int*)SQueue_Retrieve(queue));
        }
        
        SQueue_Destroy(queue);
        
    	return 0;
    }

至此，队列也就介绍完了。最后上传一下整体代码链接： [双栈实现队列C实现代码][C]

[SouthEast]: /images/20220531/85fb45df50314b2ab49e5005d15a880b.png
[SouthEast 1]: /images/20220531/25d5af53be104b96bb1cea95d4820469.png
[Link 1]: http://blog.csdn.net/u014754841/article/details/79261485
[C]: http://download.csdn.net/download/u014754841/10248830