• LeetCode 热题100——栈与队列专题（三）

    一、有效的括号

    20.有效的括号（题目链接）

    思路：

    1）括号的顺序匹配：用栈实现，遇到左括号入，遇到右括号出（保证所出的左括号与右括号对应），否则顺序不匹配。

    2）括号的数量匹配：

    1>左括号大于右括号：用栈实现，遇到左括号入，遇到右括号出，遍历完字符数组，此时栈不为空，则说明左括号数量大于右括号；

    2>右括号大于左括号：遇到右括号出时，判断栈是否为空，若此时栈为空，说明右括号数量大于左括号；

    1. typedef char  SDateType;
    2. typedef struct Stack
    3. {
    4. 	SDateType* a;
    5. 	int top;
    6. 	int capacity;
    7.  
    8. }Stack;
    9. //初始化栈和销毁栈
    10. void InitStack(Stack* ps)
    11. {
    12. 	assert(ps);
    13. 	ps->a = NULL;
    14. 	ps->capacity = ps->top = 0;
    15. }
    16. void DestoryStack(Stack* ps)
    17. {
    18. 	assert(ps);
    19. 	free(ps->a);
    20. 	ps->a = NULL;
    21. 	ps->capacity = ps->top = 0;
    22.  
    23. }
    24.  
    25. //出栈和入栈
    26. void StackPush(Stack* ps, SDateType x)
    27. {
    28. 	assert(ps);
    29. 	//扩容
    30. 	if (ps->top == ps->capacity)
    31. 	{
    32. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    33. 		SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
    34. 		if (tmp == NULL)
    35. 		{
    36. 			perror("realloc fail:");
    37. 			return;
    38. 		}
    39. 		ps->a = tmp;
    40. 		ps->capacity = newcapacity;
    41.  
    42. 	}
    43. 	//尾插
    44. 	ps->a[ps->top] = x;
    45. 	ps->top++;
    46. }
    47. void StackPop(Stack* ps)
    48. {
    49. 	assert(ps);
    50. 	assert(ps->top > 0);//只少有一个元素，才能删除
    51. 	ps->top--;
    52. }
    53.  
    54. //栈的有效个数和栈顶元素
    55. int  StackSize(Stack* ps)
    56. {
    57. 	assert(ps);
    58. 	return ps->top;
    59. }
    60. int   StackTop(Stack* ps)
    61. {
    62. 	assert(ps);
    63. 	assert(ps->top > 0);
    64. 	return ps->a[ps->top - 1];
    65. }
    66.  
    67. //栈是否为空
    68. bool StackEmpty(Stack* ps)
    69. {
    70. 	assert(ps);
    71. 	return ps->top == 0;
    72. }
    73. int isValid(char* s) {
    74. 	Stack ps;
    75. 	InitStack(&ps);
    76.  
    77. 	while (*s)
    78. 	{
    79. 		if (*s == '[' || *s == '(' || *s == '{')
    80. 		{
    81. 			StackPush(&ps, *s);
    82. 			s++;
    83. 		}
    84. 		else
    85.  
    86. 		{
    87. 			if (StackEmpty(&ps))
    88. 			{
    89. 				return false;
    90. 			}
    91. 			char tmp = StackTop(&ps);
    92. 			StackPop(&ps);
    93. 			if ((*s == ']' && tmp != '[') ||
    94. 				(*s == '}' && tmp != '{') ||
    95. 				(*s == ')' && tmp != '('))
    96. 			{
    97. 				return false;
    98. 			}
    99.  
    100. 			s++;
    101.  
    102. 		}
    103. 	}
    104. 	if (!StackEmpty(&ps))
    105. 	{
    106. 		return false;
    107. 	}
    108. 	else {
    109. 		return true;
    110. 	}
    111. 	DestoryStack(&ps);
    112. }

    二、用队列实现栈 

    225. 用队列复制栈（题目链接）

     

    思路： 栈是后进先出，队列是先进先出。

    用俩队列实现栈

    1）入栈时，选择有数据的队列入数据；

    2）出栈时，将有数据队列中前k-1个数据出队列，并入到空队列中，返回并出有数据队列的最后一个数据

    1. typedef int QDateType;
    2. typedef struct QueueNode
    3. {
    4. 	QDateType val;
    5. 	struct QueueNode * next;
    6. }QueueNode;
    7. typedef struct Queue
    8. {
    9. 	QueueNode *head;
    10. 	QueueNode *tail;
    11. 	QDateType size;
    12. }Queue;
    13.  
    14. // 初始化队列
    15. void QueueInit(Queue* pq)
    16. {
    17. 	assert(pq);
    18. 	pq->head = pq->tail = NULL;
    19. 	pq->size = 0;
    20. }
    21.  
    22. void QueuePush(Queue* pq, QDateType x)
    23. {
    24. 	assert(pq);
    25. 	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    26. 	
    27. 	node->val = x;
    28. 	node->next = NULL;
    29. 	if (pq->tail == NULL)
    30. 	{
    31. 		pq->head = pq->tail = node;
    32. 		pq->size++;
    33. 	}
    34. 	else
    35. 	{
    36. 		pq->tail->next = node;
    37. 		pq->tail = node;
    38. 		pq->size++;
    39. 	}
    40. }
    41. void QueuePop(Queue* pq)
    42. {
    43. 	assert(pq);
    44. 	assert(pq->head != NULL);//只少保证一个节点
    45. 	QueueNode* del = pq->head;
    46. 	pq->head = pq->head->next;
    47. 	free(del);
    48. 	del = NULL;
    49. 	pq->size--;
    50. 	if (pq->head == NULL)//只有一个节点处理
    51. 	{
    52. 		pq->tail = NULL;
    53. 	}
    54. }
    55.  
    56. // 返回队头和队尾
    57. QDateType QueueFront(Queue* pq)
    58. {
    59. 	assert(pq);
    60. 	return pq->head->val;
    61. }
    62. QDateType QueueBack(Queue* pq)
    63. {
    64. 	assert(pq);
    65. 	return pq->tail->val;
    66. }
    67.  
    68. // 获取队列中有效元素个数
    69. int QueueSize(Queue* pq)
    70. {
    71. 	assert(pq);
    72. 	return pq->size;
    73. }
    74.  
    75.  
    76.  
    77. bool QueueEmpty(Queue* pq)
    78. {
    79. 	assert(pq);
    80. 	return pq->head==NULL;
    81. }
    82.  
    83. void QueueDestroy(Queue* pq)
    84. {
    85. 	assert(pq);
    86. 	QueueNode* cur = pq->head;
    87. 	while (cur)
    88. 	{
    89. 		QueueNode* next = cur->next;
    90. 		free(cur);
    91. 		cur = next;
    92. 	}
    93. 	pq->head = pq->tail = NULL;
    94. 	pq->size = 0;
    95.  
    96. }
    97. typedef struct {
    98.     Queue q1;
    99.      Queue q2;
    100.  
    101. } MyStack;
    102.  
    103.  
    104. MyStack* myStackCreate() {
    105.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    106.     QueueInit(&obj->q1);
    107.     QueueInit(&obj->q2);
    108.     return obj;
    109.  
    110. }
    111.  
    112. void myStackPush(MyStack* obj, int x) {
    113.     if(!QueueEmpty(&obj->q1))
    114.     {
    115.         QueuePush(&obj->q1,x);
    116.     }
    117.     else{
    118.         QueuePush(&obj->q2,x);
    119.     }
    120. }
    121. bool myStackEmpty(MyStack* obj) {
    122.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    123. }
    124.  
    125. int myStackPop(MyStack* obj) {
    126.     assert(!myStackEmpty(obj));
    127.     Queue * empty=&obj->q1;
    128.     Queue * nonempty=&obj->q2;
    129.     if(!QueueEmpty(empty))
    130.     {
    131.         empty=&obj->q2;
    132.         nonempty=&obj->q1;
    133.     }
    134.     while(QueueSize(nonempty)!=1)
    135.     {
    136.        int tmp= QueueFront(nonempty);
    137.        QueuePush(empty,tmp);
    138.         QueuePop(nonempty);
    139.     }
    140.      int tmp= QueueFront(nonempty);
    141.       QueuePop(nonempty);
    142.       return tmp;
    143. }
    144.  
    145. int myStackTop(MyStack* obj) {
    146.      assert(!myStackEmpty(obj));
    147.     Queue * empty=&obj->q1;
    148.     Queue * nonempty=&obj->q2;
    149.     if(!QueueEmpty(empty))
    150.     {
    151.         empty=&obj->q2;
    152.         nonempty=&obj->q1;
    153.     }
    154.     return QueueBack(nonempty);
    155. }
    156.  
    157.  
    158.  
    159. void myStackFree(MyStack* obj) {
    160.     QueueDestroy(&obj->q1);
    161.     QueueDestroy(&obj->q2);
    162.     free(obj);
    163.  
    164. }

    三、用栈实现队列 

    225. 用栈实现队列（题目链接）

    思路： 栈是后进先出，队列是先进先出。

    1）入队列：s1栈用来在栈顶入数据；

    2）出队列：s2栈用来出栈顶数据，如果s2为空，则从s1出数据入到s2中去（比如;s1中的数据为1，2，3，入到s2变为3，2，1），再出s2的栈顶数据，这样就满足队列的性质了

     

    1. typedef int  SDateType;
    2. typedef struct Stack
    3. {
    4. 	SDateType* a;
    5. 	int top;
    6. 	int capacity;
    7.  
    8. }Stack;
    9. //初始化栈和销毁栈
    10. void InitStack(Stack* ps)
    11. {
    12. 	assert(ps);
    13. 	ps->a = NULL;
    14. 	ps->capacity = ps->top = 0;
    15. }
    16. void DestoryStack(Stack* ps)
    17. {
    18. 	assert(ps);
    19. 	free(ps->a);
    20. 	ps->a = NULL;
    21. 	ps->capacity = ps->top = 0;
    22.  
    23. }
    24.  
    25. //出栈和入栈
    26. void StackPush(Stack* ps, SDateType x)
    27. {
    28. 	assert(ps);
    29. 	//扩容
    30. 	if (ps->top == ps->capacity)
    31. 	{
    32. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    33. 		SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
    34. 		if (tmp == NULL)
    35. 		{
    36. 			perror("realloc fail:");
    37. 			return;
    38. 		}
    39. 		ps->a = tmp;
    40. 		ps->capacity = newcapacity;
    41.  
    42. 	}
    43. 	//尾插
    44. 	ps->a[ps->top] = x;
    45. 	ps->top++;
    46. }
    47. void StackPop(Stack* ps)
    48. {
    49. 	assert(ps);
    50. 	assert(ps->top > 0);//只少有一个元素，才能删除
    51. 	ps->top--;
    52. }
    53.  
    54. //栈的有效个数和栈顶元素
    55. int  StackSize(Stack* ps)
    56. {
    57. 	assert(ps);
    58. 	return ps->top;
    59. }
    60. int   StackTop(Stack* ps)
    61. {
    62. 	assert(ps);
    63. 	assert(ps->top > 0);
    64. 	return ps->a[ps->top - 1];
    65. }
    66.  
    67. //栈是否为空
    68. bool StackEmpty(Stack* ps)
    69. {
    70. 	assert(ps);
    71. 	return ps->top == 0;
    72. }
    73.  
    74.  
    75.  
    76. typedef struct {
    77.     Stack s1;
    78.     Stack s2;
    79.     
    80. } MyQueue;
    81.  
    82.  
    83. MyQueue* myQueueCreate() {
    84.     MyQueue* obj=(MyQueue* )malloc(sizeof(MyQueue));
    85.     InitStack(&obj->s1);
    86.     InitStack(&obj->s2);
    87.     return obj;
    88.  
    89. }
    90.  
    91. void myQueuePush(MyQueue* obj, int x) {
    92.     StackPush(&obj->s1,x);
    93. }
    94.  
    95. bool myQueueEmpty(MyQueue* obj) {
    96.     return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);
    97. }
    98.  
    99. int myQueuePop(MyQueue* obj) {
    100.     assert(!myQueueEmpty(obj));
    101.     if(StackEmpty(&obj->s2))
    102.     {
    103.        while(!StackEmpty(&obj->s1))
    104.        {
    105.           int tmp= StackTop(&obj->s1);
    106.           StackPush(&obj->s2,tmp);
    107.           StackPop(&obj->s1);
    108.        }
    109.       
    110.     }
    111.      int tmp= StackTop(&obj->s2);
    112.        StackPop(&obj->s2);
    113.        return tmp;
    114. }
    115.  
    116. int myQueuePeek(MyQueue* obj) {
    117.      assert(!myQueueEmpty(obj));
    118.     if(StackEmpty(&obj->s2))
    119.     {
    120.        while(!StackEmpty(&obj->s1))
    121.        {
    122.           int tmp= StackTop(&obj->s1);
    123.           StackPush(&obj->s2,tmp);
    124.           StackPop(&obj->s1);
    125.        }
    126.        
    127.     }
    128.     return StackTop(&obj->s2);
    129. }
    130.  
    131.  
    132.  
    133. void myQueueFree(MyQueue* obj) {
    134.     
    135.    DestoryStack(&obj->s1);
    136.    DestoryStack(&obj->s2);
    137.    free(obj);
    138.  
    139.  
    140.  
    141. }

     四、设计循环队列

    622.设计循环队列（题目链接） 

    思路一：数组

    以front为队列头下标，tail为队列尾下一个元素下标，一共k个数据，开辟k+1个整型大小空间，方便区分队列为空、为满以及一个元素的情况

    1）队列为空，front=tail

    2）队列为1个元素，front+1=tail

    3)   队列为满，（tail+1)%(k+1)==front

     

    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.     int * tmp=(int *)malloc(sizeof(int)*(k+1));
    12.     obj->a=tmp;
    13.     obj->front=0;
    14.     obj->rear=0;
    15.     obj->n=k;
    16.     return obj;
    17. }
    18.  
    19. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    20.     if((obj->rear+1)%(obj->n+1)==obj->front)
    21.     {
    22.         return true;
    23.     }
    24.     return false;
    25. }
    26.  
    27. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    28.     if(myCircularQueueIsFull( obj))
    29.     {
    30.         return false;
    31.     }
    32.     obj->a[obj->rear]=value;
    33.     obj->rear++;
    34.     obj->rear=obj->rear%(obj->n+1);
    35.     return true;
    36. }
    37.  
    38. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    39.     if(obj->front==obj->rear)
    40.     {
    41.         return true;
    42.     }
    43.     return false;
    44. }
    45. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    46.     if(myCircularQueueIsEmpty( obj))
    47.     {
    48.         return false;
    49.     }
    50.     obj->front++;
    51.     obj->front=obj->front%(obj->n+1);
    52.     return true;
    53. }
    54.  
    55. int myCircularQueueFront(MyCircularQueue* obj) {
    56.     if(myCircularQueueIsEmpty( obj))
    57.     {
    58.         return -1;
    59.     }
    60.     return obj->a[obj->front];
    61. }
    62.  
    63. int myCircularQueueRear(MyCircularQueue* obj) {
    64.     if(myCircularQueueIsEmpty( obj))
    65.     {
    66.         return -1;
    67.     }
    68.     return  obj->a[(obj->rear-1+obj->n+1)%(obj->n+1)];
    69. }
    70.  
    71.  
    72.  
    73.  
    74. void myCircularQueueFree(MyCircularQueue* obj) {
    75.     free(obj->a);
    76.     free(obj);
    77. }

     

    思路二：单向循环链表

    以head为队列头节点，tail为队列尾尾节点的下一个节点，一共k个数据，开辟k+1个节点的循环单向链表，方便区分队列为空、为满以及一个元素的情况

    1）队列为空，head=tail

    2）队列为1个元素，head->next=tail

    3)   队列为满，tail->next=head

     

    1. typedef struct QueueNode
    2. {
    3. 	int val;
    4. 	struct QueueNode * next;
    5. }QueueNode;
    6.  
    7. QueueNode* BuyNode(int x)
    8. {
    9.     QueueNode* node=(QueueNode*)malloc(sizeof(QueueNode));
    10.     node->val=x;
    11.     node->next=NULL;
    12.     return node;
    13. }
    14. typedef struct MyCircularQueue{
    15.    QueueNode *head;
    16. 	QueueNode *tail;
    17.     QueueNode * pretail;
    18. 	int n;
    19. } MyCircularQueue;
    20.  
    21.  
    22. MyCircularQueue* myCircularQueueCreate(int k) {
    23.     MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    24.     QueueNode* node=BuyNode(0);
    25.     obj->pretail=NULL;
    26.     obj->head=obj->tail=node;
    27.     obj->n=(k+1);
    28.     QueueNode* cur=obj->tail;
    29.     while(k--)
    30.     {
    31.        QueueNode* node=BuyNode(0);
    32.      
    33.       cur->next=node;
    34.         cur= cur->next;
    35.     }
    36.    
    37.    cur->next=obj->head;
    38.     return obj;
    39. }
    40.  
    41. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    42.     if(obj->tail->next==obj->head)
    43.     {
    44.         return true;
    45.     }
    46.     return false;
    47. }
    48.  
    49. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    50.     if(myCircularQueueIsFull( obj))
    51.     {
    52.         return false;
    53.     }
    54.     obj->tail->val=value;
    55.     obj->pretail=obj->tail;
    56.     obj->tail=obj->tail->next;
    57.    
    58.      
    59.     return true;
    60. }
    61.  
    62. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    63.     if(obj->head==obj->tail)
    64.     {
    65.         return true;
    66.     }
    67.     return false;
    68. }
    69. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    70.     if(myCircularQueueIsEmpty( obj))
    71.     {
    72.         return false;
    73.     }
    74.     obj->head=obj->head->next;
    75.    
    76.     return true;
    77. }
    78.  
    79. int myCircularQueueFront(MyCircularQueue* obj) {
    80.     if(myCircularQueueIsEmpty( obj))
    81.     {
    82.         return -1;
    83.     }
    84.     return obj->head->val;
    85. }
    86.  
    87. int myCircularQueueRear(MyCircularQueue* obj) {
    88.     if(myCircularQueueIsEmpty( obj))
    89.     {
    90.         return -1;
    91.     }
    92.     return  obj->pretail->val;
    93. }
    94.  
    95.  
    96.  
    97.  
    98. void myCircularQueueFree(MyCircularQueue* obj) {
    99.    while(obj->n--)
    100.    {
    101.        QueueNode*next=obj->head->next;
    102.        free(obj->head);
    103.        obj->head=next;
    104.    }
    105.    obj->head=NULL;
    106.     free(obj);
    107. }

     

  • 相关阅读:
    String的compareTo()方法使用场景介绍及全量ASCII 码表（完整版）
    P2404 自然数的拆分问题
    vue项目中的 env文件从何而来？什么是 process.env
    九、MySQL之视图的介绍
    OpenStack学习笔记-Glance组件深入了解
    黑马点评-发布探店笔记
    【C++】匿名对象 ③ ( 函数返回值为对象值时 匿名对象 的 拷贝构造函数 与 析构函数 调用情况分析 )
    TypeScript学习 | 泛型
    中国石油大学(北京)-《 油气藏经营管理》第二阶段在线作业
    单词规律（C++解法）
  • 原文地址：https://blog.csdn.net/zhoubancheng/article/details/134538488