数据结构深入剖析（5）

一、队列的特别实现
--用栈实现队列
实现思路：
--准备两个栈用于实现队列：InStack and OutStack
--当有新元素入队时：将其压入InStack中
--当需要出队时：
----当OutStack为空时：
1.将InStack中的元素逐一弹出并压入OutStack中
2.将OutStack的栈顶元素弹出
----当OutStack不为空时：
--直接将OutStack的栈顶元素弹出。

实现：
//SQueue.h头文件
#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_Retrive(SQueue* queue);
void* SQueue_Header(SQueue* queue);
int SQueue_Length(SQueue* queue);
#endif

//SQueue.c
#include
#include
#include "LinkStack.h"//包括栈实现头文件。
#include "SQueue.h"


typedef struct _tag_SQueue
{
    LinkStack* InStack;
    LinkStack* OutStack;
}TSQueue;
SQueue* SQueue_Create()
{
    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)
{
    SQueue_Clear(queue);
    free(queue);
}
void SQueue_Clear(SQueue* queue)
{
    TSQueue* sQueue = (TSQueue*)queue;
    if(sQueue != NULL){
        LinkStack_Clear(sQueue->InStack);
        LinkStack_Clear(sQueue->OutStack);
    }
}


int SQueue_Append(SQueue* queue,void* item)
{
    TSQueue* sQueue = (TSQueue*)queue;
    int ret = -1;
    if(sQueue != NULL){
        ret = LinkStack_Push(sQueue->InStack,item);
    }
    return ret;
}


void* SQueue_Retrive(SQueue* queue)
{
    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)
{
    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)
{
    TSQueue* sQueue = (TSQueue*)queue;
    int ret = -1;
    if(sQueue != NULL){
        ret = LinkStack_Size(sQueue->InStack) + LinkStack_Size(sQueue->OutStack);
    }
    return ret;
}