一、队列的特别实现
--用栈实现队列
实现思路:
--准备两个栈用于实现队列: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;
}
阅读(2341) | 评论(0) | 转发(2) |