• 数据结构-栈和队列力扣题

    目录

    有效的括号

    用队列实现栈

     用栈实现队列

     设计循环队列

    有效的括号

    题目链接：力扣（LeetCode）

    思路： 这道题可以用栈来解决，先让字符串中的左括号' ( '，' [ '，' { '入栈，s指向字符串下一个字符，如果该字符也是左括号，那就继续入栈，如果是右括号，那就让其与栈顶元素相匹配（每次都要弹出栈顶元素），匹配上了，继续循环，匹配不上就返回false，注意在每次返回false之前都要销毁栈。

    还要考虑极端情况，如果全是左括号，我们要在代码最后进行判空，不为空，返回false，同时，这次判空也能解决前面几对都匹配上，只有最后一个左括号没匹配上的问题（例如："()[]{}{"）。

    如果全是右括号，说明整个过程中没有入栈元素，此时判空，如果为空返回false，同时，这次判空也能解决前面几对都匹配上，只有最后一个右括号没匹配上的问题（例如："()[]{}}"）。

    如果用C语言来解题的话，栈需要自己写。

    代码如下：

    1. typedef int STDatatype;
    2. typedef struct Stack
    3. {
    4. 	STDatatype* a;
    5. 	int top;
    6. 	int capacity;
    7. }ST;
    8.  
    9. //初始化栈
    10. void STInit(ST* pst)
    11. {
    12. 	assert(pst);
    13. 	pst->a = NULL;
    14. 	pst->top = 0;
    15. 	pst->capacity = 0;
    16. }
    17.  
    18. //入栈
    19. void STPush(ST* pst, STDatatype x)
    20. {
    21. 	//开辟空间
    22. 	if (pst->top == pst->capacity)
    23. 	{
    24. 		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    25. 		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
    26. 		if (tmp == NULL)
    27. 		{
    28. 			perror("realloc fail");
    29. 			return;
    30. 		}
    31. 		pst->a = tmp;
    32. 		pst->capacity = newcapacity;
    33. 	}
    34. 	//插入
    35. 	pst->a[pst->top] = x;
    36. 	pst->top++;
    37. }
    38. //判空函数
    39. bool STEmpty(ST* pst)
    40. {
    41. 	assert(pst);
    42. 	return pst->top == 0;
    43. }
    44. //出栈
    45. void STPop(ST* pst)
    46. {
    47. 	assert(pst);
    48. 	assert(!STEmpty(pst));
    49. 	pst->top--;
    50. }
    51. //获取栈顶元素
    52. STDatatype STTop(ST* pst)
    53. {
    54. 	assert(pst);
    55. 	assert(!STEmpty(pst));
    56. 	return pst->a[pst->top - 1];
    57. }
    58. //获取栈中有效数据的个数
    59. int STSize(ST* pst)
    60. {
    61. 	assert(pst);
    62. 	return pst->top;
    63. }
    64. //销毁栈
    65. void STDestory(ST* pst)
    66. {
    67. 	assert(pst);
    68. 	free(pst->a);
    69. 	pst->a = NULL;
    70. 	pst->top = pst->capacity = 0;
    71. }
    72.  
    73.  
    74. bool isValid(char* s) {
    75.     ST st;
    76.     STInit(&st);
    77.     while(*s)
    78.     {
    79.  
    80.         if(*s=='('||*s=='['||*s=='{')
    81.         {
    82.             STPush(&st,*s);
    83.         }
    84.  
    85.         else
    86.         {
    87.  
    88.             if(STEmpty(&st))
    89. 			{
    90. 			   STDestory(&st);
    91.                return false;
    92. 			}
    93.  
    94.  
    95. 			char top=STTop(&st);
    96. 			STPop(&st);
    97. 						
    98.             if((top!='('&&*s==')')
    99.               ||(top!='['&&*s==']')
    100.               ||(top!='{'&&*s=='}'))
    101.             {
    102.  
    103.                 STDestory(&st);
    104.                 return false;
    105.             
    106.             }
    107.         }
    108. 				 ++s;
    109.     }
    110.  
    111. 	bool ret=STEmpty(&st);
    112. 	STDestory(&st);
    113.     return ret;
    114. }

    用队列实现栈

    题目链接：力扣（LeetCode）

     思路：队列是先入先出，栈是先入后出，要用队列实现栈，我们可以定义两个栈q1和q2，当它们都为空时，随便选一个存入数据，假设q1中有数据1 2 3 4，我们可以把q1中的1 2 3 push进q2中，然后把q1中的4 pop出去，接着把q2中的1 2 push进q1，然后把q2中的3 pop出去，这样循环在q1和q2中倒数据，就实现了4 3 2 1依次出栈，即先入后出。

    当我们在出栈的同时，想要入栈，就把数据push进有数据的队列即可。

    想要用C语言做这道题，队列的实现代码也要自己写。

    注意，我们下列代码是结构体的三层嵌套，所以销毁时要先销毁q1和q2，再销毁obj，如果只销毁obj，由于我们的队列q1和q2中分别有两个头尾指针还有节点，会造成内存泄漏的问题。

    它们的关系图如下：

    代码如下：

    1. typedef int QDatatype;
    2. typedef struct QueueNode
    3. {
    4. 	struct QueueNode* next;
    5. 	QDatatype data;
    6. }QNode;
    7.  
    8. typedef struct Queue
    9. {
    10. 	QNode* phead;
    11. 	QNode* ptail;
    12. 	int size;
    13. }Queue;
    14.  
    15. //初始化队列
    16. void QueueInit(Queue* pq)
    17. {
    18. 	pq->phead = NULL;
    19. 	pq->ptail = NULL;
    20. 	pq->size = 0;
    21. }
    22.  
    23. //队尾入队列
    24. void QueuePush(Queue* pq, QDatatype x)
    25. {
    26. 	assert(pq);
    27. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    28. 	if (newnode == NULL)
    29. 	{
    30. 		perror("malloc fail");
    31. 		return;
    32. 	}
    33. 	newnode->data = x;
    34. 	newnode->next = NULL;
    35.  
    36. 	if (pq->ptail == NULL)
    37. 	{
    38. 		assert(pq->phead == NULL);
    39. 		pq->phead = pq->ptail=newnode;
    40. 	}
    41. 	else
    42. 	{
    43. 		pq->ptail->next = newnode;
    44. 		pq->ptail = newnode;
    45. 	}
    46. 	pq->size++;
    47. }
    48.  
    49. //判空函数
    50. bool QueueEmpty(Queue* pq)
    51. {
    52. 	assert(pq);
    53. 	return pq->size ==0 ;
    54. }
    55.  
    56. //队头出队列
    57. void QueuePop(Queue* pq)
    58. {
    59. 	assert(pq);
    60. 	assert(!QueueEmpty(pq));
    61. 	//一个节点
    62. 	//多个节点
    63. 	if (pq->phead->next == NULL)
    64. 	{
    65. 		free(pq->phead);
    66. 		pq->phead = pq->ptail= NULL;
    67. 	}
    68. 	else
    69. 	{
    70. 		QNode* next = pq->phead->next;
    71. 		free(pq->phead);
    72. 		pq->phead = next;
    73. 	}
    74. 	pq->size--;
    75. }
    76.  
    77. //获取队列头部元素
    78. QDatatype QueueFront(Queue* pq)
    79. {
    80. 	assert(pq);
    81. 	assert(!QueueEmpty(pq));
    82. 	return pq->phead->data;
    83. }
    84.  
    85. //获取队列尾部元素
    86. QDatatype QueueBack(Queue* pq)
    87. {
    88. 	assert(pq);
    89. 	assert(!QueueEmpty(pq));
    90. 	return pq->ptail->data;
    91. }
    92.  
    93. //获取队列中有效元素个数
    94. int Queuesize(Queue* pq)
    95. {
    96. 	assert(pq);
    97. 	return pq->size;
    98. }
    99.  
    100. //销毁队列
    101. void DestoryQueue(Queue* pq)
    102. {
    103. 	assert(pq);
    104. 	while (pq->phead)
    105. 	{
    106. 		QNode* next = pq->phead->next;
    107. 		free(pq->phead);
    108. 		pq->phead = next;
    109. 	}
    110. 	pq->phead = pq->ptail = NULL;
    111. 	pq->size = 0;
    112. }
    113.  
    114.  
    115. typedef struct {
    116.     Queue q1;
    117.     Queue q2;
    118. } MyStack;
    119.  
    120.  
    121. MyStack* myStackCreate() {
    122.  
    123.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    124.  
    125.     if(obj==NULL)
    126.     {
    127.         perror("malloc fail");
    128.         return NULL;
    129.     }
    130.  
    131.     QueueInit(&obj->q1);
    132.     QueueInit(&obj->q2);
    133.     return obj;
    134.  
    135. }
    136.  
    137. void myStackPush(MyStack* obj, int x) {
    138.  
    139.     if(!QueueEmpty(&obj->q1))
    140.     {
    141.         QueuePush(&obj->q1,x);
    142.     }
    143.     else
    144.     {
    145.         QueuePush(&obj->q2,x);
    146.     }
    147. }
    148.  
    149. int myStackPop(MyStack* obj) {
    150.  
    151.     Queue* pemptyq=&obj->q1;
    152.     Queue* pnoemptyq=&obj->q2;
    153.  
    154.     if(!QueueEmpty(&obj->q1))
    155.     {
    156.         pemptyq=&obj->q2;
    157.         pnoemptyq=&obj->q1;
    158.     }
    159.  
    160.     while(Queuesize(pnoemptyq)>1)
    161.     {
    162.         QueuePush(pemptyq,QueueFront(pnoemptyq));
    163. 		QueuePop(pnoemptyq);
    164.     }
    165.  
    166.     int top=QueueFront(pnoemptyq);
    167.     QueuePop(pnoemptyq);
    168.     return top;
    169.  
    170. }
    171.  
    172. int myStackTop(MyStack* obj) {
    173.  
    174.     if(!QueueEmpty(&obj->q1))
    175.         return QueueBack(&obj->q1);
    176. 	else
    177. 		return QueueBack(&obj->q2);
    178.  
    179. }
    180.  
    181. bool myStackEmpty(MyStack* obj) {
    182.  
    183.     assert(obj);
    184.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    185.  
    186. }
    187.  
    188. void myStackFree(MyStack* obj) {
    189.  
    190.    	DestoryQueue(&obj->q1);
    191. 	DestoryQueue(&obj->q2);
    192.     free(obj);
    193. }

     用栈实现队列

    题目链接：力扣（LeetCode）

    思路：这道题用上道题的思路也能实现，但是过于复杂。

    简单思路：我们定义两个栈pushst和popst，栈中数据遵循先入后出的原则，如果在pushst中push进去1 2 3 4，那他从栈顶到栈底依次是 4 3 2 1 ，但是如果我们把pushst中的数据再push进popst中，那popst中从栈顶到栈底依次是 1 2 3 4，此时我们只要将popst中的数据按照栈本身先入后出的原则pop出去，就是1 2 3 4，这样就实现了先入先出。如下图：

    当我们在出队列的同时，想要入队列，要先等popst中的数据出完才行，所以当popst为空，pushst不为空时，才能把pushst中的数据往popst中push。

    代码如下：

    1. typedef int STDatatype;
    2. typedef struct Stack
    3. {
    4. 	STDatatype* a;
    5. 	int top;
    6. 	int capacity;
    7. }ST;
    8.  
    9. //初始化栈
    10. void STInit(ST* pst)
    11. {
    12. 	assert(pst);
    13. 	pst->a = NULL;
    14. 	pst->top = 0;
    15. 	pst->capacity = 0;
    16. }
    17.  
    18. //入栈
    19. void STPush(ST* pst, STDatatype x)
    20. {
    21. 	//开辟空间
    22. 	if (pst->top == pst->capacity)
    23. 	{
    24. 		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    25. 		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
    26. 		if (tmp == NULL)
    27. 		{
    28. 			perror("realloc fail");
    29. 			return;
    30. 		}
    31. 		pst->a = tmp;
    32. 		pst->capacity = newcapacity;
    33. 	}
    34. 	//插入
    35. 	pst->a[pst->top] = x;
    36. 	pst->top++;
    37. }
    38. //判空函数
    39. bool STEmpty(ST* pst)
    40. {
    41. 	assert(pst);
    42. 	return pst->top == 0;
    43. }
    44. //出栈
    45. void STPop(ST* pst)
    46. {
    47. 	assert(pst);
    48. 	assert(!STEmpty(pst));
    49. 	pst->top--;
    50. }
    51. //获取栈顶元素
    52. STDatatype STTop(ST* pst)
    53. {
    54. 	assert(pst);
    55. 	assert(!STEmpty(pst));
    56. 	return pst->a[pst->top - 1];
    57. }
    58. //获取栈中有效数据的个数
    59. int STSize(ST* pst)
    60. {
    61. 	assert(pst);
    62. 	return pst->top;
    63. }
    64. //销毁栈
    65. void STDestory(ST* pst)
    66. {
    67. 	assert(pst);
    68. 	free(pst->a);
    69. 	pst->a = NULL;
    70. 	pst->top = pst->capacity = 0;
    71. }
    72. typedef struct {
    73.     ST pushst;
    74.     ST popst;
    75. } MyQueue;
    76.  
    77.  
    78. MyQueue* myQueueCreate() {
    79.     MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    80.     if(obj==NULL)
    81.     {
    82.         perror("malloc fail\n");
    83.         return NULL;
    84.     }
    85.     STInit(&obj->pushst);
    86.     STInit(&obj->popst);
    87.     return obj;
    88. }
    89.  
    90. void myQueuePush(MyQueue* obj, int x) {
    91.         STPush(&obj->pushst,x);
    92. }
    93.  
    94. int myQueuePop(MyQueue* obj) {
    95.    int front= myQueuePeek(obj);
    96.    STPop(&obj->popst);
    97.    return front;
    98. }
    99.  
    100. int myQueuePeek(MyQueue* obj) {
    101.     if(STEmpty(&obj->popst))
    102.     {
    103.         while(!STEmpty(&obj->pushst))
    104.         {
    105.         STPush(&obj->popst,STTop(&obj->pushst));
    106.         STPop(&obj->pushst);
    107.         }
    108.     }
    109.     return STTop(&obj->popst);
    110. }
    111.  
    112. bool myQueueEmpty(MyQueue* obj) {
    113.     assert(obj);
    114.     return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
    115. }
    116.  
    117. void myQueueFree(MyQueue* obj) {
    118.     STDestory(&obj->pushst);
    119.     STDestory(&obj->popst);
    120.     free(obj);
    121. }

     设计循环队列

    题目链接：力扣（LeetCode）

    思路： 本题用数组队列和链表队列都能实现，在这里我们使用数组队列，首先，要设计一个循环队列，我们就要知道队列什么时候满，什么时候空，空很容易判断，当front=rear时就为空，问题是当我们循环一圈以后，队列已经满了，但此时front也等于rear，所以为了不发生混淆，我们在开辟空间时多开辟一块，假设要存7个数据就开辟8个空间：

    此时当rear+1==front时就为满。但这只是上图为了形象展示，实际上在数组中，每存一个数，rear++，但是数组首尾并没有相连，不能用rear+1==front判断是否满了，我们可以用下标rear，当(rear+1)%(k+1)==front时就说明队列满了。

    而要在队列中插入数据，每次插入之后下标rear++，但是当队列满了之后，rear就是数组中最后一个下标，这时如果我们在队头出了两个数据，想再往队列里插数据，就要让rear回到开始的位置，所以每次rear++后，让rear=rear%(k+1)，此时再插入，就形成了一个完美的循环，同理，删除数据也一样，每次删完都让front=front%(k+1)。

    obj->a[(obj->rear+obj->k)%(obj->k+1)]这段代码是为了返回队尾元素。

    代码如下：

    1. typedef struct {
    2.     int front;
    3.     int rear;
    4.     int k;
    5.     int*a;
    6. } MyCircularQueue;
    7.  
    8.  
    9. MyCircularQueue* myCircularQueueCreate(int k) {
    10.     MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    11.     obj->a=(int*)malloc(sizeof(int)*(k+1));
    12.     obj->front=obj->rear=0;
    13.     obj->k=k;
    14.     return obj;
    15. }
    16.  
    17. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    18.  
    19.     return obj->front==obj->rear;
    20. }
    21.  
    22. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    23.     return (obj->rear+1)%(obj->k+1)==obj->front;
    24. }
    25. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    26.     if( myCircularQueueIsFull(obj))
    27.     return false;
    28.     obj->a[obj->rear]=value;
    29.     obj->rear++;
    30.     obj->rear=(obj->rear)%(obj->k+1);
    31.     return true;
    32. }
    33.  
    34. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    35.     if(myCircularQueueIsEmpty(obj))
    36.     return false;
    37.     obj->front++;
    38.     obj->front=(obj->front)%(obj->k+1);
    39.     return true;
    40. }
    41.  
    42. int myCircularQueueFront(MyCircularQueue* obj) {
    43.     if(myCircularQueueIsEmpty(obj))
    44.     return -1;
    45.     else
    46.     return obj->a[obj->front];
    47. }
    48.  
    49. int myCircularQueueRear(MyCircularQueue* obj) {
    50.     if(myCircularQueueIsEmpty(obj))
    51.     return -1;
    52.     else
    53.     return obj->a[(obj->rear+obj->k)%(obj->k+1)];
    54. }
    55.  
    56. void myCircularQueueFree(MyCircularQueue* obj) {
    57.     free(obj->a);
    58.     free(obj);
    59. }

    栈与队列的内容到这里就结束了，下节开始学习堆与二叉树，

    未完待续。。。 

  • 相关阅读:
    【数据结构初阶】四、线性表里的链表（带头+双向+循环 链表）
    Android Qcom Sensor架构学习
    golang 基础-golang里面的读写锁实现与核心原理分析
    RK3588 linux内核中断之下半部 tasklet（三）
    Ubuntu 软件安装方法（入门必看）
    学习笔记-数据结构-树与二叉树（2024-04-23）
    Pytest系列-数据驱动@pytest.mark.parametrize（7）
    [SpringBoot] AOP-AspectJ 切面技术
    [Java面试]Spring总结以及在面试中的一些问题.
    【ROS2要素】xml、GDF、URDF的关系
  • 原文地址：https://blog.csdn.net/syh163/article/details/134307083