关键词搜索

源码搜索 ×
×

【数据结构】栈和队列典例--纯C

发布2022-04-06浏览1756次

详情内容

 s​​​​​​​20. 有效的括号

通过题目描述的问题，使用栈来解决是最优解。

思路：１）找到左括号们，将其入栈，遇到右括号就开始依次出栈，如果不符合匹配标准，就返回ｆａｌｓｅ

２）匹配过程中，会出现栈内数据为空但是需要从站内取数据的情况，出现遍历字符串结束后，栈内数据不为空的情况都需要额外考虑。

画图：

针对思路２的要额外处理

代码：

  1. typedef int 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. 	ps->a = NULL;
  12. 	ps->capacity = ps->top = 0;
  13. }
  14.  
  15. //销毁
  16. void StackDestroy(Stack* ps)
  17. {
  18. 	
  19. 	free(ps->a);
  20. 	ps->a = NULL;
  21. 	ps->capacity = ps->top = 0;
  22. }
  23.  
  24. //入栈
  25. void StackPush(Stack* ps, STDataType x)
  26. {
  27. 	//断言
  28. 	assert(ps);
  29. 	//判断是否需要扩容
  30. 	if (ps->top == ps->capacity)
  31. 	{
  32. 		int newcapacity = ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2;
  33. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
  34. 		//判断扩容是否成功
  35. 		if (tmp == NULL)
  36. 		{
  37. 			printf("realloc fail\n");
  38. 			exit(-1);
  39. 		}
  40. 		ps->a = tmp;
  41. 		ps->capacity = newcapacity;
  42. 	}
  43. 	//插入数据
  44. 	//数组的下标从0开始，top指向的就是栈顶
  45. 	ps->a[ps->top] = x;
  46. 	ps->top++;
  47. }
  48.  
  49. //出栈
  50. void StackPop(Stack* ps)
  51. {
  52. 	assert(ps);
  53. 	//断言栈是否为空
  54. 	assert(ps->top > 0);
  55.  
  56. 	ps->top--;
  57. }
  58.  
  59. //获取栈顶元素
  60. STDataType StackTop(Stack* ps)
  61. {
  62. 	assert(ps);
  63. 	//断言栈是否为空
  64. 	assert(ps->top);
  65.  
  66. 	return ps->a[ps->top-1];
  67. }
  68.  
  69. //检测栈是否为空
  70. bool StackEmpty(Stack* ps)
  71. {
  72. 	assert(ps);
  73. 	非空
  74. 	//if (ps->top > 0)
  75. 	//{
  76. 	//	return false;
  77. 	//}
  78. 	为空
  79. 	//else
  80. 	//	return true;
  81. 	//更优化的写法
  82. 	return ps->top == 0;
  83. }
  84.  
  85. int StackSize(Stack* ps)
  86. {
  87. 	assert(ps);
  88. 	//返回个数，top指的是栈顶数据的下一位。
  89. 	return ps->top;
  90. }
  91.  
  92. bool isValid(char * s){
  93.     Stack st;
  94.     StackInit(&st);//初始化
  95.     while(*s!='\0')//遍历
  96.     {
  97.         if(*s=='{'||*s=='['||*s=='(')
  98.         {
  99.             StackPush(&st,*s);//当为{,[,( 时入栈
  100.             s++;//更新
  101.         }
  102.         else
  103.         {
  104.             if(!StackEmpty(&st))//当栈不为空时
  105.             {
  106.             char top = StackTop(&st);//取出栈顶数据
  107.             StackPop(&st);//删除栈顶数据
  108.             if((top == '{'&& *s!='}')||(top == '('&&*s!=')'||top == '['&&*s!=']'))//如果不匹配，就返回false
  109.             {
  110.                 return false;
  111.             }
  112.             else
  113.             {
  114.                 s++;
  115.             }
  116.             }
  117.             else//当栈为空时，说明其缺少左括号，必然不能配对
  118.             return false;
  119.         }
  120.  
  121.     }
  122.     //循环结束时
  123.     int ret = StackEmpty(&st);//记录栈是否为空
  124.     StackDestroy(&st);//销毁栈
  125.     if(ret)//当栈为空，即结束了匹配
  126.         return true;
  127.     else//栈内有数据，就说明循环结束时，原字符串有单个左括号无法被匹配。
  128.         return false;
  129.     
  130.  
  131. }

225. 用队列实现栈

思路：队列的性质是：先入先出；栈的性质是：后入后出。

可以创建两个队列，先使用一个存数据，要取出数据时，可以将前N－１个数据移到另一个队列，取出（并删除）数据，以此往复，模拟实现栈的相关功能。

画图：

移除并返回栈顶元素：

取出５

将队列１中的数据清空

插入数据：

刚开始可以随意选择一个空的队列插入，在后面插入的元素都必须插入到非空队列中。

这里可以通过选择语句确立空与非空队列。

返回栈顶元素：

队列拥有访问队尾元素的功能，所以可以直接通过队列来实现。

判断是否为空：

队列１和　队列２　同时为空时，栈为空。

代码：

  1. typedef int QDataType;
  2.  
  3. //链表的节点
  4. typedef struct QueueNode
  5. {
  6. 	QDataType data;//数据
  7. 	struct QueueNode* next;//标记下一个节点
  8. }QNode;
  9.  
  10. typedef struct Queue
  11. {
  12. 	QNode* head;//头指针
  13. 	QNode* tail;//尾指针
  14. }Queue;
  15. void QueueInit(Queue* pq)
  16. {
  17. 	assert(pq);
  18. 	pq->head = pq->tail = NULL;
  19. }
  20.  
  21. void QueueDestory(Queue* pq)
  22. {
  23. 	assert(pq);
  24. 	QNode* cur = pq->head;
  25. 	while (cur)
  26. 	{
  27. 		QNode* next = cur->next;
  28. 		free(cur);
  29. 		cur = next;
  30. 	}
  31.  
  32. 	pq->head = pq->tail = NULL;
  33. }
  34.  
  35. void QueuePush(Queue* pq, QDataType x)
  36. {
  37. 	assert(pq);
  38. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  39. 	assert(newnode);
  40.  
  41. 	newnode->data = x;
  42. 	newnode->next = NULL;
  43.  
  44. 	if (pq->tail == NULL)
  45. 	{
  46. 		assert(pq->head == NULL);
  47. 		pq->head = pq->tail = newnode;
  48. 	}
  49. 	else
  50. 	{
  51. 		pq->tail->next = newnode;
  52. 		pq->tail = newnode;
  53. 	}
  54. }
  55.  
  56. void QueuePop(Queue* pq)
  57. {
  58. 	assert(pq);
  59. 	assert(pq->head && pq->tail);
  60.  
  61. 	if (pq->head->next == NULL)
  62. 	{
  63. 		free(pq->head);
  64. 		pq->head = pq->tail = NULL;
  65. 	}
  66. 	else
  67. 	{
  68. 		QNode* next = pq->head->next;
  69. 		free(pq->head);
  70. 		pq->head = next;
  71. 	}
  72. }
  73.  
  74. bool QueueEmpty(Queue* pq)
  75. {
  76. 	assert(pq);
  77.  
  78. 	//return pq->head == NULL && pq->tail == NULL;
  79. 	return pq->head == NULL;
  80. }
  81.  
  82. size_t QueueSize(Queue* pq)
  83. {
  84. 	assert(pq);
  85. 	QNode* cur = pq->head;
  86. 	size_t size = 0;
  87. 	while (cur)
  88. 	{
  89. 		size++;
  90. 		cur = cur->next;
  91. 	}
  92.  
  93. 	return size;
  94. }
  95.  
  96. QDataType QueueFront(Queue* pq)
  97. {
  98. 	assert(pq);
  99. 	assert(pq->head);
  100.  
  101. 	return pq->head->data;
  102. }
  103.  
  104. QDataType QueueBack(Queue* pq)
  105. {
  106. 	assert(pq);
  107. 	assert(pq->tail);
  108.  
  109. 	return pq->tail->data;
  110. }
  111.  
  112. typedef struct {
  113.     //创建两个队列
  114.     Queue q1;
  115.     Queue q2;
  116.  
  117. } MyStack;
  118.  
  119.  
  120. MyStack* myStackCreate() {
  121.     //为结构体分配空间，不能使用
  122.     //MyStack st;  栈上开辟的临时变量，出栈即销毁，返回的指针为空指针。
  123.     //在堆上开辟空间，malloc动态开辟
  124.     MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
  125.     //assert(pst);//可有可无
  126.     //Mystack结构体成员初始化
  127.     QueueInit(&pst->q1);
  128.  
  129.     QueueInit(&pst->q2);
  130.     return pst;
  131. }
  132.  
  133. void myStackPush(MyStack* obj, int x) {
  134.     //非空的队列放入数据，始终保持存在一个空的队列
  135.     if(!QueueEmpty(&obj->q1))//非空
  136.     {
  137.         QueuePush(&obj->q1,x);
  138.     }
  139.     else
  140.     {
  141.         QueuePush(&obj->q2,x);
  142.     }
  143.  
  144. }
  145.  
  146. int myStackPop(MyStack* obj) {
  147.     //assert(obj);
  148.     //指定一个空队列和非空队列,定义q1为空
  149.     Queue* empty = &obj->q1;
  150.     Queue* nonempty = &obj->q2;
  151.     //若不是，就交换
  152.     if(!QueueEmpty(&obj->q1))
  153.     {
  154.         empty = &obj->q2;
  155.         nonempty = &obj->q1;
  156.     }
  157.     while(QueueSize(nonempty)>1)//从非空队列中持续取数据放入空队列中，并删数据
  158.     {
  159.         QDataType front = QueueFront(nonempty);//获取数据
  160.         QueuePush(empty,front);//插入数据
  161.         QueuePop(nonempty);//删数据
  162.     }
  163.     //获取“栈顶”数据
  164.     QDataType top = QueueFront(nonempty);
  165.     移除栈顶数据
  166.     QueuePop(nonempty);
  167.     //返回“栈顶”元素
  168.     return top;
  169.  
  170. }
  171.  
  172. int myStackTop(MyStack* obj) {
  173.     //指定一个空队列和非空队列,定义q1为空
  174.     Queue* empty = &obj->q1;
  175.     Queue* nonempty = &obj->q2;
  176.     //若不是，就交换
  177.     if(!QueueEmpty(&obj->q1))
  178.     {
  179.         empty = &obj->q2;
  180.         nonempty = &obj->q1;
  181.     }
  182.  
  183.     return QueueBack(nonempty);
  184.  
  185. }
  186.  
  187. bool myStackEmpty(MyStack* obj) {
  188.     assert(obj);
  189.     //当q1和q2同时为空时，“栈”为空
  190.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
  191.  
  192. }
  193.  
  194. void myStackFree(MyStack* obj) {
  195.     //释放内存时，先解决结构体内部的q1和q2
  196.     assert(obj);
  197.     QueueDestory(&obj->q1);
  198.     QueueDestory(&obj->q2);
  199.     free(obj);
  200.     //置空并不会改变实参的状态
  201.  
  202. }
  203.

用栈实现队列

思路：栈的性质：后入后出；队列的性质：先入先出。

创立两个栈，在两个栈上模拟实现队列的基本功能。

画图：

先入1　2　3　4　5　数据

ｐｏｐ

取出队头元素1

将栈1的所有元素移植至栈2

从栈二中提取目标元素1

ｐｅｅｋ

通过ｐｏｐ可以看出，栈２中的数据可以模仿队列出数据。

由此可以得出结论：模拟实现队列只需要导数据1次即可。

 

ｐｕｓｈ

 

根据已有的结论，将数据先导入栈1中，等到栈2中的数据被删空时再将栈1中的数据导入栈2中。

 

ｅｍｐｔｙ

栈1　和　栈2　同时为空时队列为空。

 

注意：在ｐｏｐ和　ｐｕｓｈ数据时，要判断是否为空的情况。

 

代码：

  1. typedef int STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* a;
  5. 	int top;//栈顶
  6. 	int capacity;//容量
  7. }Stack;
  8. void StackInit(Stack* ps)
  9. {
  10. 	ps->a = NULL;
  11. 	ps->capacity = ps->top = 0;
  12. }
  13.  
  14. //销毁
  15. void StackDestroy(Stack* ps)
  16. {
  17. 	
  18. 	free(ps->a);
  19. 	ps->a = NULL;
  20. 	ps->capacity = ps->top = 0;
  21. }
  22.  
  23. //入栈
  24. void StackPush(Stack* ps, STDataType x)
  25. {
  26. 	//断言
  27. 	assert(ps);
  28. 	//判断是否需要扩容
  29. 	if (ps->top == ps->capacity)
  30. 	{
  31. 		int newcapacity = ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2;
  32. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
  33. 		//判断扩容是否成功
  34. 		if (tmp == NULL)
  35. 		{
  36. 			printf("realloc fail\n");
  37. 			exit(-1);
  38. 		}
  39. 		ps->a = tmp;
  40. 		ps->capacity = newcapacity;
  41. 	}
  42. 	//插入数据
  43. 	//数组的下标从0开始，top指向的就是栈顶
  44. 	ps->a[ps->top] = x;
  45. 	ps->top++;
  46. }
  47.  
  48. //出栈
  49. void StackPop(Stack* ps)
  50. {
  51. 	assert(ps);
  52. 	//断言栈是否为空
  53. 	assert(ps->top > 0);
  54.  
  55. 	ps->top--;
  56. }
  57.  
  58. //获取栈顶元素
  59. STDataType StackTop(Stack* ps)
  60. {
  61. 	assert(ps);
  62. 	//断言栈是否为空
  63. 	assert(ps->top);
  64.  
  65. 	return ps->a[ps->top-1];
  66. }
  67.  
  68. //检测栈是否为空
  69. bool StackEmpty(Stack* ps)
  70. {
  71. 	assert(ps);
  72. 	非空
  73. 	//if (ps->top > 0)
  74. 	//{
  75. 	//	return false;
  76. 	//}
  77. 	为空
  78. 	//else
  79. 	//	return true;
  80. 	//更优化的写法
  81. 	return ps->top == 0;
  82. }
  83.  
  84. int StackSize(Stack* ps)
  85. {
  86. 	assert(ps);
  87. 	//返回个数，top指的是栈顶数据的下一位。
  88. 	return ps->top;
  89. }
  90.  
  91. typedef struct {
  92.     Stack s1;//储存数据最初始的栈
  93.     Stack s2;//取数据专用的栈
  94.  
  95. } MyQueue;
  96. bool myQueueEmpty(MyQueue* obj);
  97.  
  98. MyQueue* myQueueCreate() {
  99.     //分配空间
  100.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  101.     //初始化
  102.     StackInit(&obj->s1);//放数据
  103.     StackInit(&obj->s2);
  104.     return obj;
  105. }
  106.  
  107. void myQueuePush(MyQueue* obj, int x) {
  108.     //插入数据,s1为储存初始数据的栈
  109.     StackPush(&obj->s1,x);
  110. }
  111.  
  112. int myQueuePop(MyQueue* obj) {
  113.     //如果s2为空
  114.     if(StackEmpty(&obj->s2))
  115.     {
  116.         //导数据
  117.         while(StackSize(&obj->s1))
  118.     {
  119.         int top = StackTop(&obj->s1);
  120.         StackPush(&obj->s2,top);
  121.         StackPop(&obj->s1);
  122.     }
  123.     }
  124.     int top = StackTop(&obj->s2);
  125.     StackPop(&obj->s2);
  126.     return top;
  127. }
  128.  
  129. int myQueuePeek(MyQueue* obj) {
  130.     if(StackEmpty(&obj->s2))
  131.     {
  132.     while(StackSize(&obj->s1))
  133.     {
  134.         int top = StackTop(&obj->s1);
  135.         StackPush(&obj->s2,top);
  136.         StackPop(&obj->s1);
  137.     }
  138.     }
  139.     int top = StackTop(&obj->s2);
  140.     return top;
  141. }
  142.  
  143. bool myQueueEmpty(MyQueue* obj) {
  144.     return StackEmpty(&obj->s2) && StackEmpty(&obj->s1);
  145. }
  146.  
  147. void myQueueFree(MyQueue* obj) {
  148.     StackDestroy(&obj->s1);
  149.     StackDestroy(&obj->s2);
  150.     free(obj);
  151. }

622. 设计循环队列

思路：

创建结构体变量，记录头尾，ｋ，指针数组。

判断为空的条件：当ｈｅａｄ　＝＝　ｔａｉｌ时表示队列为空。

但是队列已满的条件也为ｈｅａｄ　＝＝　ｔａｉｌ。

解决方案：

为空

为了能够使用ｈｅａｄ　＝＝　ｔａｉｌ的判定

条件，一般认为这个情况是满的。

为保证空间一定能存放下ｋ个元素，将数组空间＋１即可满足。

此时判断为空的条件：ｈｅａｄ　＝＝　ｔａｉｌ

　　判断为满的条件：ｈｅａｄ　＝　ｔａｉｌ＋１

注意：多出来的一个空间在数组中时随机的，并不是在数组末尾。

画图：

环形只存5个数据，开辟了6个空间

经过一系列插入，删除操作：

再插入值

此时已经插入了5个值了，队列已经满了，判定条件就成了ｔａｉｌ＋１　＝＝　ｈｅａｄ

这是多次插入和删除情况下的，若是不进行删除操作：

此时就已经满了。判定条件　ｔａｉｌ　＝＝　ｋ

 

代码：

  1. typedef struct {
  2.     //数组，头，尾，k
  3.     int* a;
  4.     int head;
  5.     int tail;
  6.     int k;
  7.  
  8. } MyCircularQueue;
  9. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  10. bool myCircularQueueIsFull(MyCircularQueue* obj);
  11. MyCircularQueue* myCircularQueueCreate(int k) {
  12.     //分配空间
  13.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  14.     //结构体内部的数组也需要开辟空间,为方便找到循环结束条件多开一个单位
  15.     obj->a = (int*)malloc(sizeof(int)*(k+1));
  16.     //初始化
  17.     obj->head = obj->tail = 0;
  18.     obj->k = k;
  19.     return obj;
  20. }
  21.  
  22. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  23.     //判断循环队列是否已满
  24.     if(myCircularQueueIsFull(obj))
  25.     {
  26.         return false;
  27.     }
  28.     else
  29.     {
  30.         obj->a[obj->tail] = value;
  31.         //更新tail
  32.         //如果走到尾的话，就归0
  33.         if(obj->tail == obj->k)
  34.         {
  35.             obj->tail = 0;
  36.         }
  37.         else
  38.             obj->tail++;
  39.     }
  40.     return true;
  41. }
  42.  
  43. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  44.     if(myCircularQueueIsEmpty(obj))
  45.     {
  46.         return false;
  47.     }
  48.     else
  49.     {
  50.         //更新头
  51.         if(obj->head == obj->k)
  52.         {
  53.             obj->head = 0;
  54.         }
  55.         //数据覆盖即可
  56.         else
  57.             obj->head++;
  58.         return true;
  59.     }
  60.     
  61. }
  62.  
  63. int myCircularQueueFront(MyCircularQueue* obj) {
  64.     if(myCircularQueueIsEmpty(obj))
  65.     {
  66.         return -1;
  67.     }
  68.     else
  69.     {
  70.         return obj->a[obj->head];
  71.     }
  72. }
  73.  
  74. int myCircularQueueRear(MyCircularQueue* obj) {
  75.     if(myCircularQueueIsEmpty(obj))
  76.     {
  77.         return -1;
  78.     }
  79.     else
  80.     {
  81.         if(obj->tail == 0)
  82.         {
  83.             return obj->a[obj->k];
  84.         }
  85.         else
  86.             return obj->a[obj->tail-1];
  87.     }
  88.  
  89. }
  90.  
  91. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  92.     return obj->head == obj->tail;
  93.     
  94. }
  95.  
  96. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  97.     if(obj->head==0 && obj->tail == obj->k)
  98.     {
  99.         return true;
  100.     }
  101.     else if(obj->tail+1 == obj->head)
  102.     {
  103.         return true;
  104.     }
  105.     else
  106.         return false;
  107.  
  108. }
  109.  
  110. void myCircularQueueFree(MyCircularQueue* obj) {
  111.     free(obj->a);
  112.     free(obj);
  113. }

相关技术文章

最新源码

下载排行榜
点击QQ咨询
开通会员
返回顶部
×
微信扫码支付 元
微信扫码支付
确定支付下载
请使用微信描二维码支付
×

提示信息

×

选择支付方式

  • 微信支付
  • 支付宝付款
确定支付下载