• 栈 和 队列

    1、栈

    1.1栈的概念

    栈是一种特殊的线性表，只能在一端进行插入或者删除。表中允许进行插入或者删除的一端成为栈顶，表的另一端叫做栈底。当栈中没有元素时称为空栈，栈的插入操作称为入栈，栈的删除操作称为出栈。

    栈主要的特点就是后进先出。即就是后进栈的元素先出栈，每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素，每次出栈的元素都是当前栈顶的元素。

     

    如上图所示就是栈的插入（进栈）和删除（出栈），大家可以看到，我在图中标记了一个top的位置，这个位置其实表示的就是栈顶元素的下一个位置，因为我们习惯性定义一个变量把它的初始化置为0，但是又要和栈里面有一个元素区分，所以我们将top指向的位置表示成栈顶元素的下一个，就可以可以理解为：top一开始为0，当进栈一个元素时，插入在top的位置，top++。 

     1.2栈的实现

    栈的实现一般可以使用 数组或者链表实现 ，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

     

     1.2.1初始化

    1. void STInit(ST* pst)//初始化
    2. {
    3. 	assert(pst);
    4. 	pst->a = NULL;
    5. 	pst->capacity = 0;
    6. 	pst->top = 0;//栈顶元素下一个位置；
    7. }

     1.2.2销毁

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

     1.2.3入栈

    1. void STPush(ST* pst, STDatatype x)//入栈；
    2. {
    3. 	assert(pst);
    4. 	if (pst->top == pst->capacity)
    5. 	{
    6. 		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
    7. 		STDatatype* tmp =(STDatatype *) realloc(pst->a, sizeof(STDatatype) * newcapacity);
    8. 		if (tmp == NULL)
    9. 		{
    10. 			perror("realloc");
    11. 			return;
    12. 		}
    13. 		pst->a = tmp;
    14. 		pst->capacity = newcapacity;
    15. 	}
    16. 	pst->a[pst->top] = x;
    17. 	pst->top++;
    18.  
    19. }

     1.2.4出栈

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

     1.2.5栈顶元素

    1. STDatatype STTop(ST* pst)
    2. {
    3. 	assert(pst);
    4. 	return pst->a[pst->top-1];
    5. }

    1.2.6判断空

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

    2、队列

    2.1队列的概念

    队列，它也是一种操作受限制的线性表，只允许它在表的一端进行插入，而在表的另一端删除操作。把进行插入一端的称为队尾，把进行删除一端的称为对首。向队列中插入新元素称为进队，先元素进队后就成为新的队尾元素；从队列中删除元素称为出队，元素出队后，他后面的元素就成为新的队首元素。

    由于队列的插入和删除操作分别是在各自一端操作的，每个元素必然按照进入的次序出队，所以队列最显著的特点就是先进先出。

    队列的进队出队如上图所示

    2.2队列的实现

    队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

    2.2.1初始化

    1. void QueueInit(Queue* pq)//初始化；
    2. {
    3. 	assert(pq);
    4. 	pq->phead = NULL;
    5. 	pq->ptail = NULL;
    6. 	pq->Queuesize = 0;
    7. }

    2.2.2销毁

    1. void QueueDestroy(Queue* pq)//销毁
    2. {
    3. 	assert(pq);
    4. 	QNode* cur = pq->phead;
    5. 	while (cur)
    6. 	{
    7. 		QNode* Next = cur->next;
    8. 		free(cur);
    9. 		cur = Next;
    10. 	}
    11. 	pq->phead = NULL;
    12. 	pq->ptail = NULL;
    13. 	pq->Queuesize = 0;
    14. }

    2.2.3入队

    1. void QueuePush(Queue* pq, QDatatype x)//进队
    2. {
    3. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    4. 	if (newnode == NULL)
    5. 	{
    6. 		perror("malloc");
    7. 		return;
    8. 	}
    9. 	newnode->data = x;
    10. 	newnode->next = NULL;
    11. 	if (pq->ptail == NULL)
    12. 	{
    13. 		pq->ptail = pq->phead = newnode;
    14. 	}
    15. 	else
    16. 	{
    17. 		pq->ptail->next=newnode;
    18. 		pq->ptail = newnode;
    19. 	}
    20. 	pq->Queuesize++;
    21. }

    2.2.4出队

    1. void QueuePop(Queue* pq)//出队
    2. {
    3. 	assert(pq);
    4. 	assert(pq->phead);
    5. 	QNode* cur = pq->phead;
    6. 	if (cur->next == NULL)
    7. 	{
    8. 		free(cur);
    9. 		cur = NULL;
    10. 		pq->phead = pq->ptail = NULL;
    11.  
    12. 	}
    13. 	else
    14. 	{
    15. 		pq->phead = pq->phead->next;
    16. 		free(cur);
    17. 		cur = NULL;
    18. 	}
    19. 	pq->Queuesize--;
    20. }

    2.2.5返回队首元素

    1. QDatatype QueueFront(Queue* pq)//返回队首元素;
    2. {
    3. 	assert(pq);
    4. 	assert(pq->phead);
    5. 	return pq->phead->data;
    6.  
    7. }

    2.2.6队尾元素

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

    2.2.7判空

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

    2.2.8队内元素个数

    1. int QueueSize(Queue* pq)//队里面个数
    2. {
    3. 	assert(pq);
    4. 	return pq->Queuesize;
    5. }

    3、源码

    3.1栈的实现源码

    1. #include<stdio.h>
    2. #include<assert.h>
    3. #include<stdlib.h>
    4. #include<stdbool.h>
    5. typedef int STDatatype;
    6. typedef struct stack
    7. {
    8. 	STDatatype* a;
    9. 	int top;
    10. 	int capacity;
    11. }ST;
    12. void STInit(ST* pst);//初始化
    13. void STDestroy(ST* pst);//销毁
    14. void STPush(ST* pst,STDatatype x);//入栈；
    15. void STPop(ST* pst);//出栈；
    16. STDatatype STTop(ST* pst);//栈顶元素；
    17. bool STEmpty(ST* pst);//判断是否为空
    18. void STInit(ST* pst)//初始化
    19. {
    20. 	assert(pst);
    21. 	pst->a = NULL;
    22. 	pst->capacity = 0;
    23. 	pst->top = 0;//栈顶元素下一个位置；
    24. }
    25. void STDestroy(ST* pst)//销毁
    26. {
    27. 	assert(pst);
    28. 	free(pst->a);
    29. 	pst->a = NULL;
    30. 	pst->capacity = 0;
    31. 	pst->top = 0;
    32. }
    33. void STPush(ST* pst, STDatatype x)//入栈；
    34. {
    35. 	assert(pst);
    36. 	if (pst->top == pst->capacity)
    37. 	{
    38. 		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
    39. 		STDatatype* tmp =(STDatatype *) realloc(pst->a, sizeof(STDatatype) * newcapacity);
    40. 		if (tmp == NULL)
    41. 		{
    42. 			perror("realloc");
    43. 			return;
    44. 		}
    45. 		pst->a = tmp;
    46. 		pst->capacity = newcapacity;
    47. 	}
    48. 	pst->a[pst->top] = x;
    49. 	pst->top++;
    50.  
    51. }
    52. void STPop(ST* pst)//出栈；
    53. {
    54. 	assert(pst);
    55. 	assert(pst->top>0);
    56. 	pst->top--;
    57. }
    58. STDatatype STTop(ST* pst)
    59. {
    60. 	assert(pst);
    61. 	return pst->a[pst->top-1];
    62. }
    63. bool STEmpty(ST* pst)//判断是否为空
    64. {
    65. 	assert(pst);
    66. 	return pst->top == 0;
    67. }
    68. 以下为测试代码
    69. void test1()
    70. {
    71. 	ST s;
    72. 	STInit(&s);
    73. 	STPush(&s, 1);
    74. 	STPush(&s, 2);
    75. 	STPush(&s, 3);
    76. 	STPush(&s, 4);
    77. 	STPush(&s, 5);
    78. 	while (!STEmpty(&s))
    79. 	{
    80. 		printf("%d ", STTop(&s));
    81. 		STPop(&s);
    82. 	}
    83. 	STDestroy(&s);
    84. }
    85. int main()
    86. {
    87. 	test1();
    88. 	return 0;
    89. }

    3.2队列的实现源码

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<assert.h>
    4. #include<stdbool.h>
    5. typedef int QDatatype;
    6. typedef struct QueueNode
    7. {
    8. 	QDatatype data;
    9. 	struct QueueNode* next;
    10.  
    11. }QNode;
    12. typedef struct Queue
    13. {
    14. 	QNode* phead;
    15. 	QNode* ptail;
    16. 	int Queuesize;
    17.  
    18. }Queue;
    19. void QueueInit(Queue* pq);//初始化；
    20. void QueueDestroy(Queue* pq);//销毁
    21. void QueuePush(Queue* pq, QDatatype x);//进队
    22. void QueuePop(Queue* pq);//出队
    23. QDatatype QueueFront(Queue* pq);//返回队首元素;
    24. QDatatype QueueBack(Queue* pq);//队尾元素
    25. bool QueueEmpty(Queue* pq);//判断是否空
    26. int QueueSize(Queue* pq);//队里面个数
    27. void QueueInit(Queue* pq)//初始化；
    28. {
    29. 	assert(pq);
    30. 	pq->phead = NULL;
    31. 	pq->ptail = NULL;
    32. 	pq->Queuesize = 0;
    33. }
    34. void QueueDestroy(Queue* pq)//销毁
    35. {
    36. 	assert(pq);
    37. 	QNode* cur = pq->phead;
    38. 	while (cur)
    39. 	{
    40. 		QNode* Next = cur->next;
    41. 		free(cur);
    42. 		cur = Next;
    43. 	}
    44. 	pq->phead = NULL;
    45. 	pq->ptail = NULL;
    46. 	pq->Queuesize = 0;
    47. }
    48. void QueuePush(Queue* pq, QDatatype x)//进队
    49. {
    50. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    51. 	if (newnode == NULL)
    52. 	{
    53. 		perror("malloc");
    54. 		return;
    55. 	}
    56. 	newnode->data = x;
    57. 	newnode->next = NULL;
    58. 	if (pq->ptail == NULL)
    59. 	{
    60. 		pq->ptail = pq->phead = newnode;
    61. 	}
    62. 	else
    63. 	{
    64. 		pq->ptail->next=newnode;
    65. 		pq->ptail = newnode;
    66. 	}
    67. 	pq->Queuesize++;
    68. }
    69. void QueuePop(Queue* pq)//出队
    70. {
    71. 	assert(pq);
    72. 	assert(pq->phead);
    73. 	QNode* cur = pq->phead;
    74. 	if (cur->next == NULL)
    75. 	{
    76. 		free(cur);
    77. 		cur = NULL;
    78. 		pq->phead = pq->ptail = NULL;
    79.  
    80. 	}
    81. 	else
    82. 	{
    83. 		pq->phead = pq->phead->next;
    84. 		free(cur);
    85. 		cur = NULL;
    86. 	}
    87. 	pq->Queuesize--;
    88. }
    89. QDatatype QueueFront(Queue* pq)//返回队首元素;
    90. {
    91. 	assert(pq);
    92. 	assert(pq->phead);
    93. 	return pq->phead->data;
    94.  
    95. }
    96. QDatatype QueueBack(Queue* pq)//队尾元素
    97. {
    98. 	assert(pq);
    99. 	assert(pq->ptail);
    100. 	return pq->ptail->data;
    101. }
    102. bool QueueEmpty(Queue* pq)//判断是否空
    103. {
    104. 	assert(pq);
    105. 	return pq->phead == NULL;
    106. }
    107. int QueueSize(Queue* pq)//队里面个数
    108. {
    109. 	assert(pq);
    110. 	return pq->Queuesize;
    111. }
    112. //以下为测试代码
    113. void test1()
    114. {
    115. 	Queue st;
    116.  
    117. 	QueueInit(&st);
    118. 	QueuePush(&st, 1);
    119. 	QueuePush(&st, 2);
    120. 	QueuePush(&st, 3);
    121. 	QueuePush(&st, 4);
    122. 	QueuePush(&st, 5);
    123. 	while (!QueueEmpty(&st))
    124. 	{
    125. 		printf("%d ", QueueFront(&st));
    126. 		QueuePop(&st);
    127. 	}
    128. 	QueueDestroy(&st);
    129.  
    130. }
    131. int main()
    132. {
    133. 	test1();
    134. 	return 0;
    135. }

     

  • 相关阅读:
    6.套餐管理业务开发
    如何在不同平台上搭建Flutter开发环境
    代码重构的一些理由
    适合Python初学者阅读的Github开源代码
    计算机网络-物理层
    【C++】简单理解模板 函数模板 类模板
    基于Springboot外卖系统07：员工分页查询+ 分页插件配置+分页代码实现
    Mysql 数据库
    python3调用阿里云openapi脚本 - 生产环境
    区块链的认识
  • 原文地址：https://blog.csdn.net/weixin_67131528/article/details/134499149