• 数据结构·栈与队列介绍与实现

    目录

    栈的概念及结构

    概念选择题 

    栈的实现

    Stack.h

    Stack.c

    Test.c

    一道关于栈的oj题目

     20. 有效的括号

    描述

    解答代码

    队列的概念及结构

    队列的实现 

    Queue.h

    Queue.c

    Test.c

    结束语

    栈的概念及结构

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
            进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
            栈中的数据元素遵守后进先出LIFO （ Last In First Out ）的原则。
    压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。
    出栈：栈的删除操作叫做出栈。 出数据也在栈顶 。

     

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

    概念选择题 

    答案 -- 选中查看

    1、B

    2、C

    栈的实现

    Stack.h

    1. #pragma once
    2.  
    3. #include
    4.  
    5. #include
    6. #include
    7. #include
    8.  
    9. //静态不考虑
    10. //#define N 100
    11. //typedef int STDataType;
    12. //struct Stack
    13. //{
    14. //	STDataType a[N];
    15. //	int top;
    16. //};
    17.  
    18.  
    19. typedef int STDataType;
    20. typedef struct Stack
    21. {
    22. 	STDataType* a;
    23. 	int top;		//数据
    24. 	int capacity;	//空间容量
    25. }ST;
    26.  
    27. //初始化
    28. void StackInit(ST* ps);
    29.  
    30. //销毁
    31. void StackDestroy(ST* ps);
    32.  
    33. //入栈
    34. void StackPush(ST* ps , STDataType x);	//根据栈的概念 栈只有一个地方可以插入
    35.  
    36. //出栈
    37. void StackPop(ST* ps);
    38.  
    39. //访问Top位置
    40. STDataType StackTop(ST* ps);
    41.  
    42. //检查是否为空
    43. bool StackEmpty(ST* ps);
    44.  
    45. //查看数据数量
    46. int StackSize(ST* ps);	//调用函数来实现 -- 数据结构建议不要直接访问结构数据，一定要通过函数接口访问
    47. 						//解耦 -- 高内聚，低耦合

    Stack.c

    1. #include "Stack.h"
    2.  
    3. //初始化
    4. void StackInit(ST* ps)
    5. {
    6. 	assert(ps);
    7. 	ps->a = NULL;
    8. 	ps->capacity = ps->top = 0;
    9. }
    10.  
    11. //销毁
    12. void StackDestroy(ST* ps)
    13. {
    14. 	assert(ps);
    15.  
    16. 	free(ps->a);
    17. 	ps->a = NULL;
    18. 	ps->capacity = ps->top = 0;
    19. }
    20.  
    21. //入栈
    22. void StackPush(ST* ps, STDataType x)
    23. {
    24. 	assert(ps);
    25. 	//扩容
    26. 	if (ps->top == ps->capacity)	//根据初始化的内容来判断
    27. 	{
    28. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    29. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
    30. 		if (tmp == NULL)
    31. 		{
    32. 			perror("realloc fail");
    33. 			exit(-1);
    34. 		}
    35. 		ps->a = tmp;
    36. 		ps->capacity = newCapacity;
    37. 	}
    38.  
    39.  
    40. 	ps->a[ps->top] = x;
    41. 	ps->top++;
    42.  
    43. }
    44.  
    45. //出栈
    46. void StackPop(ST* ps)
    47. {
    48. 	assert(ps);
    49. 	assert(!StackEmpty(ps));
    50.  
    51. 	--ps->top;
    52. }
    53.  
    54. //访问Top位置
    55. STDataType StackTop(ST* ps)
    56. {
    57. 	assert(ps);
    58. 	assert(!StackEmpty(ps));
    59.  
    60. 	return ps->a[ps->top - 1];
    61. }
    62.  
    63. //检查是否为空
    64. bool StackEmpty(ST* ps)
    65. {
    66. 	assert(ps);
    67.  
    68. 	return ps->top == 0;
    69. }
    70.  
    71. //查看数据数量
    72. int StackSize(ST* ps)
    73. {
    74. 	assert(ps);
    75.  
    76. 	return ps->top; //这里的top刚好是数据的下一个位置，自然就是数据个数
    77. }
    栈与队列的基本操作与实现
    rar 0星 超过10%的资源 1KB
    下载

    Test.c

    1. #include "Stack.h"
    2.  
    3.  
    4. void TestStack()
    5. {
    6. 	ST st;
    7. 	StackInit(&st);
    8. 	StackPush(&st, 1);
    9. 	StackPush(&st, 2);
    10. 	StackPush(&st, 3);
    11. 	printf("%d ", StackTop(&st));
    12. 	StackPop(&st);
    13. 	printf("%d ", StackTop(&st));	
    14. 	StackPop(&st);
    15.  
    16.  
    17. 	StackPush(&st, 4);
    18. 	StackPush(&st, 5);
    19. 	
    20. 	while (!StackEmpty(&st))
    21. 	{
    22. 		printf("%d ", StackTop(&st));	//访问栈顶数据
    23. 		StackPop(&st);	//根据栈的性质，访问一个弹出一个
    24. 	}
    25. 	printf("\n");
    26. }
    27.  
    28.  
    29. int main()
    30. {
    31. 	TestStack();
    32.  
    33. 	return 0;
    34. }

    一道关于栈的oj题目

     20. 有效的括号

    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/valid-parentheses

    示例 1：

    输入：s = "( )"
    输出：true
    示例 2：

    输入：s = "( )[ ]{ }"
    输出：true
    示例 3：

    输入：s = "( ]"
    输出：false
    示例 4：

    输入：s = "( [ ) ]"
    输出：false
    示例 5：

    输入：s = "{ [ ] }"
    输出：true

    提示：

    • 1 <= s.length <= 104
    • s 仅由括号 '()[]{}' 组成

    描述

    C没有栈的，要用C解决只可以自己写个栈解决

    解答代码

    1. #include
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int STDataType;
    7. typedef struct Stack
    8. {
    9. 	STDataType* a;
    10. 	int top;		//数据
    11. 	int capacity;	//空间容量
    12. }ST;
    13.  
    14. //初始化
    15. void StackInit(ST* ps);
    16.  
    17. //销毁
    18. void StackDestroy(ST* ps);
    19.  
    20. //入栈
    21. void StackPush(ST* ps , STDataType x);	//根据栈的概念 栈只有一个地方可以插入
    22.  
    23. //出栈
    24. void StackPop(ST* ps);
    25.  
    26. //访问Top位置
    27. STDataType StackTop(ST* ps);
    28.  
    29. //检查是否为空
    30. bool StackEmpty(ST* ps);
    31.  
    32. //查看数据数量
    33. int StackSize(ST* ps);	//调用函数来实现 -- 数据结构建议不要直接访问结构数据，一定要通过函数接口访问
    34. 						//解耦 -- 高内聚，低耦合
    35.  
    36.  
    37. //初始化
    38. void StackInit(ST* ps)
    39. {
    40. 	assert(ps);
    41. 	ps->a = NULL;
    42. 	ps->capacity = ps->top = 0;
    43. }
    44.  
    45. //销毁
    46. void StackDestroy(ST* ps)
    47. {
    48. 	assert(ps);
    49.  
    50. 	free(ps->a);
    51. 	ps->a = NULL;
    52. 	ps->capacity = ps->top = 0;
    53. }
    54.  
    55. //入栈
    56. void StackPush(ST* ps, STDataType x)
    57. {
    58. 	assert(ps);
    59. 	//扩容
    60. 	if (ps->top == ps->capacity)	//根据初始化的内容来判断
    61. 	{
    62. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    63. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
    64. 		if (tmp == NULL)
    65. 		{
    66. 			perror("realloc fail");
    67. 			exit(-1);
    68. 		}
    69. 		ps->a = tmp;
    70. 		ps->capacity = newCapacity;
    71. 	}
    72.  
    73.  
    74. 	ps->a[ps->top] = x;
    75. 	ps->top++;
    76.  
    77. }
    78.  
    79. //出栈
    80. void StackPop(ST* ps)
    81. {
    82. 	assert(ps);
    83. 	assert(!StackEmpty(ps));
    84.  
    85. 	--ps->top;
    86. }
    87.  
    88. //访问Top位置
    89. STDataType StackTop(ST* ps)
    90. {
    91. 	assert(ps);
    92. 	assert(!StackEmpty(ps));
    93.  
    94. 	return ps->a[ps->top - 1];
    95. }
    96.  
    97. //检查是否为空
    98. bool StackEmpty(ST* ps)
    99. {
    100. 	assert(ps);
    101. 	return ps->top == 0;
    102. }
    103.  
    104. //查看数据数量
    105. int StackSize(ST* ps)
    106. {
    107. 	assert(ps);
    108.  
    109. 	return ps->top; //这里的top刚好是数据的下一个位置，自然就是数据个数
    110. }
    111.  
    112.  
    113.  
    114. bool isValid(char * s){
    115.  
    116.  
    117.     ST st;
    118.     StackInit(&st);
    119.     while(*s)
    120.     {
    121.         if(*s == '{' || *s == '[' || *s == '(')
    122.         {
    123.             StackPush(&st, *s);
    124.         }
    125.         else
    126.         {
    127.             if(StackEmpty(&st)) //如果栈为空就说明一定不匹配 -- 数量不匹配
    128.             {
    129.                 StackDestroy(&st);  //销毁空间
    130.                 return false;
    131.             }
    132.  
    133.             char top = StackTop(&st);//保存Top 数据 再弹出来
    134.             StackPop(&st);  //记得弹出来Top
    135.             if((*s == '}' && top != '{')
    136.             || (*s == ']' && top != '[')
    137.             || (*s == ')' && top != '('))
    138.             {
    139.                 StackDestroy(&st);  //销毁空间
    140.                 return false;
    141.             }   
    142.         }
    143.  
    144.         ++s;
    145.     }
    146.     //栈不为空 -- 但是数量还是不匹配，只有左括号 -- 这也是不匹配
    147.     bool flag = StackEmpty(&st);
    148.     StackDestroy(&st);  //销毁空间
    149.  
    150.     return flag;
    151. }

    把上面写的栈搬了过来

    队列的概念及结构

    汇编语言数据结构
    pdf 5星 超过95%的资源 1.28MB
    下载
    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 先进先出 FIFO(First In First Out)
    入队列：进行插入操作的一端称为 队尾
    出队列：进行删除操作的一端称为 队头

     

    队列一般体现公平性 -- 比如在银行中的排队，先排队先办理，即先进先出，出于这点，使用链表更适合实现

    队列的实现 

    Queue.h

    1. #pragma once
    2.  
    3. #include
    4. #include
    5. #include
    6. #include
    7.  
    8. //能用单链表解决问题就可以用单链表 -- 没必要使用双向循环链表，这属于有点小题大做了
    9.  
    10. typedef int QDataType;
    11. typedef struct QueueNode
    12. {
    13. 	struct QueueNode* next;
    14. 	QDataType data;
    15. }QNode;
    16.  
    17. //再定义一个节点来存放两个指针，方便后面操作
    18. typedef struct Queue
    19. {
    20. 	//尾指针
    21. 	QNode* tail;
    22. 	//头指针
    23. 	QNode* head;
    24. 	int size;
    25. }Queue;
    26.  
    27. //初始化  -- 到现在有三种不用二级指针来初始化结构体了 返回值、哨兵位的头节点和这里的创立一个新的结构体放俩这种
    28. void QueueInit(Queue* pq);
    29.  
    30. //销毁
    31. void QueueDestroy(Queue* pq);
    32.  
    33. //入队列 -- 根据队列的性质 只尾插
    34. void QueuePush(Queue* pq,QDataType x);
    35.  
    36. //出队列 -- 根据队列的性质 只头删
    37. void QueuePop(Queue* pq);
    38.  
    39. //查看头
    40. QDataType QueueFront(Queue* pq);
    41.  
    42. //查看尾
    43. QDataType QueueBack(Queue* pq);
    44.  
    45. //判断是否为空
    46. bool QueueEmpty(Queue* pq);
    47.  
    48. //查看节点长度
    49. int QueueSize(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. 	pq->size = 0;
    9. }
    10.  
    11. //销毁
    12. void QueueDestroy(Queue* pq)
    13. {
    14. 	assert(pq);
    15. 	QNode* cur = pq->head;
    16. 	while (cur)
    17. 	{
    18. 		QNode* del = cur;
    19. 		cur = cur->next;
    20. 		free(del);
    21. 	}
    22.  
    23. 	pq->head = pq->tail = NULL;	//要改变什么就需要什么的指针，这里置空就可以了
    24. }
    25.  
    26. //入队列 -- 根据队列的性质 只尾插
    27. void QueuePush(Queue* pq, QDataType x)
    28. {
    29. 	assert(pq);
    30. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    31. 	if (newnode == NULL)
    32. 	{
    33. 		perror("malloc fail");
    34. 		exit(-1);
    35. 	}
    36. 	else
    37. 	{
    38. 		newnode->data = x;
    39. 		newnode->next = NULL;	//这里置空，下面就不需要置空了
    40. 	}
    41.  
    42. 	if (pq->tail == NULL)
    43. 	{
    44. 		pq->head = pq->tail = newnode;
    45. 	}
    46. 	else
    47. 	{
    48. 		pq->tail->next = newnode;
    49. 		pq->tail = newnode;
    50. 	}
    51.  
    52. 	pq->size++;
    53. }
    54.  
    55. //出队列 -- 根据队列的性质 只头删
    56. void QueuePop(Queue* pq)
    57. {
    58. 	assert(pq);
    59. 	assert(!QueueEmpty(pq));
    60.  
    61. 	if (pq->head->next == NULL)	//防止只剩下一个节点时候再删，就会导致野指针
    62. 	{
    63. 		free(pq->head);
    64. 		pq->tail = pq->head = NULL;
    65. 	}
    66. 	else
    67. 	{
    68. 		QNode* del = pq->head;
    69. 		pq->head = pq->head->next;
    70.  
    71. 		free(del);
    72. 		del = NULL;
    73. 	}
    74.  
    75. 	pq->size--;
    76. }
    77.  
    78. //查看头
    79. QDataType QueueFront(Queue* pq)
    80. {
    81. 	assert(pq);
    82. 	assert(!QueueEmpty(pq));
    83.  
    84. 	return pq->head->data;
    85. }
    86.  
    87. //查看尾
    88. QDataType QueueBack(Queue* pq)
    89. {
    90. 	assert(pq);
    91. 	assert(!QueueEmpty(pq));
    92.  
    93. 	return pq->tail->data;
    94. }
    95.  
    96. //判断是否为空
    97. bool QueueEmpty(Queue* pq)
    98. {
    99. 	assert(pq);
    100.  
    101. 	return pq->head == NULL && pq->tail == NULL; //理论上两个都应该为空才为空，一般一个为空就都会为空，不是就出问题了
    102. }
    103.  
    104. //查看节点长度
    105. int QueueSize(Queue* pq)
    106. {
    107. 	assert(pq);
    108.  
    109. 	//这样写就变为O(N)级别了 为此需要稍作修改
    110. 	//QNode* cur = pq->head;
    111. 	//int n = 0;
    112. 	//while (cur)
    113. 	//{
    114. 	//	++n;
    115. 	//	cur = cur->next;
    116. 	//}
    117.  
    118. 	//return n;
    119.  
    120. 	return pq->size;
    121. }

    Test.c

    1. #include "Queue.h"
    2.  
    3. void TestQueue()
    4. {
    5. 	Queue q; //这里创立了一个节点，使用不会为空
    6. 	//初始化
    7. 	QueueInit(&q);
    8. 	QueuePush(&q, 1);
    9. 	QueuePush(&q, 2);
    10.  
    11. 	printf("%d ", QueueFront(&q));
    12. 	QueuePop(&q);
    13. 	//打印尾部
    14. 	printf("%d ", QueueFront(&q));
    15.  
    16. 	QueuePush(&q, 3);
    17. 	QueuePush(&q, 4);
    18.  
    19. 	
    20. 	while (!QueueEmpty(&q))
    21. 	{
    22. 		printf("%d ", QueueFront(&q));
    23. 		QueuePop(&q);
    24. 	}
    25.  
    26. 	printf("\nsize =%d \n",QueueSize(&q));
    27.  
    28. 	QueueDestroy(&q);
    29. }
    30.  
    31.  
    32. int main()
    33. {
    34.  
    35. 	TestQueue();
    36.  
    37. 	return 0;
    38. }

    结束语

    枝上柳绵吹又少，天涯何处无芳草。
                                                            宋·苏轼 《蝶恋花·春景》 

  • 相关阅读:
    Prometheus、node_exporter、Grafana端口修改（端口占用）
    多态（polymorphic）
    PySpark的运行出错：Py4JJavaError
    提升，方法比努力重要！不懂这几点再多的努力也白费！
    茶饮门店本地生活抖音团购运营方案计划书
    ubuntu下网卡插入网线后仍然不连接
    安卓 view淡入淡出(fade in fade out) kotlin
    CiscoCUCM电话注册
    MySQL索引分类及相关概念辨析
    PyTorch模型定义和相关使用
  • 原文地址：https://blog.csdn.net/weixin_67595436/article/details/126242893