• 栈和队列及其多种接口实现-c语言

    今天我们来完成栈和队列，首先我们要明白什么是栈，什么是队列。

    目录

    栈的选择

    栈的结构

    栈的初始化

    栈的销毁

    入栈

    出栈

    返回栈顶元素

    计算数据个数

    判断是否为空

    队列的选择

    队列的结构

    入队列

    出队列

    判断是否为空

    取队头元素

    取队尾元素

    计算数据个数

    队列的销毁

    我们之前写过顺序表，链表，这都是数据结构，而栈和队列，也是数据结构，栈的特殊地方在于，栈是后进先出，也叫LIFO（last in first out），比如我们平时在桌子上堆放的书，我们堆放了十本书，如果不直接把书抽出来的话，我们要拿到最下面那本书，需要把上面九本先拿下去，也就是先要从最上面的那一本开始拿，而最上面的那一本，是我们最后放上去的，这就是一个栈。再说队列，队列的特殊地方在于先进先出，也叫FIFO（first in first out），比如我们日常生活里的排队就是一个队列，不考虑插队这些，正常情况下，第一个来的人一定第一个完成自己的业务，最后一个来的人最后完成，这就是一个队列。

    我们还是采取工程化的写法。

     首先我们来完成栈，栈的实现可以使用数组或者链表，那我们选取哪个比较好呢？

    栈的选择

    我们来比较一下二者的优缺点。

     

    首先我们看数组： 使用数组就相当于之前顺序表的尾插和尾删，用尾去做栈顶，非常合适，唯一的缺点是空间不足时需要扩容。完美避开了顺序表插入删除时需要挪动数据的缺点。

    我们再来看链表，链表又有多种结构，我们介绍一种使用单链表来完成的，插入和删除都只有O(1)。

    使用这种结构即可完成，最初栈顶和栈底都为空，插入第一个元素后，栈顶栈底都指向第一个元素，每次插入新元素后，只需将其赋给栈顶，删除时，先删除节点，再把栈顶指向栈顶的next即可。

    如果用尾做栈顶，那么使用双向链表最好，如果使用头做栈顶，那么单链表最好，插入删除都是O(1)。

    知道了两种结构完成栈的优缺点，大家会选择哪一个呢？我们这里选择数组来完成栈，因为使用数组的话各方面效率都会更优，这里知识和预加载有关，这里就不多介绍，我们举个例子，使用数组和链表的区别，学生时代家里每个月都会给你打生活费，数组就像是一个月给你打一次生活费，够你一个月花，链表就像每天给你打一次，很明显，使用数组要比链表效率高。

    决定好了用什么来实现栈，接着我们来完成栈的结构和各类接口

    栈的结构

    1. typedef int STDataType;
    2.  
    3. typedef struct Stack {
    4. 	STDataType* a;
    5. 	int top;
    6. 	int capacity;
    7. }ST;

    我们将其写为动态栈，即a不直接写为数组，不然就写死了，并且我们使用top来记录栈顶位置

    接着我们来完成栈的初始化

    栈的初始化

    1. void StackInit(ST* ps)//初始化
    2. {
    3. 	assert(ps);
    4. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    5. 	if (ps->a == NULL) {
    6. 		printf("malloc fail\n");
    7. 		exit(-1);
    8. 	}
    9. 	ps->capacity = 4;
    10. 	ps->top = 0;
    11. }

    这里的top选取0还是-1看自己喜欢，选取-1代表的是top就是当前栈顶元素，选取0表示top为栈顶元素的后一位，我这里选择初始赋0，同时，如果初始化失败，我们输出提示并结束程序

    栈的销毁

    1. void StackDestory(ST* ps)//销毁
    2. {
    3. 	assert(ps);
    4. 	free(ps->a);
    5. 	ps->a = NULL;
    6. 	ps->top = ps->capacity = 0;
    7. }

    入栈

    1. void StackPush(ST* ps, STDataType x)//入栈
    2. {
    3. 	assert(ps);
    4. 	if (ps->top == ps->capacity) {//满了扩容
    5. 		STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
    6. 		if (tmp == NULL) {
    7. 			printf("realloc fail\n");
    8. 			exit(-1);
    9. 		}
    10. 		else {
    11. 			ps->a = tmp;
    12. 			ps->capacity *= 2;
    13. 		}
    14. 	}
    15. 	ps->a[ps->top] = x;
    16. 	ps->top++;
    17. }

    入栈时我们要判断栈是否满了，满了需要扩容，扩容时我们扩容到原来的二倍，并且要判断是否扩容失败，失败的话我们给出提示并且结束程序，入栈后要记得给top+1

    出栈

    1. void StackPop(ST* ps)//出栈
    2. {
    3. 	assert(ps);
    4. 	assert(ps->top>0);
    5. 	ps->top--;
    6. }

    出栈我们直接使top-1，有人可能会先让栈顶元素置为0，但是这句是不需要的，因为入栈元素有时候本身就可能为0，并且我们不能随意出栈，比如top为0时，即空栈，所以我们加一句断言

    返回栈顶元素

    1. STDataType StackTop(ST* ps)//返回栈顶元素
    2. {
    3. 	assert(ps);
    4. 	assert(ps->top > 0);
    5. 	return ps->a[ps->top - 1];
    6. }

    和出栈同理，栈为空时不能返回，我们加一句断言

    计算数据个数

    1. void StackSize(ST* ps)//计算数据个数
    2. {
    3. 	assert(ps);
    4. 	return ps->top;
    5. }

    判断是否为空

    1. bool StackEmpty(ST* ps)//判断是否为空
    2. {
    3. 	assert(ps);
    4. 	return ps->top == 0;
    5. }

    我们直接return ps->top==0，使用bool类型，如果top==0，为真，返回true，否则返回false

    我们来测试一下我们的代码

    可以看到，没有问题。

     完成了栈，我们接着来看队列

    队列的选择

    和栈一样，队列也需要在数组和链表里选择一个，队列只允许在它的一端插入数据，在另一端删除数据

     这次其实我们要选择链表，因为数组会出现假溢出现象，比如这个数组可以放5个元素，现在已经放了四个，我们出队列一个元素，再入队列一个，就会发现数组下标0的位置是空的，但队列却显示已满，如果要挪动数据的话也非常麻烦，还有一种办法就是写成循环队列，但那是后续的事情，而且也有局限性。选取链表的话，用单链表就可以解决，采用上图结构，队列就只需要尾插和头删，效率都很高。

    选择好了用什么来实现队列后，我们来设计队列的结构吧

    队列的结构

    1. typedef int QDataType;
    2.  
    3. typedef struct QueueNode
    4. {
    5. 	struct QueueNode* next;
    6. 	QDataType data;
    7. }QNode;
    8.  
    9. typedef struct Queue
    10. {
    11. 	QNode* head;
    12. 	QNode* tail;
    13. }Queue;

    我们设计好队列的节点，然后采取两个指针，队头和队尾来设计队列即可。而且采用这样的结构可以避免使用二级指针（后续接口如果参数传QNode的话是需要二级指针的）

    入队列

    1. void QueuePush(Queue* pq, QDataType x)//入队列
    2. {
    3. 	assert(pq);
    4. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    5. 	if (newnode == NULL) {
    6. 		printf("malloc fail\n");
    7. 		exit(-1);
    8. 	}
    9. 	newnode->data = x;
    10. 	newnode->next = NULL;
    11. 	if (pq->tail == NULL) {
    12. 		pq->head = pq->tail = newnode;
    13. 	}
    14. 	else {
    15. 		pq->tail->next = newnode;
    16. 		pq->tail = newnode;
    17. 	}
    18. }

    入队列是在队尾入元素，入队列我们需要判断队列是否为空，入队列需要一个新节点，我们给节点申请一个空间，申请失败我们输出提示并且报错，然后将x赋给节点的data，节点的next置为空，我们还要判断队列是否有节点，如果一个没有，那么队头和队尾都指向这个新节点，否则队尾的next指向新节点，再把队尾指向新节点

    出队列

    1. void QueuePop(Queue* pq)//出队列
    2. {
    3. 	assert(pq);
    4. 	assert(pq->head);
    5. 	if (pq->head->next == NULL) {
    6. 		free(pq->head);
    7. 		pq->head = pq->tail = NULL;
    8. 	}
    9. 	else {
    10. 		Queue* next = pq->head->next;
    11. 		free(pq->head);
    12. 		pq->head = next;
    13. 	}
    14. }

    出队列是出队头元素，我们要进行断言，我们出队列需要把头节点的空间释放，然后让head指向它的next，但在释放前我们需要把head的next保存起来，否则我们就找不到next了，这是正常情况，如果队列只有一个元素，出队列后会造成tail的野指针现象，所以我们需要额外判断，所以我们把出队列分为队列有一个元素和多个元素的情况

    判断是否为空

    1. bool QueueEmpty(Queue* pq)//判断是否为空
    2. {
    3. 	assert(pq);
    4. 	return pq->head == NULL;
    5. }

    我们直接返回该判断语句即可，为空返回true，否则返回false

    取队头元素

    1. QDataType QueueFront(Queue* pq)//取队头元素
    2. {
    3. 	assert(pq);
    4. 	assert(pq->head);
    5. 	return pq->head->data;
    6. }

    我们直接返回队头元素即可，最好再加一句断言，有时候会很有用，比如初始化后，队列里没有元素，这种情况没有第二句断言我们就不知道程序哪里出现了错误

    取队尾元素

    1. QDataType QueueBack(Queue* pq)//取队尾元素
    2. {
    3. 	assert(pq);
    4. 	assert(pq->head);
    5. 	return pq->tail->data;
    6. }

    取队尾元素与取队头元素同理

    计算数据个数

    1. int QueueSize(Queue* pq)//计算数据个数
    2. {
    3. 	assert(pq);
    4. 	int size = 0;
    5. 	QNode* cur = pq->head;
    6. 	while (cur) {
    7. 		cur = cur->next;
    8. 		size++;
    9. 	}
    10. 	return size;
    11. }

    这个接口有人可能会把循环条件写成cur！=pq->tail，但这样是错误的，会少计算一个元素

    队列的销毁

    1. void QueueDestory(Queue* pq)//销毁
    2. {
    3. 	assert(pq);
    4. 	QNode* cur = pq->head;
    5. 	while (cur) {
    6. 		QNode* next = cur->next;
    7. 		free(cur);
    8. 		cur = next;
    9. 	}
    10. 	pq->head = pq->tail = NULL;
    11. }

    销毁需要注意先要保存cur的下一个，不然会找不到，然后就是最后要把head和tail置为空

    我们最后再来测试一下代码

    没有问题，到这里，我们的栈和队列以及他们的接口就全部实现了，希望大家可以有所收获，下面我会附上全部代码

    1. #pragma once
    2. //Stack.h
    3. #include 
    4. #include
    5. #include
    6. #include
    7. typedef int STDataType;
    8.  
    9. typedef struct Stack {
    10. 	STDataType* a;
    11. 	int top;
    12. 	int capacity;
    13. }ST;
    14.  
    15. void StackInit(ST* ps);//初始化
    16. void StackDestory(ST* ps);//销毁
    17. void StackPush(ST* ps,STDataType x);//入栈
    18. void StackPop(ST* ps);//出栈
    19. STDataType StackTop(ST* ps);//返回栈顶元素
    20. void StackSize(ST* ps);//计算数据个数
    21. bool StackEmpty(ST* ps);//判断是否为空

     

    1. //Stack.c
    2. #include "Stack.h"
    3. void StackInit(ST* ps)//初始化
    4. {
    5. 	assert(ps);
    6. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    7. 	if (ps->a == NULL) {
    8. 		printf("malloc fail\n");
    9. 		exit(-1);
    10. 	}
    11. 	ps->capacity = 4;
    12. 	ps->top = 0;
    13. }
    14. void StackDestory(ST* ps)//销毁
    15. {
    16. 	assert(ps);
    17. 	free(ps->a);
    18. 	ps->a = NULL;
    19. 	ps->top = ps->capacity = 0;
    20. }
    21. void StackPush(ST* ps, STDataType x)//入栈
    22. {
    23. 	assert(ps);
    24. 	if (ps->top == ps->capacity) {//满了扩容
    25. 		STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
    26. 		if (tmp == NULL) {
    27. 			printf("realloc fail\n");
    28. 			exit(-1);
    29. 		}
    30. 		else {
    31. 			ps->a = tmp;
    32. 			ps->capacity *= 2;
    33. 		}
    34. 	}
    35. 	ps->a[ps->top] = x;
    36. 	ps->top++;
    37. }
    38. void StackPop(ST* ps)//出栈
    39. {
    40. 	assert(ps);
    41. 	assert(ps->top>0);
    42. 	ps->top--;
    43. }
    44. STDataType StackTop(ST* ps)//返回栈顶元素
    45. {
    46. 	assert(ps);
    47. 	assert(ps->top > 0);
    48. 	return ps->a[ps->top - 1];
    49. }
    50. void StackSize(ST* ps)//计算数据个数
    51. {
    52. 	assert(ps);
    53. 	return ps->top;
    54. }
    55. bool StackEmpty(ST* ps)//判断是否为空
    56. {
    57. 	assert(ps);
    58. 	return ps->top == 0;
    59. }
    1. #pragma once
    2. //Queue.h
    3. #include 
    4. #include
    5. #include
    6. #include
    7. typedef int QDataType;
    8.  
    9. typedef struct QueueNode
    10. {
    11. 	struct QueueNode* next;
    12. 	QDataType data;
    13. }QNode;
    14.  
    15. typedef struct Queue
    16. {
    17. 	QNode* head;
    18. 	QNode* tail;
    19. }Queue;
    20.  
    21. void QueueInit(Queue* pq);//初始化
    22. void QueueDestory(Queue* pq);//销毁
    23. void QueuePush(Queue* pq, QDataType x);//入队列
    24. void QueuePop(Queue* pq);//出队列
    25. QDataType QueueFront(Queue* pq);//取队头元素
    26. QDataType QueueBack(Queue* pq);//取队尾元素
    27. int QueueSize(Queue* pq);//取数据个数
    28. bool QueueEmpty(Queue* pq);//判断是否为空
    1. //Queue.c
    2. #include"Queue.h"
    3.  
    4. void QueueInit(Queue* pq)//初始化
    5. {
    6. 	assert(pq);
    7. 	pq->head = pq->tail = NULL;
    8. }
    9. void QueueDestory(Queue* pq)//销毁
    10. {
    11. 	assert(pq);
    12. 	QNode* cur = pq->head;
    13. 	while (cur) {
    14. 		QNode* next = cur->next;
    15. 		free(cur);
    16. 		cur = next;
    17. 	}
    18. 	pq->head = pq->tail = NULL;
    19. }
    20. void QueuePush(Queue* pq, QDataType x)//入队列
    21. {
    22. 	assert(pq);
    23. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    24. 	if (newnode == NULL) {
    25. 		printf("malloc fail\n");
    26. 		exit(-1);
    27. 	}
    28. 	newnode->data = x;
    29. 	newnode->next = NULL;
    30. 	if (pq->tail == NULL) {
    31. 		pq->head = pq->tail = newnode;
    32. 	}
    33. 	else {
    34. 		pq->tail->next = newnode;
    35. 		pq->tail = newnode;
    36. 	}
    37. }
    38. void QueuePop(Queue* pq)//出队列
    39. {
    40. 	assert(pq);
    41. 	assert(pq->head);
    42. 	if (pq->head->next == NULL) {
    43. 		free(pq->head);
    44. 		pq->head = pq->tail = NULL;
    45. 	}
    46. 	else {
    47. 		Queue* next = pq->head->next;
    48. 		free(pq->head);
    49. 		pq->head = next;
    50. 	}
    51. }
    52. QDataType QueueFront(Queue* pq)//取队头元素
    53. {
    54. 	assert(pq);
    55. 	assert(pq->head);
    56. 	return pq->head->data;
    57. }
    58. QDataType QueueBack(Queue* pq)//取队尾元素
    59. {
    60. 	assert(pq);
    61. 	assert(pq->head);
    62. 	return pq->tail->data;
    63. }
    64. int QueueSize(Queue* pq)//计算数据个数
    65. {
    66. 	assert(pq);
    67. 	int size = 0;
    68. 	QNode* cur = pq->head;
    69. 	while (cur) {
    70. 		cur = cur->next;
    71. 		size++;
    72. 	}
    73. 	return size;
    74. }
    75. bool QueueEmpty(Queue* pq)//判断是否为空
    76. {
    77. 	assert(pq);
    78. 	return pq->head == NULL;
    79. }
    1. //test.c
    2. #include "Stack.h"
    3. #include"Queue.h"
    4. void testStack() {
    5. 	ST st;
    6. 	StackInit(&st);
    7. 	StackPush(&st, 1);
    8. 	StackPush(&st, 2);
    9. 	StackPush(&st, 3);
    10. 	StackPush(&st, 4);
    11. 	while (!StackEmpty(&st)) {
    12. 		printf("%d ", StackTop(&st));
    13. 		StackPop(&st);
    14. 	}
    15.  
    16. 	StackDestory(&st);
    17. }
    18.  
    19. void testQueue() {
    20. 	Queue q;
    21. 	QueueInit(&q);
    22. 	QueuePush(&q, 1);
    23. 	QueuePush(&q, 2);
    24. 	QueuePush(&q, 3);
    25. 	QueuePush(&q, 4);
    26. 	while (!QueueEmpty(&q)) {
    27. 		printf("%d ", QueueFront(&q));
    28. 		QueuePop(&q);
    29. 	}
    30. 	QueueDestory(&q);
    31. }
    32. int main() {
    33. 	//testStack();
    34. 	testQueue();
    35. 	return 0;
    36. }

    如有错误，还请指正。

  • 相关阅读:
    vue3学习（二）--- ref和reactive
    2022年程序员“生存报告”出炉，仅23%月薪不足1万，你在什么段位？
    对游戏的底层逻辑发起改变的区块链
    2024上海MWC 参展预告 | 未来先行，解锁数字化新纪元！
    【硬件专题】案例：热敏打印效果差？为什么是多个因素造成的？
    Maxcompute SQL 的查询结果条数受限1W
    Linux学习之：进程概念
    机器学习之朴素贝叶斯
    什么是用来评估神经网络,神经网络的数据预处理
    1.8 Elasticsearch建立IK中文分词器
  • 原文地址：https://blog.csdn.net/KLZUQ/article/details/128037639