Chinaunix首页 | 论坛 | 博客
  • 博客访问: 320899
  • 博文数量: 64
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 1972
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-31 21:53
个人简介

文明之精神,野蛮之体魄。

文章分类
文章存档

2015年(4)

2013年(60)

我的朋友

分类: C/C++

2013-09-27 22:10:20

一、队列的特别实现
--用栈实现队列
实现思路:
--准备两个栈用于实现队列: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;
}
阅读(2331) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~