• 数据结构——栈与队列

    一、栈

    1.1   栈的概念及结构

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

    1.2 栈的实现（数组栈）

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

    1.2.1 栈的基本功能实现

    1. #include
    2. #include
    3. #include
    4. typedef int  SDateType;
    5. typedef struct Stack
    6. {
    7. 	SDateType* a;
    8. 	int top;
    9. 	int capacity;
    10.  
    11. }Stack;
    12.  
    13. //初始化栈和销毁栈
    14. void InitStack(Stack* ps);
    15. void DestoryStack(Stack* ps);
    16.  
    17. //出栈和入栈
    18. void StackPush(Stack* ps, SDateType x);
    19. void StackPop(Stack* ps);
    20.  
    21. //栈的有效个数和栈顶元素
    22. int  StackSize(Stack* ps);
    23. int   StackTop(Stack* ps);
    24.  
    25. //栈是否为空
    26. bool StackEmpty(Stack* ps);
    1.2.1.1 栈的初始化和销毁
    1. //初始化栈和销毁栈
    2. void InitStack(Stack* ps)
    3. {
    4. 	assert(ps);
    5. 	ps->a = NULL;
    6. 	ps->capacity = ps->top = 0;
    7. }
    8. void DestoryStack(Stack* ps)
    9. {
    10. 	assert(ps);
    11. 	free(ps->a);
    12. 	ps->a = NULL;
    13. 	ps->capacity = ps->top = 0;
    14.  
    15. }
    1.2.1.2  入栈和出栈
    1. //出栈和入栈
    2. void StackPush(Stack* ps, SDateType x)
    3. {
    4. 	assert(ps);
    5. 	//扩容
    6. 	if (ps->top == ps->capacity)
    7. 	{
    8. 		SDateType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    9. 		SDateType* tmp = (SDateType*)realloc(ps->a,newcapacity*sizeof(SDateType));
    10. 		if (tmp == NULL)
    11. 		{
    12. 			perror("realloc fail:");
    13. 				return;
    14. 		}
    15. 		ps->a = tmp;
    16. 		ps->capacity = newcapacity;
    17.  
    18. 	}
    19. 	//尾插
    20. 	ps->a[ps->top] = x;
    21. 	ps->top++;
    22. }
    23. void StackPop(Stack* ps)
    24. {
    25. 	assert(ps);
    26. 	assert(ps->top > 0);//只少有一个元素，才能删除
    27. 	ps->top--;
    28. }
    1.2.1.3 栈的元素个数和栈顶元素
    1. //栈的有效个数和栈顶元素
    2. int  StackSize(Stack* ps)
    3. {
    4. 	assert(ps);
    5. 	return ps->top;
    6. }
    7. int   StackTop(Stack* ps)
    8. {
    9. 	assert(ps);
    10. 	assert(ps->top > 0);
    11. 	return ps->a[ps->top - 1];
    12. }
    1.2.1.4  栈是否为空
    1. //栈是否为空
    2. bool StackEmpty(Stack* ps)
    3. {
    4. 	assert(ps);
    5. 	return ps->top == 0;
    6. }

    1.2.2  Stack.h

    1. #include
    2. #include
    3. #include
    4. typedef int  SDateType;
    5. typedef struct Stack
    6. {
    7. 	SDateType* a;
    8. 	int top;
    9. 	int capacity;
    10.  
    11. }Stack;
    12.  
    13. //初始化栈和销毁栈
    14. void InitStack(Stack* ps);
    15. void DestoryStack(Stack* ps);
    16.  
    17. //出栈和入栈
    18. void StackPush(Stack* ps, SDateType x);
    19. void StackPop(Stack* ps);
    20.  
    21. //栈的有效个数和栈顶元素
    22. int  StackSize(Stack* ps);
    23. int   StackTop(Stack* ps);
    24.  
    25. //栈是否为空
    26. bool StackEmpty(Stack* ps);

    1.2.3  Stach.c

    1. #include"Stack.h"
    2. //初始化栈和销毁栈
    3. void InitStack(Stack* ps)
    4. {
    5. 	assert(ps);
    6. 	ps->a = NULL;
    7. 	ps->capacity = ps->top = 0;
    8. }
    9. void DestoryStack(Stack* ps)
    10. {
    11. 	assert(ps);
    12. 	free(ps->a);
    13. 	ps->a = NULL;
    14. 	ps->capacity = ps->top = 0;
    15.  
    16. }
    17.  
    18. //出栈和入栈
    19. void StackPush(Stack* ps, SDateType x)
    20. {
    21. 	assert(ps);
    22. 	//扩容
    23. 	if (ps->top == ps->capacity)
    24. 	{
    25. 		SDateType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    26. 		SDateType* tmp = (SDateType*)realloc(ps->a,newcapacity*sizeof(SDateType));
    27. 		if (tmp == NULL)
    28. 		{
    29. 			perror("realloc fail:");
    30. 				return;
    31. 		}
    32. 		ps->a = tmp;
    33. 		ps->capacity = newcapacity;
    34.  
    35. 	}
    36. 	//尾插
    37. 	ps->a[ps->top] = x;
    38. 	ps->top++;
    39. }
    40. void StackPop(Stack* ps)
    41. {
    42. 	assert(ps);
    43. 	assert(ps->top > 0);//只少有一个元素，才能删除
    44. 	ps->top--;
    45. }
    46.  
    47. //栈的有效个数和栈顶元素
    48. int  StackSize(Stack* ps)
    49. {
    50. 	assert(ps);
    51. 	return ps->top;
    52. }
    53. int   StackTop(Stack* ps)
    54. {
    55. 	assert(ps);
    56. 	assert(ps->top > 0);
    57. 	return ps->a[ps->top - 1];
    58. }
    59.  
    60. //栈是否为空
    61. bool StackEmpty(Stack* ps)
    62. {
    63. 	assert(ps);
    64. 	return ps->top == 0;
    65. }

    二、队列

    2.1  队列的概念及结构

    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)的原则。

    入队列：进行插入操作的一端称为队尾

    出队列：进行删除操作的一端称为队头

    2.2  队列的实现（单链表队列）

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

    2.2.1 队列的基本功能实现

    1. #include
    2. #include
    3. #include
    4. #include
    5. typedef int QDateType;
    6. typedef struct QueueNode
    7. {
    8. 	QDateType val;
    9. 	struct QueueNode * next;
    10. }QueueNode;
    11. typedef struct Queue
    12. {
    13. 	QueueNode *head;
    14. 	QueueNode *tail;
    15. 	QDateType size;
    16. }Queue;
    17. // 初始化队列
    18. void QueueInit(Queue* pq);
    19. void QueueDestroy(Queue* pq);
    20.  
    21. // 队尾入列和出列
    22. void QueuePush(Queue* pq, QDateType x);
    23. void QueuePop(Queue* pq);
    24.  
    25.  
    26. // 返回队头和队尾
    27. QDateType QueueFront(Queue* pq);
    28. QDateType QueueBack(Queue* pq);
    29.  
    30. // 获取队列中有效元素个数
    31. int QueueSize(Queue* pq);
    32.  
    33. // 检测队列是否为空
    34. bool QueueEmpty(Queue* pq);
    2.2.1.1 队列的初始化和销毁
    1. // 初始化队列
    2. void QueueInit(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	pq->head = pq->tail = NULL;
    6. 	pq->size = 0;
    7. }
    8. //队列的销毁
    9. bool QueueEmpty(Queue* pq)
    10. {
    11. 	assert(pq);
    12. 	return pq->head==NULL;
    13. }
    2.2.1.2 入列和出列
    1. //入列
    2. void QueuePush(Queue* pq, QDateType x)
    3. {
    4. 	assert(pq);
    5. 	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    6. 	
    7. 	node->val = x;
    8. 	node->next = NULL;
    9. 	if (pq->tail == NULL)
    10. 	{
    11. 		pq->head = pq->tail = node;
    12. 		pq->size++;
    13. 	}
    14. 	else
    15. 	{
    16. 		pq->tail->next = node;
    17. 		pq->tail = node;
    18. 		pq->size++;
    19. 	}
    20. }
    21. //出列
    22. void QueuePop(Queue* pq)
    23. {
    24. 	assert(pq);
    25. 	assert(pq->head != NULL);//只少保证一个节点
    26. 	QueueNode* del = pq->head;
    27. 	pq->head = pq->head->next;
    28. 	free(del);
    29. 	del = NULL;
    30. 	pq->size--;
    31. 	if (pq->head == NULL)//只有一个节点处理
    32. 	{
    33. 		pq->tail = NULL;
    34. 	}
    35. }
    2.2.1.3    返回队头和队尾元素
    1. // 返回队头和队尾
    2. QDateType QueueFront(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	return pq->head->val;
    6. }
    7. QDateType QueueBack(Queue* pq)
    8. {
    9. 	assert(pq);
    10. 	return pq->tail->val;
    11. }
    2.2.1.4  队列元素个数
    1. // 获取队列中有效元素个数
    2. int QueueSize(Queue* pq)
    3. {
    4. 	assert(pq);
    5. 	return pq->size;
    6. }
    2.2.1.5  队列是否为空
    1. bool QueueEmpty(Queue* pq)
    2. {
    3. 	assert(pq);
    4. 	return pq->head==NULL;
    5. }

    2.2.2  Queue.h

    1. #include
    2. #include
    3. #include
    4. #include
    5. typedef int QDateType;
    6. typedef struct QueueNode
    7. {
    8. 	QDateType val;
    9. 	struct QueueNode * next;
    10. }QueueNode;
    11. typedef struct Queue
    12. {
    13. 	QueueNode *head;
    14. 	QueueNode *tail;
    15. 	QDateType size;
    16. }Queue;
    17. // 初始化队列
    18. void QueueInit(Queue* pq);
    19. void QueueDestroy(Queue* pq);
    20.  
    21. // 队尾入列和出列
    22. void QueuePush(Queue* pq, QDateType x);
    23. void QueuePop(Queue* pq);
    24.  
    25.  
    26. // 返回队头和队尾
    27. QDateType QueueFront(Queue* pq);
    28. QDateType QueueBack(Queue* pq);
    29.  
    30. // 获取队列中有效元素个数
    31. int QueueSize(Queue* pq);
    32.  
    33. // 检测队列是否为空
    34. bool QueueEmpty(Queue* pq);

    2.2.1 Queue.c

    1. #include"Queue.h"
    2. // 初始化队列
    3. void QueueInit(Queue* pq)
    4. {
    5. 	assert(pq);
    6. 	pq->head = pq->tail = NULL;
    7. 	pq->size = 0;
    8. }
    9.  
    10. void QueuePush(Queue* pq, QDateType x)
    11. {
    12. 	assert(pq);
    13. 	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    14. 	
    15. 	node->val = x;
    16. 	node->next = NULL;
    17. 	if (pq->tail == NULL)
    18. 	{
    19. 		pq->head = pq->tail = node;
    20. 		pq->size++;
    21. 	}
    22. 	else
    23. 	{
    24. 		pq->tail->next = node;
    25. 		pq->tail = node;
    26. 		pq->size++;
    27. 	}
    28. }
    29. void QueuePop(Queue* pq)
    30. {
    31. 	assert(pq);
    32. 	assert(pq->head != NULL);//只少保证一个节点
    33. 	QueueNode* del = pq->head;
    34. 	pq->head = pq->head->next;
    35. 	free(del);
    36. 	del = NULL;
    37. 	pq->size--;
    38. 	if (pq->head == NULL)//只有一个节点处理
    39. 	{
    40. 		pq->tail = NULL;
    41. 	}
    42. }
    43.  
    44. // 返回队头和队尾
    45. QDateType QueueFront(Queue* pq)
    46. {
    47. 	assert(pq);
    48. 	return pq->head->val;
    49. }
    50. QDateType QueueBack(Queue* pq)
    51. {
    52. 	assert(pq);
    53. 	return pq->tail->val;
    54. }
    55.  
    56. // 获取队列中有效元素个数
    57. int QueueSize(Queue* pq)
    58. {
    59. 	assert(pq);
    60. 	return pq->size;
    61. }
    62.  
    63.  
    64.  
    65. bool QueueEmpty(Queue* pq)
    66. {
    67. 	assert(pq);
    68. 	return pq->head==NULL;
    69. }
    70.  
    71. void QueueDestroy(Queue* pq)
    72. {
    73. 	assert(pq);
    74. 	QueueNode* cur = pq->head;
    75. 	while (cur)
    76. 	{
    77. 		QueueNode* next = cur->next;
    78. 		free(cur);
    79. 		cur = next;
    80. 	}
    81. 	pq->head = pq->tail = NULL;
    82. 	pq->size = 0;
    83.  
    84. }

  • 相关阅读:
    第三十二章 管理许可（五）
    Excel 快速分析
    你适合做自动化测试吗？
    【MySQL知识点】默认约束、非空约束
    第二部分 Makefile 总述
    【React学习】React高级特性
    【每日一题】回文串移除方案
    tensor类型、属性、torch.tensor与torch.Tensor的区别
    k线图形态这样记（口诀篇）
    学习笔记（1）
  • 原文地址：https://blog.csdn.net/zhoubancheng/article/details/134493745