devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

[数据结构-5] 详解栈以及两种存储结构的C语言实现_c语言中栈的存储结构

作者：AllinToyou | 2024-06-06 14:27:06

赞

踩

c语言中栈的存储结构

目录

认识栈

三种物理结构

1.顺序储存结构

2.链式储存结构

3.共享栈

出栈顺序的特点

C语言实现

顺序栈

链式栈

共享栈

认识栈

栈也是一种线性的逻辑结构, 和顺序表与普通链表不同的是他的操作(运算)不同

复习一下数据结构的三要素: 逻辑结构, 物理(储存结构), 操作(运算)

栈有两端: 栈顶和栈底, 只能在栈顶进行增加(入栈)和删除(出栈)

所以栈可以看成是一种操作受限的线性表

栈的特点是先进后出

三种物理结构

1.顺序储存结构

用一个数组实现栈, 用一个额外的指针指向栈顶(一般把栈底固定)

2.链式储存结构

用链表实现栈, 链表的第一个节点表示栈顶, 最后一个节点表示栈底, 只在链表的头部进行删除和增加

3.共享栈

用一个长为n数组a实现两个栈, 这两个栈的栈顶分别在a[-1]和a[n](指向栈底说明是空栈), 栈顶向中间延伸, 只有当两个栈顶相距为1时栈才满, 更好地利用了空间

出栈顺序的特点

栈方面的考察点经常是给出入栈顺序, 判断某个出栈顺序是否存在

一般这样考虑:

例如入栈为1,2,3,4....n

  • 如果第1个出栈元素是n, 那么不用想了, 它是先全部入栈, 再全部出栈, 出栈顺序是n,n-1,n-2....1
  • 如果第2个出栈元素是n, 那么第1个出栈元素可以是任意一个, 但是第3个出栈元素只能是n-1或者n-2
  • 如果第3个出栈元素是n, 那么第1个和第2个出栈元素可以是任意一个, 但是第4个出栈元素只能是n-1,n-2,n-3
  • 以此类推...

C语言实现

顺序栈

  1. /**
  2.  * @file sequence_stack.c
  3.  * @author xiaoxiao (you@domain.com)
  4.  * @brief 顺序栈
  5.  * @version 0.1
  6.  * @date 2022-03-05
  7.  * 
  8.  * @copyright Copyright (c) 2022
  9.  * 
  10.  */
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <stdbool.h>
  14.  
  15. #define MaxSize 10
  16.  
  17. typedef struct Stack {
  18.     int* pData; // 数据
  19.     int top; // 栈顶位置(-1表示空栈, 0表示当前栈有一个元素)
  20. }Stack;
  21.  
  22. typedef Stack* PStack;
  23.  
  24. /**
  25.  * @brief 初始化一个栈
  26.  * 
  27.  * @return PStack 栈指针
  28.  */
  29. PStack initailStack(){
  30.     PStack pStack = (PStack) malloc (sizeof(PStack));
  31.     if(pStack == NULL){
  32.         printf("no more momery");
  33.         exit(1);
  34.     }
  35.     pStack -> pData = (int*) malloc (MaxSize * sizeof(int));
  36.     if(pStack -> pData == NULL){
  37.         printf("no more momery");
  38.         exit(1);
  39.     }
  40.     pStack -> top = -1; // 空栈
  41.     return pStack;
  42. }
  43.  
  44. /**
  45.  * @brief 元素入栈
  46.  * 
  47.  * @param pStack 栈指针
  48.  * @param data 入栈元素
  49.  * @return true 入栈成功
  50.  * @return false 入栈失败
  51.  */
  52. bool push(PStack pStack, int data){
  53.     if(pStack -> top == MaxSize - 1){
  54.         printf("栈已满, 无法进栈\n");
  55.         return false;
  56.     }
  57.     pStack -> pData[pStack -> top ++ + 1] = data;
  58.     return true;
  59. }
  60.  
  61. /**
  62.  * @brief 元素出栈
  63.  * 
  64.  * @param pStack 栈指针
  65.  * @return int 出栈元素
  66.  */
  67. int pop(PStack pStack){
  68.     if(pStack -> top == -1){
  69.         printf("空栈不能出栈");
  70.         return false;
  71.     }
  72.     return pStack -> pData[-- pStack -> top + 1];
  73. }
  74.  
  75. /**
  76.  * @brief 打印栈中元素
  77.  * 
  78.  * @param pStack 栈指针 
  79.  * @return true 非空栈,可以打印
  80.  * @return false 不是空栈
  81.  */
  82. bool printStack(PStack pStack){
  83.     if(pStack -> top == -1){
  84.         printf("空栈不能打印\n");
  85.         return false;
  86.     }
  87.     printf("自栈底打印元素: ");
  88.     for(int i = 0; i <= pStack -> top; i ++){
  89.         printf("%d ", pStack -> pData[i]);
  90.     }
  91.     printf("\n");
  92.     return true;
  93. }
  94.  
  95. /**
  96.  * @brief 销毁栈, 并释放栈空间
  97.  * 
  98.  * @param pStack 
  99.  */
  100. void destoryStack(PStack pStack){
  101.     free(pStack -> pData);
  102.     free(pStack);
  103. }
  104.  
  105. int main(){
  106.     printf("--------------------\n");
  107.     PStack pStack = initailStack();
  108.     push(pStack, 1);
  109.     push(pStack, 10);
  110.     push(pStack, 4);
  111.     printStack(pStack);
  112.     destoryStack(pStack);
  113.     printf("--------------------");
  114.     return 0;
  115. }

链式栈

链式栈这里引用了我以前的写的链表的linked_list.h头文件

  1. /**
  2.  * @file linked_stack.c
  3.  * @author xiaoxiao (you@domain.com)
  4.  * @brief 链式栈
  5.  * @version 0.1
  6.  * @date 2022-03-05
  7.  * 
  8.  * @copyright Copyright (c) 2022
  9.  * 
  10.  */
  11.  
  12. #include <stdio.h>
  13. #include "linked_list.h"
  14.  
  15. /**
  16.  * @brief 初始化一个链式栈
  17.  * 
  18.  * @return PNode 头结点
  19.  */
  20. PNode initailStack(){
  21.     return initalList();
  22. }
  23.  
  24. /**
  25.  * @brief 元素入栈
  26.  * 
  27.  * @param pStack 栈指针
  28.  * @param data 入栈元素
  29.  * @return true 入栈成功
  30.  * @return false 入栈失败
  31.  */
  32. bool push(PNode pHead, int data){
  33.     return insertByIndex(pHead, 1, data);
  34. }
  35.  
  36. /**
  37.  * @brief 元素出栈
  38.  * 
  39.  * @param pStack 栈指针
  40.  * @return int 出栈元素
  41.  */
  42. int pop(PNode pHead){
  43.     int x;
  44.     if(pHead -> next != NULL){
  45.         x = pHead -> next -> data;
  46.         deleteByIndex(pHead, 1);
  47.         return x;
  48.     }
  49.     printf("空栈无法出栈\n");
  50.     return -1;
  51. }
  52.  
  53. /**
  54.  * @brief 打印栈中元素
  55.  * 
  56.  * @param pStack 栈指针 
  57.  * @return true 非空栈,可以打印
  58.  * @return false 不是空栈
  59.  */
  60. bool printStack(PNode pHead){
  61.     if(pHead -> next == NULL){
  62.         printf("空栈不能打印\n");
  63.         return false;
  64.     }
  65.     PNode pCurrent = pHead;
  66.     printf("自栈底打印元素: ");
  67.     int l = getLength(pHead);
  68.     int* data = (int*) malloc (l * sizeof(int)); 
  69.     int i = 0;
  70.     while (pCurrent -> next != NULL) {
  71.         data[i ++] = pCurrent -> next -> data;
  72.         pCurrent = pCurrent -> next;
  73.     }
  74.     for(i = 1; i <= l; i++)
  75.         printf("%d ", data[l - i]);
  76.     printf("\n");
  77.     return true;
  78. }
  79.  
  80. /**
  81.  * @brief 销毁栈, 并释放栈空间
  82.  * 
  83.  * @param pStack
  84.  */
  85. void destoryStack(PNode pHead){
  86.     destroyList(pHead);
  87. }
  88.  
  89. int main(){
  90.     printf("-----------------\n");
  91.     PNode pHead = initailStack();
  92.     push(pHead, 1);
  93.     push(pHead, 4);
  94.     pop(pHead);
  95.     printStack(pHead);
  96.     destoryStack(pHead);
  97.     printf("-----------------");
  98.     return 0;
  99. }

共享栈

  1. /**
  2.  * @file shared_stack.c
  3.  * @author xiaoxiao (you@domain.com)
  4.  * @brief 共享栈
  5.  * @version 0.1
  6.  * @date 2022-03-06
  7.  *
  8.  * @copyright Copyright (c) 2022
  9.  *
  10.  */
  11.  
  12. #include <math.h>
  13. #include <stdbool.h>
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16.  
  17. #define MaxSize 20  // 总栈长
  18.  
  19. typedef struct Stack {
  20.     int* pData;    // 数据
  21.     int leftTop;   // 左栈顶(-1表示空栈, 0表示当前栈有一个元素)
  22.     int rightTop;  // 右栈顶
  23. } Stack;
  24.  
  25. typedef Stack* PStack;
  26.  
  27. /**
  28.  * @brief 初始化一个栈
  29.  *
  30.  * @return PStack 栈指针
  31.  */
  32. PStack initailStack() {
  33.     PStack pStack = (PStack)malloc(sizeof(PStack));
  34.     if (pStack == NULL) {
  35.         printf("no more momery");
  36.         exit(1);
  37.     }
  38.     pStack->pData = (int*)malloc(MaxSize * sizeof(int));
  39.     if (pStack->pData == NULL) {
  40.         printf("no more momery");
  41.         exit(1);
  42.     }
  43.     pStack->leftTop = -1;        // 左栈顶
  44.     pStack->rightTop = MaxSize;  // 右栈顶
  45.     return pStack;
  46. }
  47.  
  48. /**
  49.  * @brief 元素入栈
  50.  *
  51.  * @param pStack 栈指针
  52.  * @param data 入栈元素,非负数就是向左入栈,负数就是向后入栈
  53.  * @return true 入栈成功
  54.  * @return false 入栈失败
  55.  */
  56. bool push(PStack pStack, int data) {
  57.     if (pStack->leftTop + 1 == pStack->rightTop) {
  58.         printf("栈已满, 无法进栈\n");
  59.         return false;
  60.     }
  61.     if (data >= 0)
  62.         pStack->pData[pStack->leftTop++ + 1] = data;
  63.     else
  64.         pStack->pData[pStack->rightTop-- - 1] = abs(data);
  65.     return true;
  66. }
  67.  
  68. /**
  69.  * @brief 元素出栈
  70.  *
  71.  * @param pStack 栈指针
  72.  * @param side 哪一侧的元素,true:左侧,false:右侧
  73.  * @return int 出栈元素
  74.  */
  75. int pop(PStack pStack, bool side) {
  76.     if (side) {
  77.         if (pStack->leftTop == -1) {
  78.             printf("空栈不能出栈\n");
  79.             return -1;
  80.         }
  81.         return pStack->pData[pStack->leftTop--];
  82.     } 
  83.     else {
  84.         if (pStack->rightTop == MaxSize) {
  85.             printf("空栈不能出栈\n");
  86.             return -1;
  87.         }
  88.         return pStack->pData[pStack->rightTop++];
  89.     }
  90. }
  91.  
  92. /**
  93.  * @brief 打印栈中元素
  94.  *
  95.  * @param pStack 栈指针
  96.  * @return true 非空栈,可以打印
  97.  * @return false 不是空栈
  98.  */
  99. void printStack(PStack pStack) {
  100.     if (pStack->leftTop == -1)
  101.         printf("左栈为空,不能打印\n");
  102.     else {
  103.         printf("自左栈底打印元素: ");
  104.         for (int i = 0; i <= pStack->leftTop; i++) {
  105.             printf("%d ", pStack->pData[i]);
  106.         }
  107.         printf("\n");
  108.     }
  109.     if (pStack->rightTop == MaxSize)
  110.         printf("右栈为空,不能打印\n");
  111.     else {
  112.         printf("自右栈底打印元素: ");
  113.         for (int i = MaxSize - 1; i >= pStack->leftTop; i--) {
  114.             printf("%d ", pStack->pData[i]);
  115.         }
  116.         printf("\n");
  117.     }
  118. }
  119.  
  120. /**
  121.  * @brief 销毁栈, 并释放栈空间
  122.  *
  123.  * @param pStack
  124.  */
  125. void destoryStack(PStack pStack) {
  126.     free(pStack->pData);
  127.     free(pStack);
  128. }
  129.  
  130. int main() {
  131.     printf("--------------------\n");
  132.     PStack pStack = initailStack();
  133.     push(pStack, 1);
  134.     push(pStack, -10);
  135.     push(pStack, 4);
  136.     printStack(pStack);
  137.     destoryStack(pStack);
  138.     printf("--------------------");
  139.     return 0;
  140. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/681275
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号