• 数据结构之栈和队列

    目录

    1.栈的概念2、栈的实现

    1、队列的概念2、队列的实现

    今天介绍的是栈和队列。

    先说栈吧。

    1.栈的概念

    栈也是线性表的一种，不过他较为特殊。他只能在一边进行数据的出入。也就是说晚进的数据先出去。进行数据进出的一端叫做栈顶，另一端叫做栈底。

    数据进入叫做压栈，数据出去叫做出栈。

     

    从图中可以看出，栈的数据进出遵循后进先出的规则。

    2、栈的实现

    栈的实现可以使用数组也可使用链表。在这里我们使用数组，因为栈的数据进出本质是尾插尾删，而用链表实现，尾插与尾删还得先找到尾，相对于数组较为复杂。所以在这里选择数组。

    栈有分为静态栈与动态增长的栈。

    静态栈

     

    在实际中相对不实用，所以在这里实现可以动态增长的栈。

    这次我们实现的接口有：栈的初始化，压栈，出栈，返回栈顶数据，返回栈中数据个数，检验栈是否为空，销毁栈。

    结构体创建：

    1. typedef int Datatype;
    2. typedef struct StackList
    3. {
    4. 	Datatype* arr;
    5. 	Datatype top;// 初始为0，表示栈顶位置下一个位置下标
    6. 	Datatype capacity;
    7. }SL;

    初始化：

    1. void initialize(SL* slnum)
    2. {
    3. 	assert(slnum);
    4.  
    5. 	slnum->capacity = 0;
    6. 	slnum->top = 0;
    7. 	slnum->arr = NULL;
    8. }

    扩容：

    1. void expand(SL* slnum)
    2. {
    3. 	assert(slnum);
    4.  
    5. 	if(slnum->capacity == slnum->top)
    6. 	{
    7. 		Datatype newcapacity = slnum->capacity = 0 ? 4 : slnum->capacity * 2;
    8. 		SL* tmp = (SL*)realloc(slnum->arr,sizeof(Datatype) * newcapacity);
    9. 		if(tmp == NULL)
    10. 		{
    11. 			perror("realloc false");
    12. 			exit(-1);
    13. 		}
    14. 		slnum->arr = tmp;
    15. 		slnum->capacity = newcapacity;
    16. 	}
    17. }

    压栈：

    1. void stackint(SL* slnum,Datatype n)
    2. {
    3. 	expand(slnum);
    4. 	slnum->arr[slnum->top] = n;
    5. 	slnum->top++;
    6. }

    出栈：

    1. void stackout(SL* slnum)
    2. {
    3. 	assert(slnum);
    4.  
    5. 	assert(slnum->top > 0);
    6. 	slnum->top--;
    7. }

    栈中元素个数：

    1. Datatype stacktop(SL* slnum)
    2. {
    3. 	assert(slnum);
    4. 	assert(!stackempty);
    5. 	return slnum->top-1;
    6. }

    获取栈顶：

    1. Datatype get_stacktop(SL* slnum)
    2. {
    3. 	assert(slnum);
    4.  
    5. 	assert(!stackempty);
    6.  
    7. 	return slnum->arr[slnum->top - 1];
    8. }

    检验栈是否为空：

    1. bool stackempty(SL* slnum)
    2. {
    3. 	assert(slnum);
    4.  
    5. 	if (slnum->top > 0)
    6. 	{
    7. 		return true;
    8. 	}
    9. 	else
    10. 		return false;
    11. }

    销毁栈：

    1. void destroy(SL* slnum)
    2. {
    3. 	assert(slnum);
    4.  
    5. 	slnum->capacity = 0;
    6. 	slnum->top = 0;
    7. 	free(slnum->arr);
    8. 	slnum->arr = NULL;
    9. }

    栈的介绍就到这里，下面开始介绍队列。

    1、队列的概念

    队列是在一端插入数据在另一端删除数据的线性表。队列的数据删除规则为先进先出。队列在队尾插入，在对头删除。

     2、队列的实现

    队列的实现也可以使用数组，也可以使用链表，又因为使用数组实现队列时删除数据需要挪动数据因此在这里我们使用链表来实现队列。

    因为我们在实现队列时需要在队头出队，在队尾入队。所以我们可以再次封装一个结构体变量，里面放入一个head指针，一个tail指针。

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

    接口实现：

    初始化：

    1. void QInit(struct Queue* p)
    2. {
    3. 	assert(p);
    4. 	p->head = NULL;
    5. 	p->tail = NULL;
    6.  
    7. 	p->size = 0;
    8.  
    9. }

    队尾入队列：

    1. void Queueint(Queue* p,Qdatatype n)
    2. {
    3. 	assert(p);
    4.  
    5. 	QNode* tmp = (QNode*)malloc(sizeof(QNode));
    6.  
    7. 	QNode* tmp = (QNode*)malloc(p, sizeof(QNode));
    8.  
    9. 	if(tmp == NULL)
    10. 	{
    11. 		perror("malloc fail");
    12. 		exit(-1);
    13. 	}
    14. 	tmp->n = n;
    15. 	tmp->next = NULL;
    16. 	p->size++;
    17. 	if( p->tail == NULL)
    18. 	{
    19. 		p->head = p->tail = tmp;
    20. 	}
    21. 	else
    22. 	{
    23. 		p->tail->next = tmp;
    24. 		p->tail = p->tail->next;
    25. 	}
    26. }

    队头出队列：

    1. void Queueout(Queue* p)
    2. {
    3. 	assert(p);
    4. 	assert(!Queueempty(p));
    5. 	if(p->head->next == NULL)
    6. 	{
    7. 		free(p->head);
    8. 		p->head = p->tail = NULL;
    9. 	}
    10. 	else
    11. 	{
    12. 		QNode* tmphead = p->head;
    13. 		p->head = p->head->next;
    14. 		free(tmphead);
    15. 	}
    16. 	
    17. 	p->size--;
    18.  
    19. }

    判断队列是否为空：

    1. bool Queueempty(Queue* p)
    2. {
    3. 	return p->head == NULL&&p->tail == NULL;
    4. }

    获取队头数据：

    1. Qdatatype Gettop(Queue* p)
    2. {
    3. 	assert(p);
    4.  
    5. 	assert(!Queueempty(p));
    6.  
    7. 	assert(!queueempty(p));
    8.  
    9. 	printf("%d ", p->head->n);
    10. }

    获取队尾数据：

    1. Qdatatype Gettail(Queue* p)
    2. {
    3. 	assert(p);
    4.  
    5. 	assert(!Queueempty(p));
    6.  
    7. 	assert(!queueempty(p));
    8.  
    9. 	printf("%d ", p->tail->n);
    10. }

    有效数据个数：

    1. Qdatatype Count(Queue* p)
    2. {
    3. 	return p->size;
    4. }

    销毁队列：

    1. void destroy(Queue* p)
    2. {
    3. 	assert(p);
    4. 	QNode* cur = p->head;
    5. 	while(cur)
    6. 	{
    7. 		QNode* next = cur->next;
    8. 		free(cur);
    9. 		cur = next;
    10. 	}
    11.  
    12. 	free(p->head);
    13. 	free(p->tail);
    14.  
    15.  
    16. }

    3、完整版代码

    栈：

    1. #pragma once
    2. #include<stdio.h>
    3. #include<stdlib.h>
    4. #include<assert.h>
    5. #include<stdbool.h>
    6. typedef int Datatype;
    7. typedef struct StackList
    8. {
    9. 	Datatype* arr;
    10. 	Datatype top;// 初始为0，表示栈顶位置下一个位置下标
    11. 	Datatype capacity;
    12. }SL;
    13.  
    14. //接口功能实现
    15. //初始化
    16. void initialize(SL* slnum);
    17. //扩容
    18. void expand(SL* slnum);
    19. //入栈
    20. void stackint(SL* slnum,Datatype n);
    21. //出栈
    22. void stackout(SL* slnum);
    23. //获取栈有效元素个数
    24. Datatype stacktop(SL* slnum);
    25. //获取栈顶元素
    26. Datatype get_stacktop(SL* slnum);
    27. //检查栈是否为空
    28. bool stackempty(SL* slnum);
    29. //销毁
    30. void destroy(SL* slnum);
    1. #pragma once
    2. #include"stacklist.h"
    3. void initialize(SL* slnum)
    4. {
    5. 	assert(slnum);
    6.  
    7. 	slnum->capacity = 0;
    8. 	slnum->top = 0;
    9. 	slnum->arr = NULL;
    10. }
    11. void expand(SL* slnum)
    12. {
    13. 	assert(slnum);
    14.  
    15. 	if(slnum->capacity == slnum->top)
    16. 	{
    17. 		Datatype newcapacity = slnum->capacity = 0 ? 4 : slnum->capacity * 2;
    18. 		SL* tmp = (SL*)realloc(slnum->arr,sizeof(Datatype) * newcapacity);
    19. 		if(tmp == NULL)
    20. 		{
    21. 			perror("realloc false");
    22. 			exit(-1);
    23. 		}
    24. 		slnum->arr = tmp;
    25. 		slnum->capacity = newcapacity;
    26. 	}
    27. }
    28. void stackint(SL* slnum,Datatype n)
    29. {
    30. 	expand(slnum);
    31. 	slnum->arr[slnum->top] = n;
    32. 	slnum->top++;
    33. }
    34. void stackout(SL* slnum)
    35. {
    36. 	assert(slnum);
    37.  
    38. 	assert(slnum->top > 0);
    39. 	slnum->top--;
    40. }
    41. Datatype stacktop(SL* slnum)
    42. {
    43. 	assert(slnum);
    44. 	assert(!stackempty);
    45. 	return slnum->top-1;
    46. }
    47. Datatype get_stacktop(SL* slnum)
    48. {
    49. 	assert(slnum);
    50.  
    51. 	assert(!stackempty);
    52.  
    53. 	return slnum->arr[slnum->top - 1];
    54. }
    55. bool stackempty(SL* slnum)
    56. {
    57. 	assert(slnum);
    58.  
    59. 	if (slnum->top > 0)
    60. 	{
    61. 		return true;
    62. 	}
    63. 	else
    64. 		return false;
    65. }
    66. void destroy(SL* slnum)
    67. {
    68. 	assert(slnum);
    69.  
    70. 	slnum->capacity = 0;
    71. 	slnum->top = 0;
    72. 	free(slnum->arr);
    73. 	slnum->arr = NULL;
    74. }

    队列：

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. typedef int Qdatatype;
    8. typedef struct QueueNode
    9. {
    10. 	Qdatatype n;
    11. 	struct QueueNode* next;
    12. }QNode;
    13. typedef struct Queue
    14. {
    15. 	QNode* head;
    16. 	QNode* tail;
    17. 	int size;
    18. }Queue;
    19.  
    20. //初始化
    21. void QInit(struct Queue* p);
    22. // 队尾入队列
    23. void Queueint(Queue* p, Qdatatype n);
    24. // 队头出队列
    25. void Queueout(Queue* p);
    26. // 获取队列头部元素
    27. Qdatatype Gettop(Queue* p);
    28. // 获取队列队尾元素
    29. Qdatatype Gettail(Queue* p);
    30. // 获取队列中有效元素个数
    31. Qdatatype Count(Queue* p);
    32. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0
    33. bool Queueempty(Queue* p);
    34. // 销毁队列
    35. void destroy(Queue* p);
    1. #include"queue.h"
    2. void QInit(struct Queue* p)
    3. {
    4. 	assert(p);
    5. 	p->head = NULL;
    6. 	p->tail = NULL;
    7. <<<<<<< HEAD
    8. 	p->size = 0;
    9. =======
    10. >>>>>>> 5b9085118240e85a5ef7699a109d637576c62395
    11. }
    12. void Queueint(Queue* p,Qdatatype n)
    13. {
    14. 	assert(p);
    15. <<<<<<< HEAD
    16. 	QNode* tmp = (QNode*)malloc(sizeof(QNode));
    17. =======
    18. 	QNode* tmp = (QNode*)malloc(p, sizeof(QNode));
    19. >>>>>>> 5b9085118240e85a5ef7699a109d637576c62395
    20. 	if(tmp == NULL)
    21. 	{
    22. 		perror("malloc fail");
    23. 		exit(-1);
    24. 	}
    25. 	tmp->n = n;
    26. 	tmp->next = NULL;
    27. 	p->size++;
    28. 	if( p->tail == NULL)
    29. 	{
    30. 		p->head = p->tail = tmp;
    31. 	}
    32. 	else
    33. 	{
    34. 		p->tail->next = tmp;
    35. 		p->tail = p->tail->next;
    36. 	}
    37. }
    38. bool Queueempty(Queue* p)
    39. {
    40. 	return p->head == NULL&&p->tail == NULL;
    41. }
    42. void Queueout(Queue* p)
    43. {
    44. 	assert(p);
    45. 	assert(!Queueempty(p));
    46. 	if(p->head->next == NULL)
    47. 	{
    48. 		free(p->head);
    49. 		p->head = p->tail = NULL;
    50. 	}
    51. 	else
    52. 	{
    53. 		QNode* tmphead = p->head;
    54. 		p->head = p->head->next;
    55. 		free(tmphead);
    56. 	}
    57. 	
    58. 	p->size--;
    59.  
    60. }
    61. Qdatatype Gettop(Queue* p)
    62. {
    63. 	assert(p);
    64. <<<<<<< HEAD
    65. 	assert(!Queueempty(p));
    66. =======
    67. 	assert(!queueempty(p));
    68. >>>>>>> 5b9085118240e85a5ef7699a109d637576c62395
    69. 	printf("%d ", p->head->n);
    70. }
    71. Qdatatype Gettail(Queue* p)
    72. {
    73. 	assert(p);
    74. <<<<<<< HEAD
    75. 	assert(!Queueempty(p));
    76. =======
    77. 	assert(!queueempty(p));
    78. >>>>>>> 5b9085118240e85a5ef7699a109d637576c62395
    79. 	printf("%d ", p->tail->n);
    80. }
    81. Qdatatype Count(Queue* p)
    82. {
    83. 	return p->size;
    84. }
    85. void destroy(Queue* p)
    86. {
    87. 	assert(p);
    88. 	QNode* cur = p->head;
    89. 	while(cur)
    90. 	{
    91. 		QNode* next = cur->next;
    92. 		free(cur);
    93. 		cur = next;
    94. 	}
    95.  
    96. 	free(p->head);
    97. 	free(p->tail);
    98.  
    99.  
    100. }

  • 相关阅读:
    亚马逊鲲鹏系统一款可以帮助AMZ商品加购系统
    Vue--整合SVG Icon图标--方法/实例
    Golang 实现对配置文件加密
    Spring之Aop底层源码剖析
    Jetpack Compose 中的状态管理
    多线程（复习）
    Docker搭建DNS服务器--nouse
    【攻防世界WEB】难度一星3分入门题：get、post、robots、、cookie、button、weak、php、web、unserialize
    synchronized与ReentrantLock的区别
    【JavaEE】Spring AOP （面向切面）详解
  • 原文地址：https://blog.csdn.net/m0_64334842/article/details/127927800