【数据结构】栈和队列

栈

**栈：**一种特殊的数据结构，其只答应在固定的一段举行插入和删除元素的操纵。举行数据插入和删除的一端叫栈顶，另一端叫栈底。栈中元素遵照后进先出的原则
栈在逻辑上是线性的，物理结构上也是线性的，属于线性表的一种
压栈：栈的插入数据操纵叫做压栈，进栈，入栈，从栈顶进入
出栈：栈删除数据操纵叫做出栈，从栈顶出

栈一样平常可以由数组和链表实现，相对而言，选用数组会比利用链表的代价小
选用数组来实现栈：
选择用双向链表来实现栈：相比力单链表，双向链表多出一个指针，在差别的操纵系统下，指针的大小是差别的，32位：4字节，64位：8字节，而这些空间的消耗实在是没必要的。
选用单链表实现栈：相比于双向链表，单链表节流了的空间，但是，用单链表实现栈，在每次插入或者删除数据时，都必要举行内存的申请与释放操纵，频繁的申请空间释放空间是会低沉步伐的服从的。
选用数组实现栈：用数组实现栈既解决了双向链表不必要的空间消耗问题也解决了频繁申请与释放空间的问题，固然数组存在性能的消耗，但是相比力另外两种实现方式，这是最优的选择。
   栈里面的数据不能被遍历也不能被随机访问，这是由栈的特性决定的（后进先出，只能在一端举行插入与删除操纵）
  栈的实现

首先，创建两个文件，一个是Stack.c文件，用来实现函数，一个是Stack.h文件，这里存放对应的头文件、栈的定义与函数的定义。
栈的定义

1. typedef int STDataType;//当后面需求变更时，只需要修改int就行，比如要存储字符型，只需要把Int改成char就行。
3. typedef struct Stack
4. {
5.         STDataType* arr;
6.         int capacity;//栈空间的大小
7.         int top;//栈顶
8. }ST;

复制代码

栈的初始化

1. //.h文件下
2. void StackInit(ST*ps);//初始化栈

复制代码

1. //.c文件下
2. void StackInit(ST* ps)//初始化栈
3. {
4.         ps->arr = NULL;
5.         ps->capacity = ps->top = 0;
6. }

复制代码

栈的销毁

1. //.h文件下
2. void StackDestroy(ST*ps);//栈的销毁

复制代码

1. //.c文件下
2. void StackDestroy(ST* ps)//栈的销毁
3. {
4.         assert(ps);
5.         if (ps->arr)
6.                 free(ps->arr);
7.         ps->arr = NULL;
8.         ps->capacity = ps->top = 0;
9. }

复制代码

入栈

1. //.h
2. void StackPush(ST*ps,STDataType x);//入栈

复制代码

1. void StackPush(ST* ps, STDataType x)//入栈
2. {
3.         assert(ps);
4.         if (ps->capacity==ps->top)//空间不足
5.         {//当空间大小与有效数据个数相同时表示栈空间用完了
6.                 int newnode = ps->capacity == 0 ? 4 : 2 * ps->capacity;
7.                 STDataType* tmp = (STDataType*)realloc(ps->arr,newnode*sizeof(STDataType));
8.                 assert(tmp);
9.                 ps->arr = tmp;
10.                 ps->capacity = newnode;
11.         }
12.         ps->arr[ps->top++] = x;
13. }

复制代码

出栈

1. //.h
2. bool StackEmpty(ST*ps);//判断栈是否位空]
3. void StackPop(ST*ps);//出栈

复制代码

1. //.c
2. bool StackEmpty(ST* ps)//判断栈是否位空
3. {
4.         assert(ps);
5.         return ps->top == 0;
6. }
7. void StackPop(ST* ps)//出栈
8. {
9.         assert(ps);
10.         assert(!StackEmpty(ps));//判断栈是否为空
12.         --ps->top;
13. }

复制代码

获取栈顶元素与栈中有用元素个数

1. //.h
2. STDataType StackTop(ST*ps);//获取栈顶元素
4. STDataType STSize(ST*ps);//获取有效元素个数

复制代码

1. //.h
2. STDataType StackTop(ST* ps)//获取栈顶元素
3. {
4.         assert(ps);
5.         assert(!StackEmpty(ps));
6.         return ps->arr[ps->top-1];
7. }
9. STDataType STSize(ST* ps)//获取有效元素个数
10. {
11.         assert(ps);
12.         return ps->top;
13. }

复制代码

完整代码

1. //.h文件
2. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. #include<stdbool.h>
8. typedef int STDataType;
10. typedef struct Stack
11. {
12.         STDataType* arr;
13.         int capacity;//栈空间的大小
14.         int top;//栈顶
15. }ST;
17. void StackInit(ST*ps);//初始化栈
18. void StackDestroy(ST*ps);//栈的销毁
20. void StackPush(ST*ps,STDataType x);//入栈
21. void StackPop(ST*ps);//出栈
22. bool StackEmpty(ST*ps);//判断栈是否位空]
24. STDataType StackTop(ST*ps);//获取栈顶元素
26. STDataType STSize(ST*ps);//获取有效元素个数

复制代码

1. //.c文件
2. #include"Stack.h"
4. void StackInit(ST* ps)//初始化栈
5. {
6.         ps->arr = NULL;
7.         ps->capacity = ps->top = 0;
8. }
10. void StackDestroy(ST* ps)//栈的销毁
11. {
12.         assert(ps);
13.         if (ps->arr)
14.                 free(ps->arr);
15.         ps->arr = NULL;
16.         ps->capacity = ps->top = 0;
17. }
20. void StackPush(ST* ps, STDataType x)//入栈
21. {
22.         assert(ps);
23.         if (ps->capacity==ps->top)//空间不足
24.         {
25.                 int newnode = ps->capacity == 0 ? 4 : 2 * ps->capacity;
26.                 STDataType* tmp = (STDataType*)realloc(ps->arr,newnode*sizeof(STDataType));
27.                 assert(tmp);
28.                 ps->arr = tmp;
29.                 ps->capacity = newnode;
30.         }
31.         ps->arr[ps->top++] = x;
32. }
34. void StackPop(ST* ps)//出栈
35. {
36.         assert(ps);
37.         assert(!StackEmpty(ps));
39.         --ps->top;
40. }
42. bool StackEmpty(ST* ps)//判断栈是否位空
43. {
44.         assert(ps);
45.         return ps->top == 0;
46. }
48. STDataType StackTop(ST* ps)//获取栈顶元素
49. {
50.         assert(ps);
51.         assert(!StackEmpty(ps));
52.         return ps->arr[ps->top-1];
53. }
55. STDataType STSize(ST* ps)//获取有效元素个数
56. {
57.         assert(ps);
58.         return ps->top;
59. }

复制代码

队列

队列：只答应在一段举行插入数据，在另一端举行插入数据的特殊线性表，队列，先进先出
底层由链表来实现，固然数=数组也可以，但是数组服从低。完整代码如下：

1. .c
2. #pragma once
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<assert.h>
6. #include<stdbool.h>
8. typedef int QDataType;
9. typedef struct QueueNode//队列节点
10. {
11.         QDataType data;
12.         struct QueueNode* next;
13. }QueueNode;
15. typedef struct Queue
16. {
17.         QueueNode* phead;
18.         QueueNode* ptail;
19.         int size;//节点个数
20. }Queue;
22. void QueueInit(Queue*pq);//队列初始化
23. void QueuePush(Queue*pq,QDataType x);//队列插入数据
24. bool QueueEmpty(Queue*pq);//判断队列是否为空
25. void QueuePop(Queue*pq);//删除队列数据
26. QDataType QueueFront(QueueNode*pq);//取对头数据
27. QDataType QueueAfter(Queue* pq);//取队尾数据
29. int QueueSize(Queue*pq);//取有效数据个数
31. void QueueDestroy(Queue*pq);//队列的销毁

复制代码

1. .c
2. #include"Queue.h"
4. void QueueInit(Queue* pq)//队列初始化
5. {
6.         assert(pq);
7.         pq->phead = pq->ptail = NULL;
8.         pq->size = 0;
9. }
11. void QueuePush(Queue* pq, QDataType x)//队列插入数据
12. {
13.         assert(pq);
14.         QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
15.         assert(newnode);
16.         newnode->data = x;
17.         newnode->next = NULL;
18.         if (pq->phead==NULL)//队列为空
19.         {
20.                 pq->phead = pq->ptail = newnode;
21.         }
22.         else//队列不为空
23.         {
24.                 pq->ptail->next = newnode;
25.                 pq->ptail = newnode;
26.         }
27.         pq->size++;
28. }
30. bool QueueEmpty(Queue* pq)//判断队列是否为空
31. {
32.         assert(pq);
33.         return pq->phead == NULL;
34. }
35. void QueuePop(Queue* pq)//删除队列数据
36. {
37.         assert(pq);
38.         assert(!QueueEmpty(&pq));
39.         if (pq->phead==pq->ptail)
40.         {
41.                 free(pq->phead);
42.                 pq->phead = pq->ptail = NULL;
43.         }
44.         else
45.         {
46.                 QueueNode* next = pq->phead->next;
47.                 free(pq->phead);
48.                 pq->phead = next;
49.         }
50.         --pq->size;
51. }
53. QDataType QueueFront(Queue* pq)//取队头数据
54. {
55.         assert(pq);
56.         assert(!QueueEmpty(&pq));
58.         return pq->phead->data;
59. }
61. QDataType QueueAfter(Queue* pq)//取队尾数据
62. {
63.         assert(pq);
64.         assert(!QueueEmpty(&pq));
66.         return pq->ptail->data;
67. }
69. int QueueSize(Queue* pq)//取有效数据个数
70. {
71.         assert(pq);
72.         return pq->size;
73. }
75. void QueueDestroy(Queue* pq)//队列的销毁
76. {
77.         assert(pq);
78.         assert(!QueueEmpty(&pq));
79.         QueueNode* pcur = pq->phead;
80.         while (pcur)
81.         {
82.                 QueueNode* next = pcur->next;
83.                 free(pcur);
84.                 pcur = next;
85.         }
86.         pq->phead = pq->ptail = NULL;
87.         pq->size = 0;
88. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。