• ＜栈和队列及模拟实现＞——《Data Structure in C Train》

    目录

    详细实现链接：

    ＜栈（动态版）＞《数据结构(C语言版)》

    ＜队列（链式）＞《数据结构(C语言版)》

    1.分析实现功能、感受栈和队列的实现结构：

    1.1栈的实现结构方式：​

    1.2 队列的实现方式：

    2.完整源码：

    2.1栈的模拟实现： 

    Stack.h:

    Stack.c:

    Test.c:

    2.2 队列的模拟实现：

    Queue.h：

    Queue.c:

    Test.c:

     3.判断括号匹配程序：

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

    详细实现链接：

    ＜栈（动态版）＞《数据结构(C语言版)》

    ＜队列（链式）＞《数据结构(C语言版)》

    1.分析实现功能、感受栈和队列的实现结构：

    1.1栈的实现结构方式：

    数组实现栈的结构：

    相当于顺序表的尾插、尾删，用尾作栈顶，非常合适！从CPU预加载命中角度分析，数组实现的性能更好一些！

    缺点：空间不够时需要增容。

    单向链表实现栈的结构：

    用头结点作栈底，这样使得入栈和出栈效率都是O(1)。

    双向链表实现栈的结构：

    用尾作栈顶。

    1.2 队列的实现方式：

    数组实现队列的结构：

    不适合，队头出数据需要挪动数据

    单链表实现队列的结构：

    无需使用带头结点的单链表即可完成，带头结点是为了减少二级指针的使用。

    tail是移动的，方便尾部操作直接找到。head方便头部操作直接找到。

     

    数据结构的设计比较灵活，正所谓：“树挪死，人挪活”。在学习中，不要一味地“守死”，而要学会“变活。”

    2.完整源码：

    2.1栈的模拟实现： 

    Stack.h:

    1. #pragma once
    2.  
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. typedef char STDataType;
    9.  
    10. typedef struct Stack
    11. {
    12. 	STDataType* a;   //通过数组实现栈的结构
    13. 	int top;
    14. 	int capacity;
    15. }ST;
    16. //初始化
    17. void StackInit(ST* ps);
    18. //释放内存、销毁空间
    19. void StackDestory(ST* ps);
    20. // 入栈
    21. void StackPush(ST* ps, STDataType x);
    22. // 出栈
    23. void StackPop(ST* ps);
    24. //取栈顶数据
    25. STDataType StackTop(ST* ps);
    26. //栈的大小
    27. int StackSize(ST* ps);
    28. //判空
    29. bool StackEmpty(ST* ps);

    Stack.c:

    1. #include"Stack.h"
    2. //初始化
    3. void StackInit(ST* ps)
    4. {
    5. 	assert(ps);
    6.  
    7. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    8. 	if (ps->a == NULL)
    9. 	{
    10. 		printf("malloc fail!\n");
    11. 		exit(-1);
    12. 	}
    13.  
    14. 	ps->capacity = 4;
    15. 	ps->top = 0; //这使得top最终指向的是栈顶的后一个位置。若top=-1,则最终指向的是栈顶。
    16. }
    17. //释放内存、销毁空间
    18. void StackDestory(ST* ps)
    19. {
    20. 	assert(ps);
    21. 	free(ps->a);
    22. 	ps->a = NULL;
    23. 	ps->top = ps->capacity = 0;
    24. }
    25. // 入栈
    26. void StackPush(ST* ps, STDataType x)
    27. {
    28. 	assert(ps);
    29.  
    30. 	// 满了->增容
    31. 	if (ps->top == ps->capacity)
    32. 	{
    33. 		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
    34. 		if (tmp == NULL)
    35. 		{
    36. 			printf("realloc fail!\n");
    37. 			exit(-1);
    38. 		}
    39. 		else
    40. 		{
    41. 			ps->a = tmp;
    42. 			ps->capacity *= 2;
    43. 		}
    44. 	}
    45.  
    46. 	ps->a[ps->top] = x;
    47. 	ps->top++;
    48. }
    49.  
    50. // 出栈
    51. void StackPop(ST* ps)
    52. {
    53. 	assert(ps);
    54. 	// 栈空了，再调用Pop，就会直接中止程序报错
    55. 	assert(ps->top > 0);
    56.  
    57. 	//ps->a[ps->top - 1] = 0; //置为0只考虑了int型等，若为char、double等就不适用了。
    58. 	ps->top--;
    59. }
    60. //取栈顶数据
    61. STDataType StackTop(ST* ps)
    62. {
    63. 	assert(ps);
    64. 	// 栈空了，再调用Top，就会直接中止程序报错
    65. 	assert(ps->top > 0);
    66.  
    67. 	return ps->a[ps->top - 1];
    68. }
    69. //求栈大小
    70. int StackSize(ST* ps)
    71. {
    72. 	assert(ps);
    73.  
    74. 	return ps->top;
    75. }
    76. //判空
    77. bool StackEmpty(ST* ps)
    78. {
    79. 	assert(ps);
    80. 	return ps->top == 0;
    81. }
    82.  
    83. //判断括号是否匹配算法
    84. bool isValid(char* s) {
    85. 	ST st;
    86. 	StackInit(&st);
    87. 	while (*s != '\0')
    88. 	{
    89. 		switch (*s)
    90. 		{
    91. 		case '{':
    92. 		case '[':
    93. 		case '(':
    94. 		{
    95. 			StackPush(&st, *s);
    96. 			++s;
    97. 			break;
    98. 		}
    99. 		case '}':
    100. 		case ']':
    101. 		case ')':
    102. 		{
    103. 			if (StackEmpty(&st))
    104. 			{
    105. 				StackDestory(&st);
    106. 				return false;
    107. 			}
    108.  
    109. 			char top = StackTop(&st);
    110. 			StackPop(&st);
    111.  
    112. 			// 不匹配
    113. 			if ((*s == '}' && top != '{')
    114. 				|| (*s == ']' && top != '[')
    115. 				|| (*s == ')' && top != '('))
    116. 			{
    117. 				StackDestory(&st);
    118. 				return false;
    119. 			}
    120. 			else // 匹配
    121. 			{
    122. 				++s;
    123. 			}
    124. 			break;
    125. 		}
    126. 		default:
    127. 			break;
    128. 		}
    129. 	}
    130. 	bool ret = StackEmpty(&st);
    131. 	StackDestory(&st);
    132. 	return ret;
    133. }

    Test.c:

    1. #include"Stack.h"
    2.  
    3. int main()
    4. {
    5. 	ST st;
    6. 	StackInit(&st);
    7. 	StackPush(&st, 9);
    8. 	StackPush(&st, 5);
    9. 	StackPush(&st, 2);
    10. 	StackPush(&st, 7);
    11.  
    12. 	printf("%d \n", StackEmpty(&st));
    13. 	printf("%d \n", StackSize(&st));
    14. 	while (!StackEmpty(&st))
    15. 	{
    16. 	
    17. 		printf("%d ", StackTop(&st));
    18. 		StackPop(&st);
    19. 	}
    20. 	printf("\n");
    21. 	
    22. 	StackDestory(&st);
    23. 	return 0;
    24. }

    2.2 队列的模拟实现：

    Queue.h：

    1. #pragma once
    2.  
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7.  
    8. typedef int QDataType;
    9.  
    10. typedef struct QueueNode
    11. {
    12. 	struct QueueNode* next;
    13. 	QDataType data;
    14. }QNode;
    15.  
    16. typedef struct Queue
    17. {
    18. 	QNode* head;
    19. 	QNode* tail;
    20. }Queue;
    21. //初始化
    22. void QueueInit(Queue* pq);
    23. //销毁
    24. void QueueDestory(Queue* pq);
    25. // 队尾入
    26. void QueuePush(Queue* pq, QDataType x);
    27. // 队头出
    28. void QueuePop(Queue* pq);
    29. //取队列头元素
    30. QDataType QueueFront(Queue* pq);
    31. //取队列尾元素
    32. QDataType QueueBack(Queue* pq);
    33. //队列大小
    34. int QueueSize(Queue* pq);
    35. //队列判空
    36. bool QueueEmpty(Queue* pq);

    Queue.c:

    1. #include"Queue.h"
    2.  
    3. //初始化
    4. void QueueInit(Queue* pq)
    5. {
    6. 	assert(pq);
    7. 	pq->head = pq->tail = NULL;
    8. }
    9. //销毁
    10. void QueueDestory(Queue* pq)
    11. {
    12. 	assert(pq);
    13.  
    14. 	QNode* cur = pq->head;
    15. 	while (cur)
    16. 	{
    17. 		QNode* next = cur->next;
    18. 		free(cur);
    19. 		cur = next;
    20. 	}
    21.  
    22. 	pq->head = pq->tail = NULL;
    23. }
    24. // 队尾入
    25. void QueuePush(Queue* pq, QDataType x)
    26. {
    27. 	assert(pq);
    28. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    29. 	if (newnode == NULL)
    30. 	{
    31. 		printf("malloc fail!\n");
    32. 		exit(-1);
    33. 	}
    34.  
    35. 	newnode->data = x;
    36. 	newnode->next = NULL;
    37.  
    38. 	if (pq->tail == NULL)
    39. 	{
    40. 		pq->head = pq->tail = newnode;
    41. 	}
    42. 	else
    43. 	{
    44. 		pq->tail->next = newnode;
    45. 		pq->tail = newnode;
    46. 	}
    47. }
    48. // 队头出
    49. void QueuePop(Queue* pq)
    50. {
    51. 	assert(pq);
    52. 	assert(pq->head);
    53.  
    54. 	// 1、一个
    55. 	// 2、多个
    56. 	if (pq->head->next == NULL)
    57. 	{
    58. 		free(pq->head);
    59. 		pq->head = pq->tail = NULL;
    60. 	}
    61. 	else
    62. 	{
    63. 		QNode* next = pq->head->next;
    64. 		free(pq->head);
    65. 		pq->head = next;
    66. 	}
    67. }
    68. //取队头元素
    69. QDataType QueueFront(Queue* pq)
    70. {
    71. 	assert(pq);
    72. 	assert(pq->head);
    73.  
    74. 	return pq->head->data;
    75. }
    76. //取队尾元素
    77. QDataType QueueBack(Queue* pq)
    78. {
    79. 	assert(pq);
    80. 	assert(pq->head);
    81.  
    82. 	return pq->tail->data;
    83. }
    84. //队列大小
    85. int QueueSize(Queue* pq)
    86. {
    87. 	assert(pq);
    88. 	int size = 0;
    89. 	QNode* cur = pq->head;
    90. 	while (cur)
    91. 	{
    92. 		++size;
    93. 		cur = cur->next;
    94. 	}
    95.  
    96. 	return size;
    97. }
    98. //队列判空
    99. bool QueueEmpty(Queue* pq)
    100. {
    101. 	assert(pq);
    102. 	return pq->head == NULL;
    103. }

    Test.c:

    1. #include"Queue.h"
    2.  
    3. void TestQueue()
    4. {
    5. 	Queue q;
    6. 	QueueInit(&q);
    7. 	QueuePush(&q, 1);
    8. 	QueuePush(&q, 2);
    9. 	printf("%d ", QueueFront(&q));
    10. 	QueuePop(&q);
    11. 	printf("%d ", QueueFront(&q));
    12. 	QueuePop(&q);
    13.  
    14. 	QueuePush(&q, 3);
    15. 	QueuePush(&q, 4);
    16.  
    17. 	while (!QueueEmpty(&q))
    18. 	{
    19. 		printf("%d ", QueueFront(&q));
    20. 		QueuePop(&q);
    21. 	}
    22. 	printf("\n");
    23.  
    24. 	QueueDestory(&q);
    25. }
    26.  
    27. int main()
    28. {
    29. 	
    30. 	TestQueue();
    31.  
    32. 	return 0;
    33. }

     3.判断括号匹配程序：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. ///
    7. //声明
    8. typedef char STDataType;
    9.  
    10. typedef struct Stack
    11. {
    12. 	STDataType* a;
    13. 	int top;
    14. 	int capacity;
    15. }ST;
    16.  
    17. //
    18. //定义
    19. //初始化
    20. void StackInit(ST* ps)
    21. {
    22. 	assert(ps);
    23.  
    24. 	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    25. 	if (ps->a == NULL)
    26. 	{
    27. 		printf("malloc fail\n");
    28. 		exit(-1);
    29. 	}
    30.  
    31. 	ps->capacity = 4;
    32. 	ps->top = 0;
    33. }
    34. //销毁
    35. void StackDestory(ST* ps)
    36. {
    37. 	assert(ps);
    38. 	free(ps->a);
    39. 	ps->a = NULL;
    40. 	ps->top = ps->capacity = 0;
    41. }
    42.  
    43. // 入栈
    44. void StackPush(ST* ps, STDataType x)
    45. {
    46. 	assert(ps);
    47.  
    48. 	// 满了-》增容
    49. 	if (ps->top == ps->capacity)
    50. 	{
    51. 		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
    52. 		if (tmp == NULL)
    53. 		{
    54. 			printf("realloc fail\n");
    55. 			exit(-1);
    56. 		}
    57. 		else
    58. 		{
    59. 			ps->a = tmp;
    60. 			ps->capacity *= 2;
    61. 		}
    62. 	}
    63.  
    64. 	ps->a[ps->top] = x;
    65. 	ps->top++;
    66. }
    67.  
    68. // 出栈
    69. void StackPop(ST* ps)
    70. {
    71. 	assert(ps);
    72. 	// 栈空了，调用Pop，直接中止程序报错
    73. 	assert(ps->top > 0);
    74.  
    75. 	//ps->a[ps->top - 1] = 0;
    76. 	ps->top--;
    77. }
    78. //去栈顶元素
    79. STDataType StackTop(ST* ps)
    80. {
    81. 	assert(ps);
    82. 	// 栈空了，调用Top，直接中止程序报错
    83. 	assert(ps->top > 0);
    84.  
    85. 	return ps->a[ps->top - 1];
    86. }
    87. //求栈的的大小
    88. int StackSize(ST* ps)
    89. {
    90. 	assert(ps);
    91.  
    92. 	return ps->top;
    93. }
    94. //判空
    95. bool StackEmpty(ST* ps)
    96. {
    97. 	assert(ps);
    98.  
    99. 	return ps->top == 0;
    100. }
    101. //判断括号是否匹配
    102. bool isValid(char* s) {
    103. 	ST st;
    104. 	StackInit(&st);
    105. 	while (*s != '\0')
    106. 	{
    107. 		switch (*s)
    108. 		{
    109. 		case '{':
    110. 		case '[':
    111. 		case '(':
    112. 		{
    113. 			StackPush(&st, *s);
    114. 			++s;
    115. 			break;
    116. 		}
    117. 		case '}':
    118. 		case ']':
    119. 		case ')':
    120. 		{
    121. 			if (StackEmpty(&st))
    122. 			{
    123. 				StackDestory(&st);
    124. 				return false;
    125. 			}
    126.  
    127. 			char top = StackTop(&st);
    128. 			StackPop(&st);
    129.  
    130. 			// 不匹配
    131. 			if ((*s == '}' && top != '{')
    132. 				|| (*s == ']' && top != '[')
    133. 				|| (*s == ')' && top != '('))
    134. 			{
    135. 				StackDestory(&st);
    136. 				return false;
    137. 			}
    138. 			else // 匹配
    139. 			{
    140. 				++s;
    141. 			}
    142. 			break;
    143. 		}
    144. 		default:
    145. 			break;
    146. 		}
    147. 	}
    148.  
    149. 	bool ret = StackEmpty(&st);
    150. 	StackDestory(&st);
    151. 	return ret;
    152. }
    153.  
    154. int main()
    155. {
    156. 	//int ret = isValid("[[[");
    157. 	//int ret = isValid("[][");
    158. 	int ret = isValid("[]");
    159. 	if (ret == 0)
    160. 	{
    161. 		printf("不匹配！\n" );
    162. 	}
    163. 	else
    164. 	{
    165. 		printf("匹配！\n");
    166. 	}
    167. 	return 0;
    168. }

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

  • 相关阅读:
    图的初识·遍历
    [shell] 判断字符串是否包含子字符串方法（[[ 、=~、##、%%）
    InfluxDB 1.8 性能测试
    NFT-数字藏品之库里为何花116万买一个NFT头像？回顾NFT头像的“发迹史”或许能找到答案
    【c/c++】cpp对c的函数增强
    Vulhub靶场-KIOPTRIX: LEVEL 1.1
    Qt编写物联网管理平台50-超强跨平台
    linux自动更新oray ddns
    小程序 自定义弹框 阻止后面页面滚动
    【Springboot】Vue3-Springboot引入JWT实现登录校验以及常见的错误解决方案
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126595683