• C语言描述数据结构 —— 栈和队列OJ题

    1.括号匹配问题

    很显然，本篇文章的标题出卖了这道题，我们将使用栈来解决这道题。对于栈和队列，C 语言的库中并没有这两个数据结构，但在 C++ 的库中是可以直接使用这两种数据结构的。局限于目前我们只会使用 C 语言，所以在解这道题时，需要做一个前置工作，就是将我们写好的栈复制过来。这里我给出了上一篇关于栈和队列实现的代码。

    1. //可以动态开辟空间的栈
    2. typedef char StackData;//注意是字符元素
    3. typedef struct Stack
    4. {
    5. 	StackData* a;
    6. 	int top;//与顺序表的 size 一致
    7. 	int capacity;
    8. }Stack;
    9.  
    10. void StackInit(Stack* ps);//栈初始化
    11. void StackPush(Stack* ps,StackData x);//入栈
    12. void StackPop(Stack* ps);//出栈
    13. StackData StackTop(Stack* ps);//获取栈顶元素
    14. bool StackEmpty(Stack* ps);//判断栈是否为空
    15. int StackSize(Stack* ps);//计算栈元素个数
    16. void StackDestroy(Stack* ps);//栈销毁
    17.  
    18. //初始化栈
    19. void StackInit(Stack* ps)
    20. {
    21. 	assert(ps);
    22. 	//栈的初始容量置空
    23. 	ps->a = NULL;
    24. 	ps->top = ps->capacity = 0;
    25. }
    26. //入栈
    27. void StackPush(Stack* ps,StackData x)
    28. {
    29. 	assert(ps);
    30. 	//入栈只有一种方式，所以不需要将扩容独立封装
    31. 	if (ps->top == ps->capacity)
    32. 	{
    33. 		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    34. 		StackData* tmp = (StackData*)realloc(ps->a, NewCapacity*sizeof(StackData));
    35. 		assert(tmp);
    36. 		ps->a = tmp;
    37. 		ps->capacity = NewCapacity;
    38. 	}
    39. 	ps->a[ps->top] = x;
    40. 	ps->top++;
    41. }
    42. //出栈
    43. void StackPop(Stack* ps)
    44. {
    45. 	assert(ps);
    46. 	assert(!StackEmpty(ps));
    47. 	ps->top--;
    48. }
    49. //获取栈顶元素
    50. StackData StackTop(Stack* ps)
    51. {
    52. 	assert(ps);
    53. 	return ps -> a[ps->top - 1];
    54. }
    55. //判断栈是否为空
    56. bool StackEmpty(Stack* ps)
    57. {
    58. 	assert(ps);
    59. 	return ps->top == 0;//等于 0 则返回true，即栈为空
    60. }
    61. //计算栈中元素个数
    62. int StackSize(Stack* ps)
    63. {
    64. 	assert(ps);
    65. 	return ps->top;
    66. }
    67. //栈销毁
    68. void StackDestroy(Stack* ps)
    69. {
    70. 	assert(ps);
    71. 	free(ps->a);
    72. 	ps->a = NULL;
    73. 	ps->top = ps->capacity = 0;
    74. }

    做好了前置工作之后现在我们就要试着来解题。我们来分析一下思路：

     我们将它们转换为代码：

    1. bool isValid(char * s){
    2.     Stack st;
    3.     StackInit(&st);
    4.     while(*s)
    5.     {
    6.         if(*s == '(' || *s == '[' || *s == '{')
    7.         {
    8.             StackPush(&st,*s);
    9.         }
    10.         else
    11.         {
    12.             //如果没有一个左括号入栈
    13.             if(StackEmpty(&st))
    14.             {
    15.                 StackDestroy(&st);
    16.                 return false;
    17.             }
    18.             else
    19.             {
    20.                 char top = StackTop(&st);
    21.                 StackPop(&st);
    22.                 //如果有任何不满足匹配的情况就返回 false
    23.                 if(*s == ')' && top == '(' ||
    24.                     *s == ']' && top == '[' ||
    25.                     *s == '}' && top == '{')
    26.                     {
    27.                         StackDestroy(&st);
    28.                         return false;
    29.                     }
    30.             }
    31.         }
    32.         s++;
    33.     }
    34.     //如果括号匹配的话，那么栈中就应该没有任何元素
    35.     //这个例子见于字符串中全是左括号，没有满足任何匹配条件，就不会出栈
    36.     //不会出栈就会导致栈中有元素，即不为空
    37.     bool flag = StackEmpty(&st);
    38.     StackDestroy(&st);
    39.     return flag;
    40. }
    41.

    2.用队列实现栈

    注意看题，题目的要求是让我们用两个队列来实现栈。那么现在就要搞清楚队列转化为栈的难点是什么。队列的特征是先进先出，如果我们入队的数据是 1、2、3、4、5 ，那么出队的顺序也是 1、2、3、4、5 。而栈的特征是先进后出，即我们入栈的数据是 1、2、3、4、5，那么出栈的顺序是 5、4、3、2、1 。由此可见入队和入栈的方式一样，差别在于出队和出栈的顺序不同。我们需要解决的便是出的问题，还有就是删除的问题。

    我们知道，我们实现队列的数据结构是链表。题目的要求是让我们使用两个队列，两个队列如何实现获取队尾元素和尾删呢？

    我们拿出我们使用链表实现队列的代码，并将它复制到我们的题目上面去。

    1. //链表的结点
    2. typedef int QueueData;
    3. typedef struct QueueNode
    4. {
    5. 	QueueData val;
    6. 	struct QueueNode* next;
    7. }QueueNode;
    8. //存储头、尾结点地址的指针
    9. typedef struct HeadTail
    10. {
    11. 	QueueNode* head;
    12. 	QueueNode* tail;
    13. 	int size;//记录队列有几个元素
    14. }HeadTail;
    15.  
    16. void QueueInit(HeadTail* p);//初始化队列
    17. void QueuePush(HeadTail* p,QueueData x);//进入队列
    18. QueueData QueueHead(HeadTail* p);//获取队头元素
    19. QueueData QueueTail(HeadTail* p);//获取队尾元素
    20. void QueuePop(HeadTail* p);//删除操作，出队
    21. bool QueueEmpty(HeadTail* p);//检查队列是否为空
    22. int QueueSize(HeadTail* p);//获取队列元素个数
    23. void QueuePopTail(HeadTail* p);
    24. void QueueDestroy(HeadTail* p);//销毁队列
    25.  
    26. //初始化
    27. void QueueInit(HeadTail* p)
    28. {
    29. 	assert(p);
    30. 	p->head = p->tail = NULL;
    31. 	p->size = 0;
    32. }
    33. //队列尾插
    34. void QueuePush(HeadTail* p, QueueData x)
    35. {
    36. 	assert(p);
    37. 	//创建一个新结点
    38. 	QueueNode* newnode = (QueueNode*)calloc(1, sizeof(QueueNode));
    39. 	assert(newnode);
    40. 	newnode->val = x;
    41. 	newnode->next = NULL;
    42. 	//如果链表内没有结点，头尾指针指向同一个结点
    43. 	if (p->head == NULL)
    44. 	{
    45. 		p->head = newnode;
    46. 		p->tail = newnode;
    47. 	}
    48. 	//否则尾指针需要变化
    49. 	else
    50. 	{
    51. 		p->tail->next = newnode;
    52. 		p->tail = newnode;
    53. 	}
    54. 	p->size++;
    55. }
    56. //获取队头元素
    57. QueueData QueueHead(HeadTail* p)
    58. {
    59. 	assert(p);
    60. 	assert(!QueueEmpty(p));
    61. 	return p->head->val;
    62. }
    63. //获取队尾元素
    64. QueueData QueueTail(HeadTail* p)
    65. {
    66. 	assert(p);
    67. 	assert(!QueueEmpty(p));
    68. 	return p->tail->val;
    69. }
    70. //删除、出队
    71. void QueuePop(HeadTail* p)
    72. {
    73. 	assert(p);
    74. 	assert(!QueueEmpty(p));
    75. 	//如果链表只有一个结点
    76. 	if (p->head == p->tail)
    77. 	{
    78. 		free(p->head);
    79. 		p->head = p->tail = NULL;
    80. 	}
    81. 	//否则进行头删
    82. 	else
    83. 	{
    84. 		QueueNode* cur = p->head;
    85. 		p->head = p->head->next;
    86. 		free(cur);
    87. 		cur = NULL;
    88. 	}
    89. 	p->size--;
    90. }
    91. //检测队列是否为空
    92. bool QueueEmpty(HeadTail* p)
    93. {
    94. 	assert(p);
    95. 	return p->head == NULL && p->tail == NULL;
    96. }
    97. //获取队列元素个数
    98. int QueueSize(HeadTail* p)
    99. {
    100. 	assert(p);
    101. 	return p->size;
    102. }
    103. //销毁队列
    104. void QueueDestroy(HeadTail* p)
    105. {
    106. 	assert(p);
    107. 	QueueNode* cur = p->head;
    108. 	while (cur)
    109. 	{
    110. 		QueueNode* del = cur;
    111. 		cur = cur->next;
    112. 		free(del);
    113. 	}
    114. }
    115.  
    1. typedef struct {
    2.     HeadTail q1;
    3.     HeadTail q2;
    4. } MyStack;
    5.  
    6.  
    7. MyStack* myStackCreate() {
    8.     MyStack* obj = (MyStack*)calloc(1,sizeof(MyStack));
    9.     //取 q1、q2 的地址传入函数
    10.     QueueInit(&obj->q1);
    11.     QueueInit(&obj->q2);
    12.     return obj;
    13. }
    14.  
    15. void myStackPush(MyStack* obj, int x) {
    16.     //一定是向非空的队列插入数据
    17.     if(!QueueEmpty(&obj->q1))
    18.     {
    19.         QueuePush(&obj->q1,x);
    20.     }
    21.     else
    22.     {
    23.         QueuePush(&obj->q2,x);
    24.     }
    25. }
    26.  
    27. int myStackPop(MyStack* obj) {
    28.     //如果q1为空，将q2的size-1个倒入q1
    29.     //并将q2剩下的最后一个当成栈顶元素返回
    30.     if(QueueEmpty(&obj->q1))
    31.     {
    32.         while(QueueSize(&obj->q2) > 1)
    33.         {
    34.             QueuePush(&obj->q1,QueueHead(&obj->q2));
    35.             QueuePop(&obj->q2);
    36.         }
    37.         int ret = QueueTail(&obj->q2);
    38.         QueuePop(&obj->q2);
    39.         return ret;
    40.     }
    41.     //如果q2为空，将q1的size-1个倒入q2
    42.     //并将q1剩下的最后一个当成栈顶元素返回
    43.     else
    44.     {
    45.          while(QueueSize(&obj->q1) > 1)
    46.         {
    47.             QueuePush(&obj->q2,QueueHead(&obj->q1));
    48.             QueuePop(&obj->q1);
    49.         }
    50.         int ret = QueueTail(&obj->q1);
    51.         QueuePop(&obj->q1);
    52.         return ret;
    53.     }
    54.  
    55. }
    56.  
    57. int myStackTop(MyStack* obj) {
    58.     //这个函数并没有要求要删除数据
    59.     //所以直接返回非空队列的队尾元素
    60.     if(!QueueEmpty(&obj->q1))
    61.     {
    62.         return QueueTail(&obj->q1);
    63.     }
    64.     else
    65.     {
    66.         return QueueTail(&obj->q2);
    67.     }
    68. }
    69.  
    70. bool myStackEmpty(MyStack* obj) {
    71.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    72. }
    73.  
    74. void myStackFree(MyStack* obj) {
    75.     //obj里面存放的只是q1、q2空间的地址
    76.     //所以需要独立释放q1、q2空间
    77.     QueueDestroy(&obj->q1);
    78.     QueueDestroy(&obj->q2);
    79.     free(obj);
    80. }

    3.用栈实现队列

    这里的题目要求是用两个栈实现队列，那么肯定是要涉及倒数据的。我们现在来具体分析如何倒数据。

     我们将我们实现栈的数据结构的代码复制到题目中去：

    1. //可以动态开辟空间的栈
    2. typedef int StackData;
    3. typedef struct Stack
    4. {
    5. 	StackData* a;
    6. 	int top;//与顺序表的 size 一致
    7. 	int capacity;
    8. }Stack;
    9.  
    10. void StackInit(Stack* ps);//栈初始化
    11. void StackPush(Stack* ps,StackData x);//入栈
    12. void StackPop(Stack* ps);//出栈
    13. StackData StackTop(Stack* ps);//获取栈顶元素
    14. bool StackEmpty(Stack* ps);//判断栈是否为空
    15. int StackSize(Stack* ps);//计算栈元素个数
    16. void StackDestroy(Stack* ps);//栈销毁
    17.  
    18. //初始化栈
    19. void StackInit(Stack* ps)
    20. {
    21. 	assert(ps);
    22. 	//栈的初始容量置空
    23. 	ps->a = NULL;
    24. 	ps->top = ps->capacity = 0;
    25. }
    26. //入栈
    27. void StackPush(Stack* ps,StackData x)
    28. {
    29. 	assert(ps);
    30. 	//入栈只有一种方式，所以不需要将扩容独立封装
    31. 	if (ps->top == ps->capacity)
    32. 	{
    33. 		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    34. 		StackData* tmp = (StackData*)realloc(ps->a, NewCapacity*sizeof(StackData));
    35. 		assert(tmp);
    36. 		ps->a = tmp;
    37. 		ps->capacity = NewCapacity;
    38. 	}
    39. 	ps->a[ps->top] = x;
    40. 	ps->top++;
    41. }
    42. //出栈
    43. void StackPop(Stack* ps)
    44. {
    45. 	assert(ps);
    46. 	assert(!StackEmpty(ps));
    47. 	ps->top--;
    48. }
    49. //获取栈顶元素
    50. StackData StackTop(Stack* ps)
    51. {
    52. 	assert(ps);
    53. 	return ps -> a[ps->top - 1];
    54. }
    55. //判断栈是否为空
    56. bool StackEmpty(Stack* ps)
    57. {
    58. 	assert(ps);
    59. 	return ps->top == 0;//等于 0 则返回true，即栈为空
    60. }
    61. //计算栈中元素个数
    62. int StackSize(Stack* ps)
    63. {
    64. 	assert(ps);
    65. 	return ps->top;
    66. }
    67. //栈销毁
    68. void StackDestroy(Stack* ps)
    69. {
    70. 	assert(ps);
    71. 	free(ps->a);
    72. 	ps->a = NULL;
    73. 	ps->top = ps->capacity = 0;
    74. }
    1. typedef struct {
    2.     Stack push;
    3.     Stack pop;
    4. } MyQueue;
    5.  
    6.  
    7. MyQueue* myQueueCreate() {
    8.     MyQueue* obj = (MyQueue*)calloc(1,sizeof(MyQueue));
    9.     StackInit(&obj->push);
    10.     StackInit(&obj->pop);
    11.     return obj;
    12. }
    13.  
    14. void myQueuePush(MyQueue* obj, int x) {
    15.     //只向push栈插入数据
    16.     StackPush(&obj->push,x);
    17. }
    18.  
    19. int myQueuePop(MyQueue* obj) {
    20.     //要向pop栈中倒入数据
    21.     if(StackEmpty(&obj->pop))
    22.     {
    23.         while(!StackEmpty(&obj->push))
    24.         {
    25.             StackPush(&obj->pop,StackTop(&obj->push));
    26.             StackPop(&obj->push);
    27.         }
    28.     }
    29.     int ret = StackTop(&obj->pop);
    30.     StackPop(&obj->pop);
    31.     return ret;
    32. }
    33.  
    34. int myQueuePeek(MyQueue* obj) {
    35.     //只有向pop栈倒入数据才能取到最先进去的那个元素
    36.     if(StackEmpty(&obj->pop))
    37.     {
    38.         while(!StackEmpty(&obj->push))
    39.         {
    40.             StackPush(&obj->pop,StackTop(&obj->push));
    41.             StackPop(&obj->push);
    42.         }
    43.     }
    44.     return StackTop(&obj->pop);
    45. }
    46.  
    47. bool myQueueEmpty(MyQueue* obj) {
    48.     return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
    49. }
    50.  
    51. void myQueueFree(MyQueue* obj) {
    52.     StackDestroy(&obj->push);
    53.     StackDestroy(&obj->pop);
    54.     free(obj);
    55. }

    4.设计循环队列

     我们先不关注题目的要求，就单单循环队列而言，我们先选择合适的数据结构。

    我们有两种数据结构可选，一是链表，而是顺序表。那么那种数据结构优势较大呢？首先我们来看看循环队列是什么。

    那么其次，我们把这个逻辑结构套到两种数据结构上面去。

     

     有了上面的分析基础，现在就可以尝试去解题了。

    1. typedef struct {
    2.     int* a;
    3.     int head;//头
    4.     int tail;//尾
    5.     int size;//长度
    6. } MyCircularQueue;
    7.  
    8.  
    9. MyCircularQueue* myCircularQueueCreate(int k) {
    10.     MyCircularQueue* obj = (MyCircularQueue*)calloc(1,sizeof(MyCircularQueue));
    11.     obj->a = (int*)calloc(1,sizeof(int)*(k+1));//顺序表的空间多开一个
    12.     obj->head = obj->tail = 0;
    13.     obj->size=k+1;
    14.     return obj;
    15. }
    16.  
    17. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    18.     return obj->head == obj->tail;
    19. }
    20.  
    21. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    22.     return (obj->tail+1)%obj->size == obj->head;
    23. }
    24.  
    25. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    26.     if(myCircularQueueIsFull(obj))
    27.         return false;
    28.     obj->a[obj->tail]=value;
    29.     obj->tail++;
    30.     obj->tail %= obj->size;//确保tail的值不会超过长度范围
    31.     return true;
    32. }
    33.  
    34. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    35.     if(myCircularQueueIsEmpty(obj))
    36.         return false;
    37.     obj->head++;
    38.     obj->head %= obj->size;//确保head的值不会超过长度范围
    39.     return true;
    40. }
    41.  
    42. int myCircularQueueFront(MyCircularQueue* obj) {
    43.     if(myCircularQueueIsEmpty(obj))
    44.         return -1;
    45.     return  obj->a[obj->head];
    46. }
    47.  
    48. int myCircularQueueRear(MyCircularQueue* obj) {
    49.     if(myCircularQueueIsEmpty(obj))
    50.         return -1;
    51.         //推导的公式，以防tail的值为 0 
    52.     return obj->a[(obj->tail-1+obj->size)%obj->size];
    53. }
    54.  
    55.  
    56.  
    57. void myCircularQueueFree(MyCircularQueue* obj) {
    58.     free(obj->a);
    59.     free(obj);
    60. }

  • 相关阅读:
    AVL树 c语言版本 插入部分
    CentOS部署MySQL 5.7（详细）
    MKL稀疏矩阵运算示例及函数封装
    『现学现忘』Docker相关概念 — 6、虚拟化技术分类
    l8-d7 实现TCP通信
    机器学习笔记：seq2seq & attentioned seq2seq
    Linux下NFS共享存储安装详细步骤
    软件工程国考总结——选择题
    java 阿里云上传照片
    单点登录的三种方式
  • 原文地址：https://blog.csdn.net/weixin_59913110/article/details/126383545