不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 396|回复: 0

[c/c++] [C数据结构]二个栈实现队列(复用单链表和链式栈)

[复制链接]
j2cat 发表于 2018-1-6 19:29:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
SQueue.h
  1. #ifndef _S_QUEUE_H_
  2. #define _S_QUEUE_H_

  3. typedef void SQueue;

  4. SQueue* SQueue_Create(void);

  5. void SQueue_Destroy(SQueue* queue);

  6. void SQueue_Clear(SQueue* queue);

  7. int SQueue_Append(SQueue* queue, void* item);

  8. void* SQueue_Retrieve(SQueue* queue);

  9. void* SQueue_Header(SQueue* queue);

  10. int SQueue_Size(SQueue* queue);


  11. #endif
复制代码
SQueue.c
  1. /*
  2. *特殊队列, 2个栈实现的队列.1输入栈,1输出栈
  3. *复用单链表和链式栈
  4. */
  5. #include "linklist.h"
  6. #include "LinkStack.h"
  7. #include "SQueue.h"
  8. #include <malloc.h>

  9. typedef struct _tag_SQueue {
  10.         LinkStack* iStack; //输入栈
  11.         LinkStack* oStack; //输出栈
  12. }TSQueue;

  13. SQueue* SQueue_Create(void) {
  14.         TSQueue* ret = (TSQueue*)malloc(sizeof(TSQueue));
  15.         if (NULL != ret) {
  16.                 ret->iStack = LinkStack_Create(); //创建栈
  17.                 ret->oStack = LinkStack_Create();
  18.                 if (NULL == ret->iStack || NULL == ret->oStack) {
  19.                         LinkStack_Destroy(ret->iStack);
  20.                         LinkStack_Destroy(ret->oStack);
  21.                         free(ret);
  22.                         ret = NULL;
  23.                 }
  24.         }
  25.         return ret;
  26. }

  27. void SQueue_Destroy(SQueue* queue) {
  28.         if (NULL != queue) {
  29.                 SQueue_Clear(queue);
  30.                 free(queue);
  31.         }
  32. }

  33. void SQueue_Clear(SQueue* queue) {
  34.         TSQueue* sQueue = (TSQueue*)queue;
  35.         if (NULL != sQueue) {
  36.                 LinkStack_Clear(sQueue->iStack);
  37.                 LinkStack_Clear(sQueue->oStack);
  38.         }
  39. }

  40. int SQueue_Append(SQueue* queue, void* item) {
  41.         TSQueue* sQueue = (TSQueue*)queue;
  42.         int ret = (NULL != sQueue && NULL != item);
  43.         if (ret) {
  44.                 ret = LinkStack_Push(sQueue->iStack, item); //把数据压入istack栈
  45.         }
  46.         return ret;
  47. }

  48. void* SQueue_Retrieve(SQueue* queue) {
  49.         TSQueue* sQueue = (TSQueue*)queue;
  50.         void* ret = NULL;
  51.         if (NULL != sQueue) {
  52.                 if (0 == LinkStack_Size(sQueue->oStack)) { //ostack为空栈时,把istack里的元素弹出压入ostack
  53.                         while (0 < LinkStack_Size(sQueue->iStack)) {
  54.                                 LinkStack_Push(sQueue->oStack, LinkStack_Pop(sQueue->iStack));
  55.                         }
  56.                 }
  57.                 ret = LinkStack_Pop(sQueue->oStack);
  58.         }
  59.         return ret;
  60. }

  61. void* SQueue_Header(SQueue* queue) {
  62.         TSQueue* sQueue = (TSQueue*)queue;
  63.         void* ret = NULL;
  64.         if (NULL != sQueue) {
  65.                 if (0 == LinkStack_Size(sQueue->oStack)) {
  66.                         while (0 < LinkStack_Size(sQueue->iStack)) {
  67.                                 LinkStack_Push(sQueue->oStack, LinkStack_Pop(sQueue->iStack));
  68.                         }
  69.                 }
  70.                 ret = LinkStack_Top(sQueue->oStack);
  71.         }
  72.         return ret;
  73. }

  74. int SQueue_Size(SQueue* queue) {
  75.         TSQueue* sQueue = (TSQueue*)queue;
  76.         int ret = -1;
  77.         if (NULL != sQueue) {
  78.                 ret = LinkStack_Size(sQueue->iStack) + LinkStack_Size(sQueue->oStack);
  79.         }
  80.         return ret;
  81. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-9-19 05:29

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表