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

手撕数据结构---栈和队列的概念以及实现

作者：黑客灵魂 | 2024-08-03 07:34:01

赞

踩

手撕数据结构---栈和队列的概念以及实现

栈的概念：

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

 栈的基本框架

  1. struct Stack
  2. {
  3.     int* arr;
  4.     int capacity;
  5.     int top;//栈顶
  6. };

栈的实现

test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Stack.h"
  3.  
  4. void STTest()
  5. {
  6.     ST st;//创建一个栈变量
  7.  
  8.     //初始化
  9.     STInit(&st);
  10.  
  11.     //入栈
  12.     SrackPush(&st, 1);
  13.     SrackPush(&st, 2);
  14.     SrackPush(&st, 3);
  15.     SrackPush(&st, 4);
  16.     SrackPush(&st, 5);
  17.     //打印栈内的有效数据
  18.     printf("%d\n", STSize(&st));
  19.     //栈的出数据
  20.     /*SrackPop(&st);*/
  21.     //循环出栈，直到栈为空
  22.     // 
  23.     while (!StackEmpty(&st))//如果栈不为空的话，我们一直进行循环打印栈顶数据
  24.     {
  25.         //取出当前栈顶的数据
  26.         STDataType data = StackTop(&st);
  27.         printf("%d ", data);//打印返回的栈顶数据
  28.         //数据出栈
  29.         SrackPop(&st);
  30.  
  31.         //入栈的顺序是1 2 3 4 5
  32.         //出栈的顺序是5 4 3 2 1
  33.  
  34.         //栈是不能被遍历的，也不能被随机访问
  35.     }
  36.     //打印栈内的有效数据
  37.     printf("%d\n", STSize(&st));
  38.  
  39.  
  40.     //销毁
  41.     STDestory(&st);
  42. }
  43.  
  44. int main()
  45. {
  46.     STTest();
  47.     return 0;
  48. }
  49. //栈这样的结构只能在一端入栈，一端出栈

Stack.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Stack.h"
  3.  
  4. //初始化
  5. void STInit(ST* ps)
  6. {
  7.     assert(ps);//判断传的ps是不是空的
  8.     ps->arr = NULL;
  9.     ps->capacity = ps->top = 0;
  10.     //一开始的栈顶等于我们的栈底（栈为空的话）
  11. }
  12.  
  13. //销毁
  14. void STDestory(ST* ps)
  15. {
  16.     assert(ps);//参数不能传空
  17.  
  18.     if (ps->arr)//arr不为空的话我们直接将数组释放掉
  19.     {
  20.         free(ps->arr);
  21.     }
  22.     ps->arr = NULL;
  23.     ps->capacity = ps->top = 0;
  24. }
  25.  
  26.  
  27.  
  28.  
  29.  
  30. //栈的入数据操作
  31. void SrackPush(ST* ps, STDataType x)
  32. {
  33.     assert(ps);//ps不能传空
  34.  
  35.     //如果空间足够的话我们直接进行插入
  36.  
  37.     //判断空间是否足够，如果top等于capacity的话，那么就说明我们这个栈就是满的
  38.     if (ps->capacity == ps->top)//，满了，我们需要进行增容操作
  39.     {
  40.         //二倍的增加
  41.         //初始情况下我们的capacity是定义为0的，所以我们不能直接进行乘二的操作
  42.         //我们需要创建一个变量
  43.         int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  44.         //如果容量为0的话，我们给newCapacity一个初始值4，如果不为0我们就进行乘二的操作
  45.  
  46.         STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
  47.         if (tmp == NULL)
  48.         {
  49.             perror("realloc fail!");
  50.             exit(1);
  51.         }
  52.         //申请成功，我们将tmp申请的空间给pa->arr
  53.         ps->arr = tmp;
  54.  
  55.         //申请空间成功了，那么我们就要将capacity进行改变了
  56.         ps->capacity = newCapacity;
  57.     }
  58.  
  59.     //到这里空间一定是够的
  60.     ps->arr[ps->top] = x;//我们往栈顶的位置进行添加数据
  61.     //添加完数据之后，top要加加
  62.     ps->top++;
  63. }
  64.  
  65. //判断栈是否为空
  66. bool StackEmpty(ST* ps)
  67. {
  68.     assert(ps);
  69.     return ps->top == 0;//为空就返回true
  70. }
  71.  
  72. //栈的出数据操作
  73. void SrackPop(ST* ps)
  74. {
  75.     assert(ps);
  76.     //如果栈为空的话，我们是不能出数据的（top==0）
  77.     assert(!StackEmpty(ps));//如果栈为空就会报错了
  78.  
  79.     //走到这里就说明栈不为空
  80.     --ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了
  81. }
  82.  
  83.  
  84. //取栈顶元素---循环打印栈顶的数据
  85. STDataType StackTop(ST* ps)//返回值是栈顶的元素
  86. {
  87.     assert(ps);
  88.  
  89.     assert(!StackEmpty(ps));//判断当前栈是不是空的，如果是空的话，我们没有什么能取的
  90.  
  91.     return ps->arr[ps->top - 1];//ps->top - 1是这个栈的最后一个数据的下标
  92.  
  93. }
  94.  
  95. //获取栈中有效个数
  96. int STSize(ST* ps)
  97. {
  98.     assert(ps);
  99.     return ps->top;
  100. }

Stack.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7.  
  8. //定义栈的结构
  9. typedef int STDataType;
  10. typedef struct Stack
  11. {
  12.     STDataType* arr;
  13.     int capacity;//栈的空间大小
  14.     int top;//栈顶（插入数据和删除数据的位置）
  15. }ST;
  16.  
  17. //初始化
  18. void STInit(ST* ps);//传的是地址
  19.  
  20. //销毁
  21. void STDestory(ST* ps);
  22.  
  23. //栈顶-=--如数据、出数据
  24.  
  25. //栈的入数据操作
  26. void SrackPush(ST* ps, STDataType x);//第二个参数是要插入的数据
  27.  
  28. //栈的出数据操作
  29. void SrackPop(ST* ps);
  30.  
  31. //取栈顶元素---循环打印栈顶的数据
  32. STDataType StackTop(ST* ps);//返回值是栈顶的元素
  33.  
  34. //判断栈是否为空
  35. bool StackEmpty(ST* ps);
  36.  
  37. //获取栈中有效个数
  38. int STSize(ST* ps);

队列的概念

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

队头：用来删除数据

对头：用来插入数据

队列的底层是链表，链表是由一个一个的节点组成

  1. //定义队列节点的结构
  2. struct QueueNode
  3. {
  4.     int data;
  5.     struct QueueNode* next;//指向下个节点的指针
  6. };
  7.  
  8. struct Queue
  9. {
  10.     struct QueueNode* phead;//指向的是队头--删除数据
  11.     struct QueueNode* ptail;//指向的是队尾--插入数据
  12. };

为什么是定义的是两个结构体类型呢？

队列中的每一个数据是通过一个节点保存的，节点和节点之间是通过指针链接的，

其实就是维护了一个链表，给这个链表加上先进先出的限制，其实就是队列了

Queue.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7.  
  8. //定义队列结构
  9. typedef int QDataType;
  10. typedef struct QueueNode
  11. {
  12.     QDataType data;
  13.     struct QueueNode* next;
  14.  
  15. }QueueNode;
  16.  
  17. typedef struct Queue
  18. {
  19.     QueueNode*phead;//指向头节点的指针---队头--删除数据
  20.     QueueNode*ptail;//指向尾节点的指针---队尾--插入数据
  21.     int size;//保存队列有效个数
  22. }Queue ;
  23.  
  24.  
  25. //初始化
  26. void QueueInit(Queue* pq);
  27.  
  28. //入队列，队尾   插入数据
  29. void QueuePush(Queue* pq, QDataType x);
  30.  
  31. //出队列,队头    删除数据
  32. void QueuePop(Queue* pq);
  33.  
  34. //判断队列是否为空
  35. bool Queuempty(Queue* pq);
  36.  
  37. //取队头数据
  38. QDataType QueueFront(Queue* pq);
  39.  
  40. //取队尾数据
  41. QDataType QueueBack(Queue* pq);
  42.  
  43. //队列有效元素个数
  44. int QueueSize(Queue* pq);
  45.  
  46. //队列的销毁
  47. void QueueDestroy(Queue* pq);

Queue.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Queue.h"
  3.  
  4. //初始化
  5. void QueueInit(Queue* pq)
  6. {
  7.     assert(pq);//传过来的不能是空指针 
  8.  
  9.     pq->phead = pq->ptail = NULL;//空的队列
  10.     pq->size = 0;
  11. }
  12.  
  13. //判断队列是否为空
  14. bool Queuempty(Queue* pq)
  15. {
  16.     assert(pq);
  17.  
  18.     return pq->phead == NULL && pq->ptail == NULL;
  19.     //如果后面的表达式成立，那么就是真，返回的是true
  20.  
  21.     //就是说如果这里的是空队列的话，那么就返回的是true
  22. }
  23.  
  24. //入队列，队尾   插入数据
  25. void QueuePush(Queue* pq, QDataType x)
  26. {
  27.     assert(pq);
  28.  
  29.     //申请新节点
  30.     QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间
  31.     if (newnode == NULL)
  32.     {
  33.         perror("malloc dail!");
  34.         exit(1);
  35.     }
  36.     //对newnode进行初始化操作
  37.     newnode->data = x;
  38.     newnode->next = NULL;
  39.     if (pq->phead == NULL)//说明队列为空
  40.     {
  41.         pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点
  42.     }
  43.     else//队列不为空
  44.     {
  45.         pq->ptail->next = newnode;
  46.         //那么此时的newnode 就是新的ptail
  47.         pq->ptail = newnode;
  48.     }
  49.     pq->size++;
  50. }
  51.  
  52. //出队列,队头    删除数据    从头结点开始删除数据
  53. void QueuePop(Queue* pq)
  54. {
  55.     assert(pq);
  56.     //队列为空（不可删除数据，因为没有数据）
  57.     //队列不为空（可删除数据）
  58.  
  59.     assert(!Queuempty(pq));//队列为空白的话就报错
  60.  
  61.     //处理只有一个节点的情况，避免ptail变成野指针
  62.     //判断只有一个节点的情况
  63.     if (pq->ptail == pq->phead)//头尾指针相同，说明只有一个节点
  64.     {
  65.         free(pq->phead);//随便释放
  66.         pq->phead = pq->ptail = NULL;
  67.     }
  68.     else//处理多个节点的情况
  69.     {
  70.         //删除队头元素
  71.     //那么我们现将下个节点的位置进行保存
  72.         QueueNode* next = pq->phead->next;
  73.         //存储好之后我们直接将头结点进行释放
  74.         free(pq->phead);
  75.         pq->phead = next;//那么之前存的next就是新的头结点了
  76.     }
  77.     pq->size--;
  78. }
  79.  
  80. //取队头数据
  81. QDataType QueueFront(Queue* pq)//返回队头数据
  82. {
  83.     assert(pq);
  84.     assert(!Queuempty(pq));//队列不为空
  85.  
  86.     return pq->phead->data;//将队头里面的数据直接返回就行了
  87. }
  88.  
  89. //取队尾数据
  90. QDataType QueueBack(Queue* pq)
  91. {
  92.     assert(pq);
  93.     assert(!Queuempty(pq));//队列不为空
  94.  
  95.     return pq->ptail->data;
  96. }
  97.  
  98. //队列有效元素个数
  99. int QueueSize(Queue* pq)
  100. {
  101.     assert(pq);
  102.     //下面这种遍历的话效率太低了
  103.     //int size = 0;
  104.     定义一个指针进行遍历
  105.     //QueueNode* pcur = pq->phead;//指向队列的头结点
  106.     //while (pcur)//pcur不为空就往后走
  107.     //{
  108.     //  size++;
  109.     //  pcur = pcur->next;
  110.     //}
  111.     //return size;
  112.     return pq->size;
  113. }
  114.  
  115. //队列的销毁
  116. void QueueDestroy(Queue* pq)
  117. {
  118.     assert(pq);
  119.     assert(!Queuempty(pq));//队列不为空
  120.     //遍历
  121.     QueueNode* pcur = pq->phead;
  122.     while (pcur)
  123.     {
  124.         //销毁之前先把下个节点进行保存
  125.         QueueNode* next = pcur -> next;
  126.         free(pcur);
  127.         //将Pcur销毁之后，那么之前保存的next就是新的头结点
  128.         pcur = next;
  129.     }
  130.     pq->phead = pq->ptail = NULL;
  131.     pq->size = 0;
  132. }

test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Queue.h"
  3.  
  4.  
  5. void QueueTest01()
  6. {
  7.     Queue q;//创建一个队列变量
  8.     //初始化
  9.     QueueInit(&q);
  10.  
  11.     //插入数据
  12.     QueuePush(&q, 1);
  13.     QueuePush(&q, 2);
  14.     QueuePush(&q, 3);
  15.     QueuePush(&q, 4);
  16.  
  17.     //取队头数据
  18.     printf("head:%d\n", QueueFront(&q));
  19.  
  20.     //取队尾数据
  21.     printf("tail:%d\n", QueueBack(&q));
  22.  
  23.     //删除
  24.     QueuePop(&q);
  25.  
  26.     //队列有效个数
  27.     printf("size:%d\n", QueueSize(&q));
  28.  
  29.     //队列的销毁
  30.     QueueDestroy(&q);
  31.  
  32. }
  33. int main()  
  34. {
  35.     QueueTest01();
  36. }

栈和队列相关的OJ题

题目一：有效的括号

 

  1. //借助数据结构---栈来解决这道题
  2. /*
  3. 思路：我们先创建一个字符串指针ps
  4. 我们再创建一个栈空间
  5. 我们通过ps进行字符串的遍历
  6. 如果是做左括号的话，那么我们就进行入栈操作
  7. 如果我们遇到了右括号的话，那么我们就与栈顶的元素进行匹配
  8.  如果是一对括号的话，那么我们就进行出栈操作，然后ps++,top-- 进行下一对括号的匹配
  9.  如果ps++指向的是大括号，但是栈顶的是小括号，那么现在就是不匹配的
  10.  那么我们就直接返回false
  11.  
  12.  
  13. */
  14. typedef char STDataType;
  15. typedef struct Stack
  16. {
  17.     STDataType* arr;
  18.     int capacity;
  19.     int top;//栈顶
  20. }ST;
  21.  
  22. //初始化
  23. void STInit(ST* ps)
  24. {
  25.     assert(ps);//判断传的ps是不是空的
  26.     ps->arr = NULL;
  27.     ps->capacity = ps->top = 0;
  28.     //一开始的栈顶等于我们的栈底（栈为空的话）
  29. }
  30.  
  31. //销毁
  32. void STDestory(ST* ps)
  33. {
  34.     assert(ps);//参数不能传空
  35.  
  36.     if (ps->arr)//arr不为空的话我们直接将数组释放掉
  37.     {
  38.         free(ps->arr);
  39.     }
  40.     ps->arr = NULL;
  41.     ps->capacity = ps->top = 0;
  42. }
  43.  
  44. //栈的入数据操作
  45. void SrackPush(ST* ps, STDataType x)
  46. {
  47.     assert(ps);//ps不能传空
  48.  
  49.     //如果空间足够的话我们直接进行插入
  50.  
  51.     //判断空间是否足够，如果top等于capacity的话，那么就说明我们这个栈就是满的
  52.     if (ps->capacity == ps->top)//，满了，我们需要进行增容操作
  53.     {
  54.         //二倍的增加
  55.         //初始情况下我们的capacity是定义为0的，所以我们不能直接进行乘二的操作
  56.         //我们需要创建一个变量
  57.         int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  58.         //如果容量为0的话，我们给newCapacity一个初始值4，如果不为0我们就进行乘二的操作
  59.  
  60.         STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
  61.         if (tmp == NULL)
  62.         {
  63.             perror("realloc fail!");
  64.             exit(1);
  65.         }
  66.         //申请成功，我们将tmp申请的空间给pa->arr
  67.         ps->arr = tmp;
  68.  
  69.         //申请空间成功了，那么我们就要将capacity进行改变了
  70.         ps->capacity = newCapacity;
  71.     }
  72.  
  73.     //到这里空间一定是够的
  74.     ps->arr[ps->top] = x;//我们往栈顶的位置进行添加数据
  75.     //添加完数据之后，top要加加
  76.     ps->top++;
  77. }
  78.  
  79. //判断栈是否为空
  80. bool StackEmpty(ST* ps)
  81. {
  82.     assert(ps);
  83.     return ps->top == 0;//为空就返回true
  84. }
  85.  
  86. //栈的出数据操作
  87. void SrackPop(ST* ps)
  88. {
  89.     assert(ps);
  90.     //如果栈为空的话，我们是不能出数据的（top==0）
  91.     assert(!StackEmpty(ps));//如果栈为空就会报错了
  92.  
  93.     //走到这里就说明栈不为空
  94.     --ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了
  95. }
  96.  
  97.  
  98. //取栈顶元素---循环打印栈顶的数据
  99. STDataType StackTop(ST* ps)//返回值是栈顶的元素
  100. {
  101.     assert(ps);
  102.  
  103.     assert(!StackEmpty(ps));//判断当前栈是不是空的，如果是空的话，我们没有什么能取的
  104.  
  105.     return ps->arr[ps->top - 1];//ps->top - 1是这个栈的最后一个数据的下标
  106.  
  107. }
  108.  
  109. //获取栈中有效个数
  110. int STSize(ST* ps)
  111. {
  112.     assert(ps);
  113.     return ps->top;
  114. }
  115.  
  116. bool isValid(char* s)
  117. {
  118.     ST st;//创建一个栈变量
  119.     //初始化
  120.     STInit(&st);
  121.  
  122.  
  123.     //遍历字符串s
  124.     char *ps=s;//指向字符串s
  125.     while(*ps!='\0')//我们需要遍历字符串'\0'之前的数据
  126.     {
  127.         //左括号入栈
  128.         if(*ps=='('|| *ps=='[' || *ps=='{')
  129.         {
  130.             SrackPush(&st,*ps);
  131.         }
  132.         else//右括号，和栈顶元素进行匹配
  133.         {
  134.             //栈不为空才能取元素
  135.             //判断栈是否为空，空的话直接返回false
  136.             if(StackEmpty(&st))//栈为空的话，这个函数返回的就是true
  137.             {
  138.                 return false;
  139.             }
  140.             //取栈顶元素，与top进行比较
  141.             char ch=StackTop(&st);//栈顶的元素，我们取出
  142.             if((*ps==')' &&ch=='(')
  143.             ||(*ps==']' &&ch=='[')
  144.             ||(*ps=='}' &&ch=='{'))
  145.             {
  146.                 //匹配上了我们就进行出栈操作
  147.                 SrackPop(&st);
  148.             }
  149.             else
  150.             {
  151.                 //不匹配的话，我们在返回之前我们同样需要进行销毁操作
  152.                 STDestory(&st);
  153.                 //那么就是括号不匹配了
  154.                 return false;
  155.             }
  156.         }
  157.         //入栈之后我们进行ps++
  158.         ps++;
  159.  
  160.     }
  161.     bool ret=StackEmpty(&st)==true;//为空的话那么我们就返回truew
  162.     //销毁
  163.     STDestory(&st);
  164.     return ret;
  165. }
  166. /*
  167. 假如我们的字符串里面只有一个左括号的话，那么这个代码就会直接入栈
  168. 然后跳出循环，并没有对栈内的空间进行检查 
  169. 并没有进行出栈的操作，所以栈内是有元素的
  170. 我们要判断栈内是否为空
  171. 如果是空的话，那么就说括号都配对完成了，左括号都出栈了，那么就返回true
  172.  
  173. */
  174. /*
  175. 我们在取栈顶元素之前我们还要对栈的空间进行判断，看看栈是否为空，
  176. 栈不为空才能去栈顶元素
  177. 栈为空的话，之间返回false
  178.  
  179. */

题目二:用队列实现栈

 

  1. /*
  2. 队列是先进先出
  3. 栈是先进后出
  4. */
  5. /*
  6. 因为我们是要进行栈的实现
  7. 那么假如我们存进去1 2 3
  8. 那么拿出来的就是3 2 1
  9.  
  10. 我们用两个队列实现
  11. Q1和Q2两个队列
  12. 假设现在Q1里面的是1 2 3,1在对头，3在队尾
  13. 我们Q1每次出size-1个数据入到Q2里面，那么此时的Q1就剩下一个3,那么我们直接将3出栈，那么得到的第一个数就是3
  14. 以此类推我们就能得到3 2 1
  15. */
  16.  
  17. /*
  18. 两个队列，那个队列不为空，我们就将这个队列里面的size-1个数据导入到另一个队列里面去，然后将剩下的元素导出了
  19.  
  20. 如果最后队列里面只有一个数据，那么我们就直接将这个数据导出
  21. */
  22.  
  23. /*思路：
  24. 出栈：找到不为空的队列，将size-1个数据导入到另一个队列中
  25. 入栈：往空队列中插入数据
  26. 取栈顶元素
  27.  
  28.  
  29. */
  30.  
  31. //定义队列结构
  32. typedef int QDataType;
  33. typedef struct QueueNode
  34. {
  35.     QDataType data;
  36.     struct QueueNode* next;
  37.  
  38. }QueueNode;
  39.  
  40. typedef struct Queue
  41. {
  42.     QueueNode*phead;//指向头节点的指针---队头--删除数据
  43.     QueueNode*ptail;//指向尾节点的指针---队尾--插入数据
  44.     int size;//保存队列有效个数
  45. }Queue ;
  46.  
  47. //初始化
  48. void QueueInit(Queue* pq)
  49. {
  50.     assert(pq);//传过来的不能是空指针 
  51.  
  52.     pq->phead = pq->ptail = NULL;//空的队列
  53.     pq->size = 0;
  54. }
  55.  
  56. //判断队列是否为空
  57. bool Queuempty(Queue* pq)
  58. {
  59.     assert(pq);
  60.  
  61.     return pq->phead == NULL && pq->ptail == NULL;
  62.     //如果后面的表达式成立，那么就是真，返回的是true
  63.  
  64.     //就是说如果这里的是空队列的话，那么就返回的是true
  65. }
  66.  
  67. //入队列，队尾   插入数据
  68. void QueuePush(Queue* pq, QDataType x)
  69. {
  70.     assert(pq);
  71.  
  72.     //申请新节点
  73.     QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间
  74.     if (newnode == NULL)
  75.     {
  76.         perror("malloc dail!");
  77.         exit(1);
  78.     }
  79.     //对newnode进行初始化操作
  80.     newnode->data = x;
  81.     newnode->next = NULL;
  82.     if (pq->phead == NULL)//说明队列为空
  83.     {
  84.         pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点
  85.     }
  86.     else//队列不为空
  87.     {
  88.         pq->ptail->next = newnode;
  89.         //那么此时的newnode 就是新的ptail
  90.         pq->ptail = newnode;
  91.     }
  92.     pq->size++;
  93. }
  94.  
  95. //出队列,队头    删除数据    从头结点开始删除数据
  96. void QueuePop(Queue* pq)
  97. {
  98.     assert(pq);
  99.     //队列为空（不可删除数据，因为没有数据）
  100.     //队列不为空（可删除数据）
  101.  
  102.     assert(!Queuempty(pq));//队列为空白的话就报错
  103.  
  104.     //处理只有一个节点的情况，避免ptail变成野指针
  105.     //判断只有一个节点的情况
  106.     if (pq->ptail == pq->phead)//头尾指针相同，说明只有一个节点
  107.     {
  108.         free(pq->phead);//随便释放
  109.         pq->phead = pq->ptail = NULL;
  110.     }
  111.     else//处理多个节点的情况
  112.     {
  113.         //删除队头元素
  114.     //那么我们现将下个节点的位置进行保存
  115.         QueueNode* next = pq->phead->next;
  116.         //存储好之后我们直接将头结点进行释放
  117.         free(pq->phead);
  118.         pq->phead = next;//那么之前存的next就是新的头结点了
  119.     }
  120.     pq->size--;
  121. }
  122.  
  123. //取队头数据
  124. QDataType QueueFront(Queue* pq)//返回队头数据
  125. {
  126.     assert(pq);
  127.     assert(!Queuempty(pq));//队列不为空
  128.  
  129.     return pq->phead->data;//将队头里面的数据直接返回就行了
  130. }
  131.  
  132. //取队尾数据
  133. QDataType QueueBack(Queue* pq)
  134. {
  135.     assert(pq);
  136.     assert(!Queuempty(pq));//队列不为空
  137.  
  138.     return pq->ptail->data;
  139. }
  140.  
  141. //队列有效元素个数
  142. int QueueSize(Queue* pq)
  143. {
  144.     assert(pq);
  145.     //下面这种遍历的话效率太低了
  146.     //int size = 0;
  147.     定义一个指针进行遍历
  148.     //QueueNode* pcur = pq->phead;//指向队列的头结点
  149.     //while (pcur)//pcur不为空就往后走
  150.     //{
  151.     //  size++;
  152.     //  pcur = pcur->next;
  153.     //}
  154.     //return size;
  155.     return pq->size;
  156. }
  157.  
  158. //队列的销毁
  159. void QueueDestroy(Queue* pq)
  160. {
  161.     assert(pq);
  162.     //assert(!Queuempty(pq));//队列不为空
  163.     //遍历
  164.     QueueNode* pcur = pq->phead;
  165.     while (pcur)
  166.     {
  167.         //销毁之前先把下个节点进行保存
  168.         QueueNode* next = pcur -> next;
  169.         free(pcur);
  170.         //将Pcur销毁之后，那么之前保存的next就是新的头结点
  171.         pcur = next;
  172.     }
  173.     pq->phead = pq->ptail = NULL;
  174.     pq->size = 0;
  175. }
  176.  
  177.  
  178.  
  179. //两个队列来实现栈
  180. typedef struct 
  181. {
  182.     Queue q1;//队列1
  183.     Queue q2;//队列2
  184. } MyStack;
  185.  
  186. //STInit  栈的初始化
  187. MyStack* myStackCreate()
  188. {
  189.     MyStack*pst=(MyStack*)malloc(sizeof(MyStack));//创建一个栈大小的空间
  190.     QueueInit(&pst->q1);//调用初始化函数对q1进行初始化
  191.     QueueInit(&pst->q2);
  192.  
  193.     return pst;
  194. }
  195.  
  196. //那么到这里我们有一个空栈，栈里面有两个队列
  197.  
  198. //入数据
  199. void myStackPush(MyStack* obj, int x)
  200. {
  201.     //往不为空的队列插入数据
  202.     //第一步判断那个队列是非空队列
  203.     if(!Queuempty(&obj->q1))//如果这个队列不是空的话，我们就我那个这个队列里面入数据
  204.     {
  205.         //往队列内插入数据
  206.         QueuePush(&obj->q1,x);
  207.     }
  208.     else
  209.     {
  210.         QueuePush(&obj->q2,x);
  211.     }
  212.  
  213. }
  214. //出数据
  215. int myStackPop(MyStack* obj)
  216. {
  217.     //找到不为空的队列
  218.     Queue*empQ=&obj->q1;//假设q1是空的，创建指针指向q1
  219.     Queue*noneQ=&obj->q2;//q2不为空，指针指向q2
  220.  
  221.     if(!Queuempty(&obj->q1))//如果q1不为空
  222.     {
  223.         //创建两个指针，noneQ指向的是非空队列，empQ指向的是空队列
  224.         noneQ=&obj->q1;//那么这个非空指针就指向了q1
  225.         empQ=&obj->q2;//那么空指针就指向q2了
  226.     }
  227.     //将不为空内的size-1个数据导入到另一个队列里面
  228.     while(QueueSize(noneQ)>1)//循环条件是非空队列里面只剩下一个有效的数据了
  229.     {
  230.         int front=QueueFront(noneQ);//获取这个非空队列里面的队头数据
  231.         QueuePush(empQ,front);//往空队列里面循环插入队头数据
  232.         QueuePop(noneQ);//因为我们这个非空队列的队头数据已经拿出去了 ，那么我们就将非空队列进行删除数据操作
  233.     }
  234.     //非空队列中只剩下一个数据----那么这个数据就是要出栈的数据
  235.     int pop=QueueFront(noneQ);//获取剩下的这个元素
  236.     QueuePop(noneQ);//进行出数据操作
  237.     return pop;//返回我们要的值
  238.  
  239. }
  240.  
  241. //取栈顶元素  假设插入1 2 3，那么栈顶就是3   这里是2两个队列
  242. int myStackTop(MyStack* obj)   
  243. {
  244.     //找到不为空的队列，取队尾元素
  245.     if(!Queuempty(&obj->q1))//如果第一个队列不为空的话
  246.     {
  247.         return QueueBack(&obj->q1);//直接将取到的队尾元素进行返回就行了
  248.     }
  249.     else
  250.     {
  251.         return QueueBack(&obj->q2);
  252.     }
  253. }
  254. //判读栈是否为空
  255. bool myStackEmpty(MyStack* obj)
  256. {
  257.     //两个队列如果都为空的话，那么这个栈就是空的
  258.     return Queuempty(&obj->q1)  &&  Queuempty(&obj->q2);
  259. }
  260. //销毁
  261. void myStackFree(MyStack* obj)
  262. {
  263.     //就是栈内的连个队列的销毁
  264.     QueueDestroy(&obj->q1);
  265.     QueueDestroy(&obj->q2);
  266.     free(obj);//将我们之前申请的栈空间进行释放掉
  267.     obj=NULL;
  268. }
  269.  
  270. /**
  271.  * Your MyStack struct will be instantiated and called as such:
  272.  * MyStack* obj = myStackCreate();
  273.  * myStackPush(obj, x);
  275.  * int param_2 = myStackPop(obj);
  277.  * int param_3 = myStackTop(obj);
  279.  * bool param_4 = myStackEmpty(obj);
  281.  * myStackFree(obj);
  282. */

题目三：用栈实现队列

 

  1. //定义栈的结构
  2. typedef int STDataType;
  3. typedef struct Stack
  4. {
  5.     STDataType* arr;
  6.     int capacity;//栈的空间大小
  7.     int top;//栈顶（插入数据和删除数据的位置）
  8. }ST;
  9.  
  10. //初始化
  11. void STInit(ST* ps)
  12. {
  13.     assert(ps);//判断传的ps是不是空的
  14.     ps->arr = NULL;
  15.     ps->capacity = ps->top = 0;
  16.     //一开始的栈顶等于我们的栈底（栈为空的话）
  17. }
  18.  
  19. //销毁
  20. void STDestory(ST* ps)
  21. {
  22.     assert(ps);//参数不能传空
  23.  
  24.     if (ps->arr)//arr不为空的话我们直接将数组释放掉
  25.     {
  26.         free(ps->arr);
  27.     }
  28.     ps->arr = NULL;
  29.     ps->capacity = ps->top = 0;
  30. }
  31.  
  32.  
  33.  
  34.  
  35.  
  36. //栈的入数据操作
  37. void SrackPush(ST* ps, STDataType x)
  38. {
  39.     assert(ps);//ps不能传空
  40.  
  41.     //如果空间足够的话我们直接进行插入
  42.  
  43.     //判断空间是否足够，如果top等于capacity的话，那么就说明我们这个栈就是满的
  44.     if (ps->capacity == ps->top)//，满了，我们需要进行增容操作
  45.     {
  46.         //二倍的增加
  47.         //初始情况下我们的capacity是定义为0的，所以我们不能直接进行乘二的操作
  48.         //我们需要创建一个变量
  49.         int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  50.         //如果容量为0的话，我们给newCapacity一个初始值4，如果不为0我们就进行乘二的操作
  51.  
  52.         STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
  53.         if (tmp == NULL)
  54.         {
  55.             perror("realloc fail!");
  56.             exit(1);
  57.         }
  58.         //申请成功，我们将tmp申请的空间给pa->arr
  59.         ps->arr = tmp;
  60.  
  61.         //申请空间成功了，那么我们就要将capacity进行改变了
  62.         ps->capacity = newCapacity;
  63.     }
  64.  
  65.     //到这里空间一定是够的
  66.     ps->arr[ps->top] = x;//我们往栈顶的位置进行添加数据
  67.     //添加完数据之后，top要加加
  68.     ps->top++;
  69. }
  70.  
  71. //判断栈是否为空
  72. bool StackEmpty(ST* ps)
  73. {
  74.     assert(ps);
  75.     return ps->top == 0;//为空就返回true
  76. }
  77.  
  78. //栈的出数据操作
  79. void SrackPop(ST* ps)
  80. {
  81.     assert(ps);
  82.     //如果栈为空的话，我们是不能出数据的（top==0）
  83.     assert(!StackEmpty(ps));//如果栈为空就会报错了
  84.  
  85.     //走到这里就说明栈不为空
  86.     --ps->top;//我们只需要将top进行--操作就能进行栈的出数据操作了
  87. }
  88.  
  89.  
  90. //取栈顶元素---循环打印栈顶的数据
  91. STDataType StackTop(ST* ps)//返回值是栈顶的元素
  92. {
  93.     assert(ps);
  94.  
  95.     assert(!StackEmpty(ps));//判断当前栈是不是空的，如果是空的话，我们没有什么能取的
  96.  
  97.     return ps->arr[ps->top - 1];//ps->top - 1是这个栈的最后一个数据的下标
  98.  
  99. }
  100.  
  101. //获取栈中有效个数
  102. int STSize(ST* ps)
  103. {
  104.     assert(ps);
  105.     return ps->top;
  106. }
  107.  
  108. ///
  109.  
  110.  
  111. /*
  112. 因为我们是用两个栈来实现队列
  113. 那么假如我们插入1 2 3 
  114. 那么导出的也是1 2 3
  115.  
  116.  
  117.  我们创建两个栈，分别用来入数据和出数据
  118.  第一个栈接入我们放的是1 2 3  1在栈底，3在栈顶
  119.  那么我们将这三个数据依次放到另一个栈内
  120.  那么另一个栈就是3 2 1  3在栈第，1在栈顶，那么我们依次将这个栈的数据依次导出
  121.  就能达到队列的效果了
  122. */
  123.  
  124. /*逻辑：pop是出数据
  125. 入队：往pushST中插入数据
  126.  
  127. 出队：判断popST是否为空，不为空直接pop,为空的话将pushST导入到popST中
  128.  
  129.  取队头：跟出队一样的，但是这里不pop数据
  130. */
  131. typedef struct
  132. {
  133.     ST pushST;//两个栈
  134.     ST popST;
  135. } MyQueue;
  136.  
  137. //初始化操作
  138. MyQueue* myQueueCreate()
  139. {
  140.     MyQueue*pst=(MyQueue*)malloc(sizeof(MyQueue));
  141.     STInit(&pst->pushST);//栈的初始化
  142.     STInit(&pst->popST);
  143.     return pst;
  144. }
  145.  
  146. //往pushST中插入数据
  147. void myQueuePush(MyQueue* obj, int x)
  148. {
  149.     //调用栈的插入方法
  150.     SrackPush(&obj->pushST,x);//往pushST中插入数据
  151. }
  152.  
  153. //删除数据
  154. int myQueuePop(MyQueue* obj)
  155. {
  156.     //1.检查popST是否为空
  157.        //1)不为空直接 出
  158.        //2)为空，pushST导入到popST,在出数据
  159.     if(StackEmpty(&obj->popST))//如果为空的话，我们就进项导数据操作
  160.     {
  161.         //导数据
  162.         while(!StackEmpty(&obj->pushST))//只要不为空，我们就将这个栈内的数据导出
  163.         {
  164.             //循环取栈顶数据
  165.             //StackTop(&obj->pushST)将这个栈内的栈顶数据取出
  166.             SrackPush(&obj->popST,StackTop(&obj->pushST));
  167.             //将pushST这个栈的栈顶数据导入到popST中
  168.  
  169.             //取完数据，插入完数据之后我们再将进行pop操作，换下个数
  170.             SrackPop(&obj->pushST);
  171.             //下次我们取到的就是新的栈顶元素
  172.         }
  173.     }
  174.     //取栈顶，删除栈顶元素并返回栈顶数据
  175.     int top=StackTop(&obj->popST);//将这个栈的栈顶元素保存出来
  176.     SrackPop(&obj->popST);//将栈顶元素删除，下次就是新的栈顶元素
  177.     return top;
  178. }
  179. //取队头元素
  180. int myQueuePeek(MyQueue* obj)
  181. {
  182.     //1.检查popST是否为空
  183.        //1)不为空直接 出
  184.        //2)为空，pushST导入到popST,在出数据
  185.     if(StackEmpty(&obj->popST))//如果为空的话，我们就进项导数据操作
  186.     {
  187.         //导数据
  188.         while(!StackEmpty(&obj->pushST))//只要不为空，我们就将这个栈内的数据导出
  189.         {
  190.             //循环取栈顶数据
  191.             //StackTop(&obj->pushST)将这个栈内的栈顶数据取出
  192.             SrackPush(&obj->popST,StackTop(&obj->pushST));
  193.             //将pushST这个栈的栈顶数据导入到popST中
  194.  
  195.             //取完数据，插入完数据之后我们再将进行pop操作，换下个数
  196.             SrackPop(&obj->pushST);
  197.             //下次我们取到的就是新的栈顶元素
  198.         }
  199.     }
  200.     //取栈顶，删除栈顶元素并返回栈顶数据
  201.     return StackTop(&obj->popST);//我们直接将这个栈顶数据返回
  202.  
  203.  
  204. }
  205.  
  206. //判断我们的队列是否为空，就是判断这个队列里面的两个栈是否为空
  207. bool myQueueEmpty(MyQueue* obj)
  208. {
  209.     //如果这两个栈都不为空，那么这个队列就不为空
  210.     return StackEmpty(&obj->pushST)  &&StackEmpty(&obj->popST);
  211. }
  212.  
  213. //销毁
  214. void myQueueFree(MyQueue* obj)
  215. {
  216.     STDestory(&obj->pushST);
  217.     STDestory(&obj->popST);
  218.     free(obj);
  219.     obj=NULL;
  220. }
  221.  
  222. /**
  223.  * Your MyQueue struct will be instantiated and called as such:
  224.  * MyQueue* obj = myQueueCreate();
  225.  * myQueuePush(obj, x);
  227.  * int param_2 = myQueuePop(obj);
  229.  * int param_3 = myQueuePeek(obj);
  231.  * bool param_4 = myQueueEmpty(obj);
  233.  * myQueueFree(obj);
  234. */

题目四：设计循环队列

  1. //推荐循环队列底层队列为数组
  2.  
  3. /*
  4. 插入数据：循环队列满了，就不能插入数据
  5.  
  6.  
  7. */
  8.  
  9. /*
  10. 一开始的front指向的是数组的头元素
  11. rear也是指向数组的头元素
  12. 每次插入一个元素，rear就进行++操作
  13. 我们在下面申请了k+1个整型的空间，最后一个空间仅仅只是占位置的，不是存储数据的，实际存储数据的只有k个
  14. 假设这里是5个空间
  15. 0 1 2 3 4  这是对应的下标
  16. 一开始的front和rear都指向的是0，每次增加一个元素，rear++
  17. 等rear指向4的时候这个数组就存满了
  18.  
  19. 因为是循环，最后rear++会回到front的位置
  20. 那么我们可以通过(rear+1)%(k+1)==front来判断队列是否满了
  21. rear==front可以判断队列是否为空
  22. */
  23. //定义循环队列的结构
  24. typedef struct
  25. {
  26.     int *arr;
  27.     int rear;
  28.     int front;
  29.     int capacity;//保存数组的空间的大小k
  30. } MyCircularQueue;
  31.  
  32. //循环队列的初始化
  33. MyCircularQueue* myCircularQueueCreate(int k)//我们根据这个K进行动态的申请内存,这里的返回值是指向循环队列的指针
  34. {
  35.     MyCircularQueue*pst=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//先开辟队列的空间
  36.     //因为队列的底层结构是数组，那么我们再为数组开辟空间
  37.     pst->arr=(int*)malloc(sizeof(int)*(k+1));//我们给数组申请K+1个整型大小的空间
  38.  
  39.     pst->front=pst->rear=0;
  40.     pst->capacity=k;//循环队列的容量大小是k
  41.     return pst;
  42. }
  43. //判断队列是否满了
  44. bool myCircularQueueIsFull(MyCircularQueue* obj)
  45. {
  46.     return (obj->rear+1)%(obj->capacity+1)==obj->front;//就说明满了
  47.     //capacity+1是数组的容量大小，多出的1是用来占位置的
  48. }
  49.  
  50. //向循环队列里面插入数据，如果成功插入就返回真
  51. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
  52. {
  53.     //队列如果满了的话就不能进行插入数据的操作了
  54.     if(myCircularQueueIsFull(obj))//如果满了的话,就不能插入数据了
  55.     {
  56.         return false;
  57.     }
  58.  
  59.     //走到这里说明队列还没有满，我们就进行插数据操作
  60.     obj->arr[obj->rear++]=value;//插入完数据之后rear要进行++的操作
  61.     //为了保证循环的效果
  62.     /*
  63.     假设我们的rear此时在占位置的那个位置，就是多出来的1的那个位置
  64.     为了保证循环，我们要让rear回到数组的第一个位置 */
  65.     obj->rear%=obj->capacity+1;//obj->rear=obj->rear % (obj->capacity+1)//我们这里进行求余的操作，将结果给rear
  66.  
  67.     //插入完成我们就返回true
  68.     return true;
  69. }
  70. //判断队列是否为空
  71. bool myCircularQueueIsEmpty(MyCircularQueue* obj)
  72. {
  73.     return obj->rear==obj->front;
  74. }
  75.  
  76. //从循环队列中删除一个元素，成功删除就返回true
  77. bool myCircularQueueDeQueue(MyCircularQueue* obj)
  78. {
  79.     //既然要删除数据，那么队列就不能为空
  80.     if(myCircularQueueIsEmpty(obj))//说明这个数组为空，我们就不进行删除数据的操作了
  81.     {
  82.         return false;
  83.     }
  84.  
  85.     //走到这里说明队列不为空，那么我们就进行删除操作
  86.     obj->front++;
  87.     obj->front%=obj->capacity+1;//取余
  88.     //原先front位置的数据还在，但是我们现在front已经换位置了，那么原先位置的数据就能就行插入数据了
  89.     return true;
  90. }
  91. //取对首元素，返回对应值
  92. int myCircularQueueFront(MyCircularQueue* obj)
  93. {
  94.     //队列为空就没啥数据能取
  95.     //判断队列是否为空
  96.     if(myCircularQueueIsEmpty(obj))//队列为空的话我们直接返回-1
  97.     {
  98.         return -1;
  99.     }
  100.     return obj->arr[obj->front];
  101. }
  102. //取对尾元素，返回对应值
  103. int myCircularQueueRear(MyCircularQueue* obj)
  104. {
  105.     //队列为空就没啥数据能取
  106.     //判断队列是否为空
  107.     if(myCircularQueueIsEmpty(obj))//队列为空的话我们直接返回-1
  108.     {
  109.         return -1;
  110.     }
  111.     //return obj->arr[obj->rear-1];//rear指向的是最后一个数据的下一个位置
  112.     //假如我们的rear指向的是0下标的数，那么rear-1不就是-1吗？这么写代码就是错的，，存在越界情况
  113.     int prev=obj->rear-1;//定义一个指针指向rear前一个数据
  114.     if(obj->rear==0)
  115.     {
  116.         prev=obj->capacity;//下标为4，那么就是这个数组的第5个位置，就是最后一个位置
  117.     }
  118.     return obj->arr[prev];
  119.     //队尾元素就是rear经历过++操作之前的位置的元素
  120. }
  121.  
  122. //循环队列的销毁
  123. void myCircularQueueFree(MyCircularQueue* obj)
  124. {
  125.     free(obj->arr);
  126.     free(obj);
  127.     obj=NULL;
  128. }
  129.  
  130. /**
  131.  * Your MyCircularQueue struct will be instantiated and called as such:
  132.  * MyCircularQueue* obj = myCircularQueueCreate(k);
  133.  * bool param_1 = myCircularQueueEnQueue(obj, value);
  135.  * bool param_2 = myCircularQueueDeQueue(obj);
  137.  * int param_3 = myCircularQueueFront(obj);
  139.  * int param_4 = myCircularQueueRear(obj);
  141.  * bool param_5 = myCircularQueueIsEmpty(obj);
  143.  * bool param_6 = myCircularQueueIsFull(obj);
  145.  * myCircularQueueFree(obj);
  146. */
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/922060
推荐阅读
相关标签

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

  

闽ICP备14008679号