不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 280|回复: 0

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

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

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

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

x
QStack.h
  1. #ifndef _Q_STACK_H_
  2. #define _Q_STACK_H_

  3. typedef void QStack;

  4. QStack* QStack_Create(void);

  5. void QStack_Destroy(QStack* stack);

  6. void QStack_Clear(QStack* stack);

  7. int QStack_Size(QStack* stack);

  8. int QStack_Push(QStack* stack, void* item);

  9. void* QStack_Pop(QStack* stack);

  10. void* QStack_Top(QStack* stack);


  11. #endif
复制代码
QStack.c
  1. /*
  2. * 复用链式队列源码
  3. * 2个队列实现一个栈
  4. * 实现思路:
  5. * 队列是先进先出的,所以保证其中一个队列为空.
  6. * 每次出栈 就从其中一个队列push到另一个队列,最后一个元素则直接Push出来;
  7. */
  8. #include "LinkQueue.h"
  9. #include "QStack.h"
  10. #include <malloc.h>

  11. typedef struct _tag_QStack {
  12.         LinkQueue* Astack;
  13.         LinkQueue* Bstack;
  14. }TQStack;

  15. QStack* QStack_Create(void) {
  16.         TQStack* qstack = (TQStack*)malloc(sizeof(TQStack));
  17.         if (NULL != qstack) {
  18.                 qstack->Astack = LinkQueue_Create();
  19.                 qstack->Bstack = LinkQueue_Create();
  20.                 if (NULL == qstack->Astack || NULL == qstack->Bstack) {
  21.                         free(qstack->Astack);
  22.                         free(qstack->Bstack);
  23.                         free(qstack);
  24.                         qstack = NULL;
  25.                 }
  26.         }
  27.         return qstack;
  28. }

  29. void QStack_Destroy(QStack* stack) {
  30.         QStack_Clear(stack);
  31.         free(stack);
  32. }

  33. void QStack_Clear(QStack* stack) {
  34.         TQStack* qstack = (TQStack*)stack;
  35.         LinkQueue_Clear(qstack->Astack);
  36.         LinkQueue_Clear(qstack->Bstack);
  37. }

  38. int QStack_Size(QStack* stack) {
  39.         TQStack* qstack = (TQStack*)stack;
  40.         return LinkQueue_Length(qstack->Astack) + LinkQueue_Length(qstack->Bstack);
  41. }

  42. int QStack_Push(QStack* stack, void* item) {
  43.         TQStack* qstack = (TQStack*)stack;
  44.         int ret = (NULL != qstack && NULL != item);
  45.         if (ret) {
  46.                 ret = LinkQueue_Append(qstack->Astack, item);
  47.         }
  48.         return ret;
  49. }

  50. void* QStack_Pop(QStack* stack) {
  51.         TQStack* qstack = (TQStack*)stack;
  52.         void* ret = NULL;
  53.         if (NULL != qstack) {
  54.                 if (0 == LinkQueue_Length(qstack->Bstack)) {
  55.                         while (1 < LinkQueue_Length(qstack->Astack)) {
  56.                                 LinkQueue_Append(qstack->Bstack, LinkQueue_Retrieve(qstack->Astack));
  57.                         }
  58.                         ret = LinkQueue_Retrieve(qstack->Astack);
  59.                 }
  60.                 else if (0 == LinkQueue_Length(qstack->Astack)) {
  61.                         while (1 < LinkQueue_Length(qstack->Bstack)) {
  62.                                 LinkQueue_Append(qstack->Astack, LinkQueue_Retrieve(qstack->Bstack));
  63.                         }
  64.                         ret = LinkQueue_Retrieve(qstack->Bstack);
  65.                 }

  66.         }
  67.         return ret;
  68. }

  69. void* QStack_Top(QStack* stack) {
  70.         TQStack* qstack = (TQStack*)stack;
  71.         void* ret = NULL;
  72.         if (NULL != qstack) {
  73.                 if (0 == LinkQueue_Length(qstack->Bstack)) {
  74.                         while (1 < LinkQueue_Length(qstack->Astack)) {
  75.                                 LinkQueue_Append(qstack->Bstack, LinkQueue_Retrieve(qstack->Astack));
  76.                         }
  77.                         ret = LinkQueue_Header(qstack->Astack);
  78.                         LinkQueue_Append(qstack->Bstack, LinkQueue_Retrieve(qstack->Astack));
  79.                 }
  80.                 else if (0 == LinkQueue_Length(qstack->Astack)) {
  81.                         while (1 < LinkQueue_Length(qstack->Bstack)) {
  82.                                 LinkQueue_Append(qstack->Astack, LinkQueue_Retrieve(qstack->Bstack));
  83.                         }
  84.                         ret = LinkQueue_Header(qstack->Bstack);
  85.                         LinkQueue_Append(qstack->Bstack, LinkQueue_Retrieve(qstack->Bstack));
  86.                 }

  87.         }
  88.         return ret;
  89. }
复制代码
main.c
  1. #include <stdio.h>
  2. #include "QStack.h"

  3. int main(void) {
  4.         QStack* stack = QStack_Create();
  5.         int arr[10];
  6.         for (int i = 0; i < 10; i++) {
  7.                 arr[i] = i + 1;
  8.                 QStack_Push(stack, arr + i);
  9.         }
  10.         printf("QStack Size: %d\n", QStack_Size(stack));
  11.         printf("QStack Top: %d\n\n", *(int*)QStack_Top(stack));
  12.         while (QStack_Size(stack) > 5) {
  13.                 printf("Pop -> %d\n", *(int*)QStack_Pop(stack));
  14.         }

  15.         for (int i = 0; i < 10; i++) {
  16.                 arr[i] = i + 1;
  17.                 QStack_Push(stack, arr + i);
  18.         }
  19.         printf("\n\nQStack Size: %d\n", QStack_Size(stack));
  20.         printf("QStack Top: %d\n\n", *(int*)QStack_Top(stack));
  21.         while (QStack_Size(stack) > 0) {
  22.                 printf("Pop -> %d\n", *(int*)QStack_Pop(stack));
  23.         }
  24.         QStack_Destroy(stack);
  25.         getchar();
  26.         return 0;
  27. }
复制代码


回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2018-6-21 16:44

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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