• 【数据结构初阶】一文详解顺序栈和链队列的基本操作

    目录

    1.栈的概念

     2.栈的结构

     3.实现栈的基本操作

    3.1栈的初始化

    3.2压栈

    3.3出栈

    3.4 取栈顶元素

    3.5 计算栈内元素个数

    3.6栈的判空

    3.7栈的销毁

    4.源代码

    4.1stack.c

    4.2stack.h

    4.3test.c

     4.4效果

    1.队列的概念

     2.队列的结构

     3.实现队列的基本操作

    3-1结构体定义

    3-2队列的初始化

    3-3入队列

    3-4出队列

    3-5取队头元素

    3-6取队尾元素

    3-7队列判空

    3-8队列长度

    3-9队列销毁

    4.源代码

    4-1queue.c

    4.2queue.h

    4.3test.c

    4.4效果图

    1.栈的概念

    栈，一种特殊的线性表，特殊在于只允许在固定的一端进行插入删除数据，插入和删除数据的一端是栈顶，另一端是栈底，已经在栈中的数据满足Fist In  Last Out的原则。

    压栈：栈顶插入数据

    出栈：栈顶弹出数据

     

     2.栈的结构

    总体而言，用顺序表和链表实现都可以，但是由于栈只支持在栈顶插入删除数据，且要满足后进先出，而顺序表尾插尾删的效率比链表高，（顺序表唯一的缺点在这就是扩容有性能和空间的消耗）同时也满足后进先出的原则，所以选择顺序表实现好！

    有人可能会说用链表，然后定义一个尾指针，这样尾插效率不是也很高吗？

    答：定义一个尾指针，链表的插入时很方便，但是尾删呐？？

    其实顺序表，双向循环链表，头上操作单链表都行，但是由于顺序表命中率高的优点，还是选择顺序表。

     3.实现栈的基本操作

    3.1栈的初始化

    1.  选择哪一个方式初始化top都可以，但是记得做到和后面的push等做到统一。
    2.  建议再主函数内判空操作不直接自己if(ps->top==0)等，因为这个内部怎么实现的不一定是初始化为ps->top=0,而是建议调用函数去判空if(StackEmpty(&ST))
    1. void StackInit(Stack* ps)
    2. {
    3. 	assert(ps);
    4. 	ps->a = NULL;
    5. 	ps->top = ps->capacity = 0;
    6. }

    3.2压栈

    1. void StackPush(Stack* ps, STDateType x)
    2. {
    3. 	assert(ps);
    4.  
    5. 	if(ps->top == ps->capacity)
    6. 	{
    7. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
    8. 		STDateType* temp = (STDateType*)realloc(ps->a, sizeof(STDateType)*newcapacity);
    9. 		if (temp == NULL)
    10. 		{
    11. 			perror("malloc fail.\n");
    12. 			exit(-1);
    13. 		}
    14. 		ps->capacity = newcapacity;
    15. 		ps->a = temp;
    16. 	}
    17. 	ps->a[ps->top] = x;
    18. 	ps->top++;
    19. }

    3.3出栈

     

    1. void StackPop(Stack* ps)
    2. {
    3. 	assert(ps);
    4. 	assert(!StackEmpty(ps));
    5. 	ps->top--;
    6. }

    3.4 取栈顶元素

    1. STDateType StackTop(Stack* ps)
    2. {
    3. 	assert(ps);
    4. 	assert(!StackEmpty(ps));
    5. 	return ps->a[ps->top - 1];
    6. }

    3.5 计算栈内元素个数

    1. int StackSize(Stack* ps)
    2. {
    3. 	assert(ps);
    4. 	return ps->top;
    5. }

    3.6栈的判空

    1. bool StackEmpty(Stack* ps)
    2. {
    3. 	assert(ps);
    4. 	return ps->top == 0;
    5. }

    3.7栈的销毁

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

    4.源代码

    4.1stack.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"stack.h"
    3. void StackInit(Stack* ps)
    4. {
    5. 	assert(ps);
    6. 	ps->a = NULL;
    7. 	ps->top = ps->capacity = 0;
    8. }
    9.  
    10. void StackPush(Stack* ps, STDateType x)
    11. {
    12. 	assert(ps);
    13.  
    14. 	if(ps->top == ps->capacity)
    15. 	{
    16. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;
    17. 		STDateType* temp = (STDateType*)realloc(ps->a, sizeof(STDateType)*newcapacity);
    18. 		if (temp == NULL)
    19. 		{
    20. 			perror("malloc fail.\n");
    21. 			exit(-1);
    22. 		}
    23. 		ps->capacity = newcapacity;
    24. 		ps->a = temp;
    25. 	}
    26. 	ps->a[ps->top] = x;
    27. 	ps->top++;
    28. }
    29.  
    30. void StackPop(Stack* ps)
    31. {
    32. 	assert(ps);
    33. 	assert(!StackEmpty(ps));
    34. 	ps->top--;
    35. }
    36.  
    37. STDateType StackTop(Stack* ps)
    38. {
    39. 	assert(ps);
    40. 	assert(!StackEmpty(ps));
    41. 	return ps->a[ps->top - 1];
    42. }
    43.  
    44. int StackSize(Stack* ps)
    45. {
    46. 	assert(ps);
    47. 	return ps->top;
    48. }
    49.  
    50. bool StackEmpty(Stack* ps)
    51. {
    52. 	assert(ps);
    53. 	return ps->top == 0;
    54. }
    55.  
    56.  
    57. void StackDestory(Stack* ps)
    58. {
    59. 	assert(ps);
    60. 	free(ps->a);
    61. 	ps->a = NULL;
    62. 	ps->top = ps->capacity = 0;
    63. }

    4.2stack.h

     

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. typedef int STDateType;
    8. typedef struct Stack
    9. {
    10. 	STDateType* a;
    11. 	int top;
    12. 	int capacity;
    13. }Stack;
    14.  
    15. void StackInit(Stack* ps);
    16.  
    17. void StackPush(Stack* ps,STDateType x);
    18.  
    19. void StackPop(Stack* ps);
    20.  
    21. STDateType StackTop(Stack* ps);
    22.  
    23. bool StackEmpty(Stack* ps);
    24.  
    25. int StackSize(Stack* ps);
    26.  
    27. void StackDestory(Stack* ps);
    28.

    4.3test.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"stack.h"
    3.  
    4.  
    5. int main()
    6. {
    7. 	Stack ST;
    8. 	StackInit(&ST);
    9. 	StackPush(&ST, 1);
    10. 	StackPush(&ST, 2);
    11. 	StackPush(&ST, 3);
    12. 	StackPush(&ST, 4);
    13. 	STDateType top = StackTop(&ST);
    14. 	printf("top:%d\n", top);
    15. 	StackPop(&ST);
    16. 	top = StackTop(&ST);
    17. 	printf("top:%d\n", top);
    18. 	int size = StackSize(&ST);
    19. 	printf("size:%d\n", size);
    20. 	StackDestory(&ST);
    21. 	return 0;
    22. }

     4.4效果图

    1.队列的概念

    队列是一种特殊的线性表，特殊在只能从一端进行插入操作，另一端进行删除操作，队列具有Fist  In First Out的原则。

    队尾：进行插入操作的一端，这个过程叫做入队列

    队头：进行删除操作的一端，这个过程叫做出队列

    抽号机：先来先服务，先给号码排队 （涉及嵌入式）

     

     

     2.队列的结构

    队列我们采用链表实现：顺序表在满了要扩容，删完了后再入队列的时候还得扩容

    链表的话，入队列就是尾插，定义一个尾指针。出队列就是头删，定义一个头指针

     3.实现队列的基本操作

    3-1结构体定义

     

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

    3-2队列的初始化

    这里的链表队列我并没有带头，没有带头就要在入队列和出队列时有一点特殊情况的考虑

    1. void QueueInit(Queue* ps)
    2. {
    3. 	assert(ps);
    4. 	ps->head = ps->tail = NULL;
    5. }

    3-3入队列

    相当于尾插，考虑特殊情况：队列为空的情况

    1. //入队列：尾插
    2. void QueuePush(Queue* ps,QDateType x)
    3. {
    4. 	assert(ps);
    5. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    6. 	newnode->next = NULL;
    7. 	newnode->val = x;
    8. 	if (newnode == NULL)
    9. 	{
    10. 		perror("malloc fail.");
    11. 		exit(-1);
    12. 	}
    13. 	if (ps->tail == NULL)
    14. 	{
    15. 		ps->head = ps->tail = newnode;
    16. 	}
    17. 	else
    18. 	{
    19. 		ps->tail->next = newnode;
    20. 		ps->tail = ps->tail->next;
    21. 	}
    22. }

    3-4出队列

    相当于头删，考虑特殊情况：只有一个结点的情况，出队列后要改变ps->tail

    1. void QueuePop(Queue* ps)
    2. {
    3. 	assert(ps);
    4. 	assert(!QueueEmpty(ps));
    5. 	if (ps->head->next == NULL)
    6. 	{
    7. 		free(ps->head);
    8. 		ps->head = ps->tail = NULL;
    9. 	}
    10. 	else
    11. 	{
    12. 		QueueNode* next = ps->head->next;
    13. 		free(ps->head);
    14. 		ps->head = next;
    15.  
    16. 	} 
    17. }

    3-5取队头元素

    1. QDateType QueueFront(Queue* ps)
    2. {
    3. 	assert(ps);
    4. 	assert(!QueueEmpty(ps));
    5. 	return ps->head->val;
    6. }

    3-6取队尾元素

    1. QDateType QueueBack(Queue* ps)
    2. {
    3. 	assert(ps);
    4. 	assert(!QueueEmpty(ps));
    5. 	return ps->tail->val;
    6. }

    3-7队列判空

    1. bool QueueEmpty(Queue* ps)
    2. {
    3. 	assert(ps);
    4. 	return ps->tail == NULL;
    5. }

    3-8队列长度

    1. int QueueSize(Queue* ps)
    2. {
    3. 	assert(ps);
    4. 	int size = 0;
    5. 	QueueNode* cur = ps->head;
    6. 	while(cur)
    7. 	{
    8. 		++size;
    9. 		cur = cur->next;
    10. 	}
    11. 	return size;
    12. }

    3-9队列销毁

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

    4.源代码

    4-1queue.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"queue.h"
    3.  
    4. void QueueInit(Queue* ps)
    5. {
    6. 	assert(ps);
    7. 	ps->head = ps->tail = NULL;
    8. }
    9.  
    10. void QueueDestory(Queue* ps)
    11. {
    12. 	assert(ps);
    13. 	QueueNode* cur = ps->head;
    14. 	while (cur)
    15. 	{
    16. 		QueueNode* next = cur->next;
    17. 		free(cur);
    18. 		cur = next;
    19. 	}
    20. 	ps->head = ps->tail = NULL;
    21. }
    22.  
    23. //入队列：尾插
    24. void QueuePush(Queue* ps,QDateType x)
    25. {
    26. 	assert(ps);
    27. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    28. 	newnode->next = NULL;
    29. 	newnode->val = x;
    30. 	if (newnode == NULL)
    31. 	{
    32. 		perror("malloc fail.");
    33. 		exit(-1);
    34. 	}
    35. 	if (ps->tail == NULL)
    36. 	{
    37. 		ps->head = ps->tail = newnode;
    38. 	}
    39. 	else
    40. 	{
    41. 		ps->tail->next = newnode;
    42. 		ps->tail = ps->tail->next;
    43. 	}
    44. }
    45.  
    46. void QueuePop(Queue* ps)
    47. {
    48. 	assert(ps);
    49. 	assert(!QueueEmpty(ps));
    50. 	if (ps->head == ps->tail)
    51. 	{
    52. 		free(ps->head);
    53. 		ps->head = ps->tail = NULL;
    54. 	}
    55. 	else
    56. 	{
    57. 		QueueNode* next = ps->head->next;
    58. 		free(ps->head);
    59. 		ps->head = next;
    60.  
    61. 	} 
    62. }
    63.  
    64. QDateType QueueFront(Queue* ps)
    65. {
    66. 	assert(ps);
    67. 	assert(!QueueEmpty(ps));
    68. 	return ps->head->val;
    69. }
    70.  
    71. QDateType QueueBack(Queue* ps)
    72. {
    73. 	assert(ps);
    74. 	assert(!QueueEmpty(ps));
    75. 	return ps->tail->val;
    76. }
    77.  
    78. bool QueueEmpty(Queue* ps)
    79. {
    80. 	assert(ps);
    81. 	return ps->tail == NULL;
    82. }
    83.  
    84. int QueueSize(Queue* ps)
    85. {
    86. 	assert(ps);
    87. 	int size = 0;
    88. 	QueueNode* cur = ps->head;
    89. 	while(cur)
    90. 	{
    91. 		++size;
    92. 		cur = cur->next;
    93. 	}
    94. 	return size;
    95. }

    4.2queue.h

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7.  
    8. typedef int QDateType;
    9. typedef struct QueueNode
    10. {
    11. 	struct QueueNode* next;
    12. 	QDateType val;
    13. }QueueNode;
    14.  
    15. typedef struct Queue
    16. {
    17. 	QueueNode* head;
    18. 	QueueNode* tail;
    19. }Queue;
    20.  
    21. void QueueInit(Queue* ps);
    22.  
    23. void QueuePush(Queue* ps, QDateType x);
    24.  
    25. void QueuePop(Queue* ps);
    26.  
    27. QDateType QueueFront(Queue* ps);
    28.  
    29. QDateType QueueBack(Queue* ps);
    30.  
    31. bool QueueEmpty(Queue* ps);
    32.  
    33. int QueueSize(Queue* ps);
    34.  
    35. void QueueDestory(Queue* ps);

    4.3test.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"queue.h"
    3.  
    4.  
    5. int main()
    6. {
    7. 	Queue Q;
    8. 	QueueInit(&Q);
    9. 	QueuePush(&Q, 1);
    10. 	QueuePush(&Q, 2);
    11. 	QueuePush(&Q, 3);
    12. 	QueuePush(&Q, 4);
    13. 	QueuePush(&Q, 5);
    14. 	QDateType ret1 = QueueFront(&Q);
    15. 	printf("QueueFront:%d\n", ret1);
    16. 	QDateType ret2 = QueueBack(&Q);
    17. 	printf("QueueBack:%d\n", ret2);
    18. 	int size = QueueSize(&Q);
    19. 	printf("size：%d\n", size);
    20. 	while (!QueueEmpty(&Q))
    21. 	{
    22. 		printf("%d", QueueFront(&Q));
    23. 		QueuePop(&Q);
    24. 	}
    25. 	QueueDestory(&Q);
    26. 	return 0;
    27. }

    4.4效果图

     制作不易，敬请三连

  • 相关阅读:
    迈德威视工业相机 Linux驱动详细步骤
    智慧学习环境移动智能终端零信任安全机制改进方案
    [Python进阶] 消息框、弹窗：tkinter库
    spring5.3 十四：spring AOP源码分析
    基于JSP的图书销售管理系统
    web框架之路由列表及SQL语句查询数据库数据替换模板变量
    大华智慧园区前台任意文件上传(1day)
    Linux脚本练习之script083-nginx日志分析之查询某个IP的详细访问情况
    大学生川菜网页制作教程 学生HTML静态美食菜品网页设计作业成品 简单网页制作代码 学生美食网页作品免费设计
    【k8s】4、资源管理命令-陈述式
  • 原文地址：https://blog.csdn.net/qq_64428099/article/details/126173181