devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构--栈，队列_栈和队是挨着的吗

作者：从前慢现在也慢 | 2024-05-18 17:48:59

赞

踩

栈和队是挨着的吗

前言

        这篇文章主要是关于栈与队列，为什么一般都是将栈与队列挨着讲，因为他们两个像一对欢喜冤家一样，在争锋相对的同时也互相成就，彼此通过不同的性质又可以联系在一起。本章节主要成分部分：什么是栈和队列，栈和队列的构造，栈和队列的习题。通过基础知识完成练习，通过练习巩固知识与理解栈与队列的联系。相信这篇文章会对大家有帮助，因为计算机就是解决我们生活中的问题，栈与队列的性质也是来源于生活中，比如栈--手枪的弹夹，队列--排队。

目录

前言

栈

栈的概念及结构

 栈的实现

实现代码

队列

队列的概念及结构

 队列的实现

 实现代码

循环队列

 栈和队列面试题

括号匹配问题---链接

用队列实现栈--链接

用栈实现队列--链接

设计循环队列--链接

栈

栈的概念及结构

栈：

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

动态演示

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

动态演示

 栈的实现

        栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为压栈与出栈正好满足数组的尾插与头删。数组的代价是及小的，操作相当于链表也更加简便。

动态演示

                                                                        压栈

出栈 

实现代码

主要步骤：

构建栈结构--数组，容量，栈顶

接口的实现--初始化栈 ，入栈，出栈 ，获取栈顶元素 ，获取栈中有效元素个数 ，检测栈是否为空， 销毁栈 

主函数演示

Stack.h

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma once
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <assert.h>
  6. #include <stdbool.h>
  7.  
  8. typedef int STDataType; 
  9.  
  10. //#define N 10
  11. //typedef struct Stack
  12. //{
  13. //	   STDataType _a[N]; 
  14. //	   int _top; // 栈顶
  15. //}Stack;
  16.  
  17. // 支持动态增长的栈
  18. typedef int STDataType;
  19. typedef struct Stack
  20. {
  21. 	STDataType* _a;
  22. 	int _top;       // 栈顶
  23. 	int _capacity;  // 容量 
  24. }Stack;
  25. // 初始化栈 
  26. void StackInit(Stack* ps); 
  27. // 入栈
  28. void StackPush(Stack* ps, STDataType data); 
  29. // 出栈 
  30. void StackPop(Stack* ps); 
  31. // 获取栈顶元素 
  32. STDataType StackTop(Stack* ps); 
  33. // 获取栈中有效元素个数 
  34. int StackSize(Stack* ps); 
  35. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  36. bool StackEmpty(Stack* ps);
  37. // 销毁栈 
  38. void StackDestroy(Stack* ps);

Stack.c

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "Stack.h"
  3.  
  4. // 初始化栈 
  5. void StackInit(Stack* ps)
  6. {
  7. 	assert(ps);//断言传入地址是否为空
  8. 	ps->_a = NULL;
  9. 	ps->_capacity = ps->_top = 0;
  10. }
  11.  
  12. // 入栈
  13. void StackPush(Stack* ps, STDataType data)
  14. {
  15. 	assert(ps);
  16. 	if (ps->_top == ps->_capacity)
  17. 	{
  18. 		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity*2;//判断容量是否为空并设置增加容量数量
  19.  
  20. 		STDataType* temp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));//增加容量
  21. 		if (temp == NULL)//判断地址是否开辟成功
  22. 		{
  23. 			perror("realloc fail");
  24. 			exit(-1);
  25. 		}
  26. 		ps->_a = temp;//赋址与结构体中
  27. 		ps->_capacity = newCapacity;//更新容量
  28. 	}
  29. 	ps->_a[ps->_top] = data;//数据入栈
  30. 	ps->_top++;//栈顶++
  31. }
  32.  
  33. // 出栈 
  34. void StackPop(Stack* ps)
  35. {
  36. 	assert(ps);
  37. 	assert(!StackEmpty(ps));//断言栈是否为空
  38. 	--ps->_top;//栈顶--
  39. }
  40.  
  41. // 获取栈顶元素 
  42. STDataType StackTop(Stack* ps)
  43. {
  44. 	assert(ps);
  45. 	assert(!StackEmpty(ps));
  46.  
  47. 	return ps->_a[ps->_top-1];
  48. }
  49.  
  50. // 获取栈中有效元素个数 
  51. int StackSize(Stack* ps)
  52. {
  53. 	assert(ps);
  54.  
  55. 	return ps->_top;
  56. }
  57.  
  58. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  59. bool StackEmpty(Stack* ps)
  60. {
  61. 	assert(ps);
  62. 	return ps->_top==0;
  63. }
  64.  
  65. // 销毁栈 
  66. void StackDestroy(Stack* ps)
  67. {
  68. 	assert(ps);
  69. 	free(ps->_a);//清除数组地址
  70. 	ps->_a = NULL;
  71. 	ps->_top = ps->_capacity = 0;
  72. }

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "Stack.h"
  3.  
  4.  
  5. //进栈--出栈演示
  6. void TestStack()
  7. {
  8. 	Stack ps;
  9. 	StackInit(&ps);
  10. 	StackPush(&ps,5);
  11. 	StackPush(&ps,6);
  12. 	StackPush(&ps,7);
  13. //	printf("%d ", StackTop(&ps));
  14. 	StackPop(&ps);
  15. //	printf("%d ", StackTop(&ps));
  16. 	StackPop(&ps);
  17.  
  18. 	while (!StackEmpty(&ps))
  19. 	{
  20. 		printf("%d ", StackTop(&ps));
  21. 		StackPop(&ps);
  22. 	}
  23. 	printf("\n");
  24. }
  25.  
  26. int main()
  27. {
  28. 	TestStack();
  29.  
  30. 	return 0;
  31. }

队列

队列的概念及结构

队列：

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

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

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

动态演示

 队列的实现

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

动态演示

 实现代码

实现步骤：

构建链式结构--结构体指针，数据

构建队列结构--头指针，尾指针

接口的实现--初始化队列 ，队尾入队列 ，队头出队列 ，获取队列头部元素，获取队列队尾元素 ，获取队列中有效元素个数 ， 检测队列是否为空 ， 销毁队列 。

主函数演示

Queue.h

  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <stdlib.h>
  4. #include <stdbool.h>
  5.  
  6. // 链式结构：表示队列 
  7. typedef int QDataType;
  8. typedef struct QListNode
  9. {
  10. 	struct QListNode* _next;
  11. 	QDataType _data;
  12. }QNode;
  13.  
  14. // 队列的结构 
  15. typedef struct Queue
  16. {
  17. 	QNode* _front;
  18. 	QNode* _rear;
  19. 	QDataType _size;
  20. }Queue;
  21.  
  22. // 初始化队列 
  23. void QueueInit(Queue* q);
  24. // 队尾入队列 
  25. void QueuePush(Queue* q, QDataType data);
  26. // 队头出队列 
  27. void QueuePop(Queue* q);
  28. // 获取队列头部元素 
  29. QDataType QueueFront(Queue* q);
  30. // 获取队列队尾元素 
  31. QDataType QueueBack(Queue* q);
  32. // 获取队列中有效元素个数 
  33. int QueueSize(Queue* q);
  34. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  35. bool QueueEmpty(Queue* q);
  36. // 销毁队列 
  37. void QueueDestroy(Queue* q);

Queue.c

  1. #include "Queue.h"
  2.  
  3. // 初始化队列
  4. void QueueInit(Queue* q)
  5. {
  6. 	assert(q);
  7. 	q->_front = q->_rear = NULL;
  8. 	q->_size = 0;
  9. }
  10.  
  11. // 队尾入队列 
  12. void QueuePush(Queue* q, QDataType data)
  13. {
  14. 	assert(q);
  15.  
  16. 	QNode* cur = (QNode*)malloc(sizeof(QNode));
  17. 	if (cur == NULL)
  18. 	{
  19. 		perror("malloc fail");
  20. 		exit(-1);
  21. 	}
  22. 	else
  23. 	{
  24. 		cur->_data = data;
  25. 		cur->_next = NULL;
  26. 	}
  27.  
  28. 	if (q->_rear == NULL)
  29. 	{
  30. 		q->_front = q->_rear = cur;
  31. 	}
  32. 	else
  33. 	{
  34. 		q->_rear->_next = cur;
  35. 		q->_rear = cur;
  36. 	}
  37. 	q->_size++;
  38. }
  39.  
  40. // 队头出队列 
  41. void QueuePop(Queue* q)
  42. {
  43. 	assert(q);
  44. 	assert(!QueueEmpty(q));
  45. 	if (q->_front->_next==NULL)
  46. 	{
  47. 		free(q->_front);
  48. 		q->_front = q->_rear = NULL;
  49. 	}
  50. 	else
  51. 	{
  52. 		QNode* cur = q->_front;
  53. 		q->_front = q->_front->_next;
  54. 		free(cur);
  55. 		cur = NULL;
  56. 	}
  57. 	q->_size--;
  58. }
  59. // 获取队列头部元素 
  60. QDataType QueueFront(Queue* q)
  61. {
  62. 	assert(q);
  63. 	assert(!QueueEmpty(q));
  64. 	return q->_front->_data;
  65. }
  66.  
  67. // 获取队列队尾元素 
  68. QDataType QueueBack(Queue* q)
  69. {
  70. 	assert(q);
  71. 	assert(!QueueEmpty(q));
  72. 	return q->_rear->_data;
  73. }
  74.  
  75. // 获取队列中有效元素个数 
  76. int QueueSize(Queue* q)
  77. {
  78. 	assert(q);
  79. 	
  80. 	return q->_size;
  81. }
  82.  
  83. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  84. bool QueueEmpty(Queue* q)
  85. {
  86. 	assert(q);
  87.  
  88. 	return q->_front == NULL && q->_rear == NULL;
  89. }
  90.  
  91. // 销毁队列 
  92. void QueueDestroy(Queue* q)
  93. {
  94. 	assert(q);
  95. 	QNode* cur = q->_front;
  96. 	while (cur)
  97. 	{
  98. 		QNode* del = cur;
  99. 		cur = cur->_next;
  100. 		free(del);
  101. 		del = NULL;
  102. 	}
  103. 	q->_front = q->_rear = NULL;
  104. }

Test.c

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

循环队列

        另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

 

 栈和队列面试题

括号匹配问题---链接

动态演示

 

 两种特殊错误情况

实现代码

  1. typedef char STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* _a;
  5. 	int _top;       // 栈顶
  6. 	int _capacity;  // 容量 
  7. }Stack;
  8. // 初始化栈 
  9. void StackInit(Stack* ps); 
  10. // 入栈
  11. void StackPush(Stack* ps, STDataType data); 
  12. // 出栈 
  13. void StackPop(Stack* ps); 
  14. // 获取栈顶元素 
  15. STDataType StackTop(Stack* ps); 
  16. // 获取栈中有效元素个数 
  17. int StackSize(Stack* ps); 
  18. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  19. bool StackEmpty(Stack* ps);
  20. // 销毁栈 
  21. void StackDestroy(Stack* ps);
  22.  
  23. // 初始化栈 
  24. void StackInit(Stack* ps)
  25. {
  26. 	assert(ps);//断言传入地址是否为空
  27. 	ps->_a = NULL;
  28. 	ps->_capacity = ps->_top = 0;
  29. }
  30.  
  31. // 入栈
  32. void StackPush(Stack* ps, STDataType data)
  33. {
  34. 	assert(ps);
  35. 	if (ps->_top == ps->_capacity)
  36. 	{
  37. 		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity*2;//判断容量是否为空并设置增加容量数量
  38.  
  39. 		STDataType* temp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));//增加容量
  40. 		if (temp == NULL)//判断地址是否开辟成功
  41. 		{
  42. 			perror("realloc fail");
  43. 			exit(-1);
  44. 		}
  45. 		ps->_a = temp;//赋址与结构体中
  46. 		ps->_capacity = newCapacity;//更新容量
  47. 	}
  48. 	ps->_a[ps->_top] = data;//数据入栈
  49. 	ps->_top++;//栈顶++
  50. }
  51.  
  52. // 出栈 
  53. void StackPop(Stack* ps)
  54. {
  55. 	assert(ps);
  56. 	assert(!StackEmpty(ps));//断言栈是否为空
  57. 	--ps->_top;//栈顶--
  58. }
  59.  
  60. // 获取栈顶元素 
  61. STDataType StackTop(Stack* ps)
  62. {
  63. 	assert(ps);
  64. 	assert(!StackEmpty(ps));
  65.  
  66. 	return ps->_a[ps->_top-1];
  67. }
  68.  
  69. // 获取栈中有效元素个数 
  70. int StackSize(Stack* ps)
  71. {
  72. 	assert(ps);
  73.  
  74. 	return ps->_top;
  75. }
  76.  
  77. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  78. bool StackEmpty(Stack* ps)
  79. {
  80. 	assert(ps);
  81. 	return ps->_top==0;
  82. }
  83.  
  84. // 销毁栈 
  85. void StackDestroy(Stack* ps)
  86. {
  87. 	assert(ps);
  88. 	free(ps->_a);//清除数组地址
  89. 	ps->_a = NULL;
  90. 	ps->_top = ps->_capacity = 0;
  91. }
  92.  
  93. bool isValid(char * s){
  94.     Stack st;
  95.     StackInit(&st);
  96.     while(*s)
  97.     {
  98.         if(*s=='('||*s=='{'||*s=='[')
  99.         {
  100.             StackPush(&st,*s);
  101.         }
  102.         else 
  103.         {
  104.             if(StackEmpty(&st))
  105.             {
  106.                  StackDestroy(&st);
  107.                  return false;
  108.             }
  109.             char tem= StackTop(&st);
  110.             StackPop(&st);
  111.             if(*s=='}' && tem!='{' || *s==')' && tem!='(' || *s==']' && tem!='[')
  112.             {
  113.                 StackDestroy(&st);
  114.                 return false;
  115.             }
  116.         }
  117.         s++;
  118.     }
  119.     bool flag=StackEmpty(&st);
  120.     StackDestroy(&st);
  121.     return flag;
  122. }

用队列实现栈--链接

动态演示

 

 实现代码

  1. // 链式结构：表示队列 
  2. typedef int QDataType;
  3. typedef struct QListNode
  4. {
  5. 	struct QListNode* _next;
  6. 	QDataType _data;
  7. }QNode;
  8.  
  9. // 队列的结构 
  10. typedef struct Queue
  11. {
  12. 	QNode* _front;
  13. 	QNode* _rear;
  14. 	QDataType _size;
  15. }Queue;
  16.  
  17. // 初始化队列 
  18. void QueueInit(Queue* q);
  19. // 队尾入队列 
  20. void QueuePush(Queue* q, QDataType data);
  21. // 队头出队列 
  22. void QueuePop(Queue* q);
  23. // 获取队列头部元素 
  24. QDataType QueueFront(Queue* q);
  25. // 获取队列队尾元素 
  26. QDataType QueueBack(Queue* q);
  27. // 获取队列中有效元素个数 
  28. int QueueSize(Queue* q);
  29. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  30. bool QueueEmpty(Queue* q);
  31. // 销毁队列 
  32. void QueueDestroy(Queue* q);
  33.  
  34.  
  35. // 初始化队列
  36. void QueueInit(Queue* q)
  37. {
  38. 	assert(q);
  39. 	q->_front = q->_rear = NULL;
  40. 	q->_size = 0;
  41. }
  42.  
  43. // 队尾入队列 
  44. void QueuePush(Queue* q, QDataType data)
  45. {
  46. 	assert(q);
  47.  
  48. 	QNode* cur = (QNode*)malloc(sizeof(QNode));
  49. 	if (cur == NULL)
  50. 	{
  51. 		perror("malloc fail");
  52. 		exit(-1);
  53. 	}
  54. 	else
  55. 	{
  56. 		cur->_data = data;
  57. 		cur->_next = NULL;
  58. 	}
  59.  
  60. 	if (q->_rear == NULL)
  61. 	{
  62. 		q->_front = q->_rear = cur;
  63. 	}
  64. 	else
  65. 	{
  66. 		q->_rear->_next = cur;
  67. 		q->_rear = cur;
  68. 	}
  69. 	q->_size++;
  70. }
  71.  
  72. // 队头出队列 
  73. void QueuePop(Queue* q)
  74. {
  75. 	assert(q);
  76. 	assert(!QueueEmpty(q));
  77. 	if (q->_front->_next==NULL)
  78. 	{
  79. 		free(q->_front);
  80. 		q->_front = q->_rear = NULL;
  81. 	}
  82. 	else
  83. 	{
  84. 		QNode* cur = q->_front;
  85. 		q->_front = q->_front->_next;
  86. 		free(cur);
  87. 		cur = NULL;
  88. 	}
  89. 	q->_size--;
  90. }
  91. // 获取队列头部元素 
  92. QDataType QueueFront(Queue* q)
  93. {
  94. 	assert(q);
  95. 	assert(!QueueEmpty(q));
  96. 	return q->_front->_data;
  97. }
  98.  
  99. // 获取队列队尾元素 
  100. QDataType QueueBack(Queue* q)
  101. {
  102. 	assert(q);
  103. 	assert(!QueueEmpty(q));
  104. 	return q->_rear->_data;
  105. }
  106.  
  107. // 获取队列中有效元素个数 
  108. int QueueSize(Queue* q)
  109. {
  110. 	assert(q);
  111. 	
  112. 	return q->_size;
  113. }
  114.  
  115. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  116. bool QueueEmpty(Queue* q)
  117. {
  118. 	assert(q);
  119.  
  120. 	return q->_front == NULL && q->_rear == NULL;
  121. }
  122.  
  123. // 销毁队列 
  124. void QueueDestroy(Queue* q)
  125. {
  126. 	assert(q);
  127. 	QNode* cur = q->_front;
  128. 	while (cur)
  129. 	{
  130. 		QNode* del = cur;
  131. 		cur = cur->_next;
  132. 		free(del);
  133. 		del = NULL;
  134. 	}
  135. 	q->_front = q->_rear = NULL;
  136. }
  137.  
  138. typedef struct {
  139.     Queue q1;
  140.     Queue q2;
  141. } MyStack;
  142.  
  143. //创建队列形成的栈
  144. MyStack* myStackCreate() {
  145.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
  146.     QueueInit(&obj->q1);
  147.     QueueInit(&obj->q2);
  148.  
  149.     return obj;
  150. }
  151.  
  152. //压栈
  153. void myStackPush(MyStack* obj, int x) {
  154.     if(!QueueEmpty(&obj->q1))
  155.     {
  156.         QueuePush(&obj->q1,x);
  157.     }
  158.     else
  159.     {
  160.         QueuePush(&obj->q2,x);
  161.     }
  162. }
  163.  
  164. //出栈 QueuePop
  165. int myStackPop(MyStack* obj) {
  166.     QNode* empty=&obj->q1;
  167.     QNode* nonempty=&obj->q2;
  168.     if(!QueueEmpty(&obj->q1))
  169.     {
  170.         empty=&obj->q2;
  171.         nonempty=&obj->q1;
  172.     }
  173.     
  174.     while(QueueSize(nonempty)>1)
  175.     {
  176.          QueuePush(empty,QueueFront(nonempty));
  177.          QueuePop(nonempty);
  178.     }
  179.     int top=QueueFront(nonempty);
  180.     QueuePop(nonempty);
  181.     return top;
  182. }
  183.  
  184. //栈顶值
  185. int myStackTop(MyStack* obj) {
  186.      if(!QueueEmpty(&obj->q1))
  187.     {
  188.       return QueueBack(&obj->q1) ;
  189.     }
  190.     else
  191.     {
  192.         return QueueBack(&obj->q2);
  193.     }
  194. }
  195. //判断栈为空
  196. bool myStackEmpty(MyStack* obj) {
  197.  
  198.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
  199. }
  200.  
  201. //释放栈
  202. void myStackFree(MyStack* obj) {
  203.     QueueDestroy(&obj->q1);
  204.     QueueDestroy(&obj->q2);
  205.     free(obj);
  206.     obj==NULL;
  207. }
  208.  
  209. /**
  210.  * Your MyStack struct will be instantiated and called as such:
  211.  * MyStack* obj = myStackCreate();
  212.  * myStackPush(obj, x);
  213.  
  214.  * int param_2 = myStackPop(obj);
  215.  
  216.  * int param_3 = myStackTop(obj);
  217.  
  218.  * bool param_4 = myStackEmpty(obj);
  219.  
  220.  * myStackFree(obj);
  221. */

用栈实现队列--链接

动态演示

  实现代码

  1. typedef int STDataType; 
  2.  
  3. //#define N 10
  4. //typedef struct Stack
  5. //{
  6. //	   STDataType _a[N]; 
  7. //	   int _top; // 栈顶
  8. //}Stack;
  9.  
  10. // 支持动态增长的栈
  11. typedef int STDataType;
  12. typedef struct Stack
  13. {
  14. 	STDataType* _a;
  15. 	int _top;       // 栈顶
  16. 	int _capacity;  // 容量 
  17. }Stack;
  18. // 初始化栈 
  19. void StackInit(Stack* ps); 
  20. // 入栈
  21. void StackPush(Stack* ps, STDataType data); 
  22. // 出栈 
  23. void StackPop(Stack* ps); 
  24. // 获取栈顶元素 
  25. STDataType StackTop(Stack* ps); 
  26. // 获取栈中有效元素个数 
  27. int StackSize(Stack* ps); 
  28. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  29. bool StackEmpty(Stack* ps);
  30. // 销毁栈 
  31. void StackDestroy(Stack* ps);
  32.  
  33. // 初始化栈 
  34. void StackInit(Stack* ps)
  35. {
  36. 	assert(ps);//断言传入地址是否为空
  37. 	ps->_a = NULL;
  38. 	ps->_capacity = ps->_top = 0;
  39. }
  40.  
  41. // 入栈
  42. void StackPush(Stack* ps, STDataType data)
  43. {
  44. 	assert(ps);
  45. 	if (ps->_top == ps->_capacity)
  46. 	{
  47. 		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity*2;//判断容量是否为空并设置增加容量数量
  48.  
  49. 		STDataType* temp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));//增加容量
  50. 		if (temp == NULL)//判断地址是否开辟成功
  51. 		{
  52. 			perror("realloc fail");
  53. 			exit(-1);
  54. 		}
  55. 		ps->_a = temp;//赋址与结构体中
  56. 		ps->_capacity = newCapacity;//更新容量
  57. 	}
  58. 	ps->_a[ps->_top] = data;//数据入栈
  59. 	ps->_top++;//栈顶++
  60. }
  61.  
  62. // 出栈 
  63. void StackPop(Stack* ps)
  64. {
  65. 	assert(ps);
  66. 	assert(!StackEmpty(ps));//断言栈是否为空
  67. 	--ps->_top;//栈顶--
  68. }
  69.  
  70. // 获取栈顶元素 
  71. STDataType StackTop(Stack* ps)
  72. {
  73. 	assert(ps);
  74. 	assert(!StackEmpty(ps));
  75.  
  76. 	return ps->_a[ps->_top-1];
  77. }
  78.  
  79. // 获取栈中有效元素个数 
  80. int StackSize(Stack* ps)
  81. {
  82. 	assert(ps);
  83.  
  84. 	return ps->_top;
  85. }
  86.  
  87. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  88. bool StackEmpty(Stack* ps)
  89. {
  90. 	assert(ps);
  91. 	return ps->_top==0;
  92. }
  93.  
  94. // 销毁栈 
  95. void StackDestroy(Stack* ps)
  96. {
  97. 	assert(ps);
  98. 	free(ps->_a);//清除数组地址
  99. 	ps->_a = NULL;
  100. 	ps->_top = ps->_capacity = 0;
  101. }
  102.  
  103. typedef struct {
  104.     Stack push;
  105.     Stack pop;
  106.  
  107. } MyQueue;
  108.  
  109.  
  110. MyQueue* myQueueCreate() {
  111.     MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
  112.     StackInit(&obj->push);
  113.     StackInit(&obj->pop);
  114.  
  115.     return obj;
  116. }
  117.  
  118. void myQueuePush(MyQueue* obj, int x) {
  119.        
  120.         StackPush(&obj->push,x);  
  121. }
  122.  
  123. int myQueuePop(MyQueue* obj) {
  124.    if(StackEmpty(&obj->pop))
  125.    {
  126.        while(!StackEmpty(&obj->push))
  127.      {
  128.        StackPush(&obj->pop,StackTop(&obj->push));
  129.        StackPop(&obj->push);
  130.      }
  131.    }
  132.    
  133.    STDataType tem =StackTop(&obj->pop);
  134.    StackPop(&obj->pop);
  135.    
  136.    return tem;
  137. }
  138.  
  139. int myQueuePeek(MyQueue* obj) {
  140.     if(StackEmpty(&obj->pop))
  141.    {
  142.        while(!StackEmpty(&obj->push))
  143.      {
  144.        StackPush(&obj->pop,StackTop(&obj->push));
  145.        StackPop(&obj->push);
  146.      }
  147.    }
  148.     
  149.     return StackTop(&obj->pop);
  150. }
  151.  
  152. bool myQueueEmpty(MyQueue* obj) {
  153.     return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
  154. }
  155.  
  156. void myQueueFree(MyQueue* obj) {
  157.     StackDestroy(&obj->push);
  158.     StackDestroy(&obj->pop);
  159.     free(obj);
  160. }
  161.  
  162. /**
  163.  * Your MyQueue struct will be instantiated and called as such:
  164.  * MyQueue* obj = myQueueCreate();
  165.  * myQueuePush(obj, x);
  166.  
  167.  * int param_2 = myQueuePop(obj);
  168.  
  169.  * int param_3 = myQueuePeek(obj);
  170.  
  171.  * bool param_4 = myQueueEmpty(obj);
  172.  
  173.  * myQueueFree(obj);
  174. */

设计循环队列--链接

用数组更好还是链表

在考虑用谁更好时，有个问题已经来了，如何判断满和空

判断空只需要front==rear就为空

 判断满 有两个方法： 1.用size计数 2.增加一个空节点

这里如果用size的话我们发现实现循环还是需要加节点，那如果不加呢？

不加节点我们发现，先走的rear，如果满了rear与front就重复了到底是空还是满就不好判断。所以这里我们选择加节点。

当加了节点我们发现循环之后需要获取队列最后一个元素时，需要重新遍历或者加一个指向前面的指针

当我们决定用数组时我们需要注意什么呢？

 当rear进行循环时，rear+1会出现越界的问题，如何解决呢？

我们只需要（rear+1）%rear 即可，就可以进行循环。

动态演示

 实现代码

  1. typedef struct {
  2.     int *a;
  3.     int front;
  4.     int rear;
  5.     int N;
  6. } MyCircularQueue;
  7.  
  8.  
  9. MyCircularQueue* myCircularQueueCreate(int k) {
  10.     MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  11.     obj->a=(int*)malloc((k+1)*sizeof(int));
  12.     obj->front=obj->rear=0;
  13.     obj->N=k+1;
  14.     
  15.     return obj;
  16. }
  17.  
  18. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  19.     return obj->front==obj->rear;
  20. }
  21.  
  22. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  23.     return (obj->rear+1)%obj->N==obj->front;
  24. }
  25.  
  26. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  27.     if( myCircularQueueIsFull(obj))
  28.     return false;
  29.  
  30.     obj->a[obj->rear]=value;
  31.     obj->rear++;
  32.     obj->rear %= obj->N;
  33.  
  34.     return true;
  35. }
  36.  
  37. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  38.     if(myCircularQueueIsEmpty(obj))
  39.     return false;
  40.  
  41.     obj->front++;
  42.  
  43.     obj->front %= obj->N;
  44.     return true;
  45. }
  46.  
  47. int myCircularQueueFront(MyCircularQueue* obj) {
  48.     if(myCircularQueueIsEmpty(obj))
  49.         return -1;
  50.     else
  51.         return obj->a[obj->front];
  52. }
  53.  
  54. int myCircularQueueRear(MyCircularQueue* obj) {
  55.     if(myCircularQueueIsEmpty(obj))
  56.         return -1;
  57.     else
  58.         return obj->a[(obj->rear+obj->N-1)%obj->N];
  59. }
  60.  
  61.  
  62.  
  63. void myCircularQueueFree(MyCircularQueue* obj) {
  64.     free(obj->a);
  65.     free(obj);
  66. }
  67.  
  68. /**
  69.  * Your MyCircularQueue struct will be instantiated and called as such:
  70.  * MyCircularQueue* obj = myCircularQueueCreate(k);
  71.  * bool param_1 = myCircularQueueEnQueue(obj, value);
  72.  
  73.  * bool param_2 = myCircularQueueDeQueue(obj);
  74.  
  75.  * int param_3 = myCircularQueueFront(obj);
  76.  
  77.  * int param_4 = myCircularQueueRear(obj);
  78.  
  79.  * bool param_5 = myCircularQueueIsEmpty(obj);
  80.  
  81.  * bool param_6 = myCircularQueueIsFull(obj);
  82.  
  83.  * myCircularQueueFree(obj);
  84. */

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/589291
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号