• 栈和队列题目练习

    本节小编选了两道题来加深对栈和队列的认识理解！

    有效的括号

    方法1：直接用栈的结构（动态数组）

    本题可以用栈这个结构来解答，将'(','{','['  左括号压入栈中，然后取出栈顶元素与右括号')','}',']'匹配。不匹配的话，返回false,我们同时也要考虑空集的情况，即栈中元素为空，则返回false。

    因为本题使用c语言写的，所以需要手撕栈的结构，可以运用上篇博客所写的栈的代码。

    1. typedef  char  datatype;
    2. typedef struct stack {
    3. 	datatype* a;
    4. 	int top;//栈顶
    5. 	int capacity;
    6. }ST;
    7. void STInit(ST* pst){
    8. 	assert(pst);
    9. 	pst->a = NULL;
    10. 	//top指向栈顶数据的下一个位置,可以理解为下标
    11. 	pst->top = 0;
    12. 	pst->capacity = 0;
    13. }
    14. void STDestory(ST* pst) {
    15. 	assert(pst);
    16. 	free(pst->a);
    17. 	pst->a = NULL;
    18. 	pst->top = pst->capacity = 0;
    19. }
    20. //容量检查
    21. void Checkcapacity(ST* pst) {
    22. 	assert(pst);
    23. 	if (pst->top == pst->capacity) {
    24. 		int newcapacity = pst->capacity==0?4:pst->capacity * 2;
    25. 		datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype));
    26. 		if (temp == NULL) {
    27. 			perror("relloc fail");
    28. 			return;
    29. 		}
    30. 		pst->a = temp;
    31. 		pst->capacity = newcapacity;
    32. 	}
    33. }
    34. //入栈和出栈
    35. void STPush(ST* pst, datatype x) {
    36. 	assert(pst);
    37. 	Checkcapacity(pst);
    38. 	pst->a[pst->top] = x;
    39. 	pst->top++;
    40. }
    41. void STPop(ST* pst) {
    42. 	assert(pst);
    43. 	assert(pst->top>0);
    44. 	pst->top--;
    45. }
    46. //获取栈顶数据
    47. datatype STTop(ST* pst) {
    48. 	assert(pst);
    49. 	assert(pst->top > 0);
    50. 	return pst->a[pst->top-1];
    51. }
    52. //判空
    53. bool STEmpty(ST* pst) {
    54. 	assert(pst);
    55. 	return pst->top == 0;//表达式判断
    56. }
    57. //栈的数据个数
    58. int STSize(ST* pst) {
    59. 	assert(pst);
    60. 	return pst->top;
    61. }
    62. bool isValid(char* s) {
    63.     ST st;
    64.     STInit(&st);
    65.     while(*s){
    66.         //左括号入栈
    67.         if(*s=='('||*s=='{'||*s=='['){
    68.             STPush(&st,*s);
    69.         }
    70.     else{
    71.        //空集的情况，入栈结束后检查是否为空，
    72.         if(STEmpty(&st)){
    73.         STDestory(&st);
    74.         return false;
    75.         }
    76.         char top=STTop(&st);
    77.         STPop(&st);
    78.        //通过括号不匹配的情况判断
    79.         if((top=='('&& *s!=')') ||(top=='['&& *s!=']')||(top=='{'&& *s!='}')){
    80.         STDestory(&st);
    81.         return false;
    82.         //STPop(&st);
    83.     }
    84.     }
    85.     s++;
    86.     }
    87. //看最后是否栈为空，探讨左右括号数量不匹配的情况。
    88.    bool ret=(STEmpty(&st));
    89.      STDestory(&st);
    90.      return ret;
    91. }

    方法2：通过数组模拟栈来实现

    使用一个字符数组作为栈，通过使用top标记栈顶的位置来实现栈的操作。在遍历字符串的过程中，遇到左括号就将其压入栈中，遇到右括号就与栈顶元素进行匹配。如果匹配成功，则将栈顶元素出栈，否则返回false。最后，如果栈为空，则说明所有的括号都匹配成功，返回true；否则，返回false。

    1. bool isValid(char* s) {
    2.     char stack[10000];
    3.     int top = -1;
    4.     int len = strlen(s);
    5.     for (int i = 0; i < len; i++) {
    6.         if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
    7.             stack[++top] = s[i];
    8.         } else {
    9.             if (top == -1) {
    10.                 return false;
    11.             }
    12.             
    13.             if ((s[i] == ')' && stack[top] == '(') || 
    14.                 (s[i] == '}' && stack[top] == '{') || 
    15.                 (s[i] == ']' && stack[top] == '[')) {
    16.                 top--;
    17.             } else {
    18.                 return false;
    19.             }
    20.         }
    21.     }
    22.     
    23.     return top == -1;
    24. }

    设计循环队列

    方法1:使用动态数组

    通过画图发现，当head==tail时，既是队列为空的条件，也是队列满的条件，所以我们可以通过增加一个空间来辅助判满，当tail+1=head时。还有另外一个方法，通过定义size变量，当size大小等于k时，也是队列满的时候。

    在后续解决回绕的问题时，我们多次采用取模的方法，因为一个数除以比他大的数，取模后大小不变，当相等时，模为0，刚好回到起点处，完美的解决了回绕问题。

    1.  
    2.  
    3. //循环队列先进先出
    4. typedef struct {
    5.     int *arr;
    6.     int head;
    7.     int tail;//指向尾下一个
    8.     int k;
    9. } MyCircularQueue;
    10.  
    11. //创建循环队列
    12. MyCircularQueue* myCircularQueueCreate(int k) {
    13.     MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    14.     //多开辟一个空间
    15. 	obj->arr=(int*)malloc(sizeof(int)*(k+1));
    16.     
    17. 	obj->head=0;
    18.     obj->tail=0;
    19.     obj->k=k;
    20.     return obj;
    21. }
    22. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    23.     //头尾相等时队列为空
    24. 	return (obj->head)==obj->tail;
    25. }
    26.  
    27. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    28.     //当tail+1=head时，为满，通过取模解决回绕问题
    29. 	return((obj->tail+1)%(obj->k+1))==obj->head;
    30. }
    31. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    32.     //队列满的时候，返回false
    33. 	if(myCircularQueueIsFull(obj))
    34.     return false;
    35.     //插入一个数据，tail后移
    36. 	obj->arr[obj->tail]=value;
    37.     obj->tail++;
    38.     //解决回绕，重头再来
    39.     obj->tail %=(obj->k+1);
    40.     return true;
    41. }
    42.  
    43. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    44.     if(myCircularQueueIsEmpty(obj))
    45.     return false;
    46.     //head前进，删除数据
    47. 	obj->head++;
    48. 	//解决回绕问题
    49.     obj->head %=(obj->k+1);
    50.     return true;
    51. }
    52.  
    53. int myCircularQueueFront(MyCircularQueue* obj) {
    54.     if(myCircularQueueIsEmpty(obj))
    55.     return -1;
    56.     return obj->arr[obj->head];
    57. }
    58.  
    59. int myCircularQueueRear(MyCircularQueue* obj) {
    60.     if(myCircularQueueIsEmpty(obj))
    61.     return -1;
    62.     else
    63.     //分类讨论取尾元素
    64.     return obj->tail==0?obj->arr[obj->k]:obj->arr[obj->tail-1];
    65.     //return obj->arr[(obj->tail-1+obj->k+1)%(obj->k+1)];//取模的方法很巧妙
    66. }
    67.  
    68. void myCircularQueueFree(MyCircularQueue* obj) {
    69.     free(obj->arr);
    70.     free(obj);
    71. }

    方法2：双向链表实现

    使用双向链表实现，其中每个节点（Node）包含一个整数值（val），以及指向前一个节点和后一个节点的指针（prev和next）。循环队列（MyCircularQueue）包含一个指向队列头部和尾部的指针（head和tail），以及队列的大小（size）和容量（capacity）。

    1. //节点建立
    2. typedef struct Node {
    3.     int val;
    4.     struct Node* prev;
    5.     struct Node* next;
    6. } Node;
    7. //双向链表实现队列
    8. typedef struct {
    9.     Node* head;
    10.     Node* tail;
    11.     int size;
    12.     int capacity;
    13. } MyCircularQueue;
    14.  
    15. MyCircularQueue* myCircularQueueCreate(int k) {
    16.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    17.     obj->head = NULL;
    18.     obj->tail = NULL;
    19.     obj->size = 0;
    20.     obj->capacity = k;
    21.     return obj;
    22. }
    23. //判空
    24. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    25.     return obj->size == 0;
    26. }
    27. //判满
    28. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    29.     return obj->size == obj->capacity;
    30. }
    31. //插入数据
    32. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    33.     if (myCircularQueueIsFull(obj)) {
    34.         return false;
    35.     }
    36.  
    37.     Node* newNode = (Node*)malloc(sizeof(Node));
    38.     newNode->val = value;
    39.     newNode->prev = NULL;
    40.     newNode->next = NULL;
    41.  //队列为空时
    42.     if (myCircularQueueIsEmpty(obj)) {
    43.         obj->head = newNode;
    44.         obj->tail = newNode;
    45.         newNode->next = newNode;
    46.         newNode->prev = newNode;
    47.     } 
    48.   // 不为空时
    49.  
    50. else {
    51.         newNode->prev = obj->tail;
    52.         newNode->next = obj->head;
    53.         obj->tail->next = newNode;
    54.         obj->head->prev = newNode;
    55.         obj->tail = newNode;
    56.     }
    57.     obj->size++;
    58.     return true;
    59. }
    60. //数据的删除
    61. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    62.     if (myCircularQueueIsEmpty(obj)) {
    63.         return false;
    64.     }
    65.  
    66.     Node* del = obj->head;
    67.     if (obj->size == 1) {
    68.         obj->head = NULL;
    69.         obj->tail = NULL;
    70.     } else {
    71.         obj->head = obj->head->next;
    72.         obj->head->prev = obj->tail;
    73.         obj->tail->next = obj->head;
    74.     }
    75.  
    76.     obj->size--;
    77.     free(del);
    78.     return true;
    79. }
    80. //头数据
    81. int myCircularQueueFront(MyCircularQueue* obj) {
    82.     if (myCircularQueueIsEmpty(obj)) {
    83.         return -1;
    84.     }
    85.     return obj->head->val;
    86. }
    87. //尾数据
    88. int myCircularQueueRear(MyCircularQueue* obj) {
    89.     if (myCircularQueueIsEmpty(obj)) {
    90.         return -1;
    91.     }
    92.     return obj->tail->val;
    93. }
    94. //队列销毁
    95. void myCircularQueueFree(MyCircularQueue* obj) {
    96.     Node* curr = obj->head;
    97.     while (curr != obj->tail) {
    98.         Node* next = curr->next;
    99.         free(curr);
    100.         curr = next;
    101.     }
    102.     obj->tail=NULL;
    103.  
    104.     free(obj);
    105. }

    补充方法3：

    使用链表（单链表）-投机取巧哈哈哈

    不过这种方法没有关系到循环队列，也能通过该题目。

    可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在 O(1)时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。

    循环队列的属性如下:

    head：链表的头节点，队列的头节点。
    tail：链表的尾节点，队列的尾节点。
    capacity：队列的容量，即队列可以存储的最大元素数量。
    size：队列当前的元素的数量。

    相比较与数组，我们使用了size的方法来判断队列为空为满的状态，

    1. #include 
    2. #include 
    3. #include 
    4. //中间节点创建和函数主体
    5. typedef struct node {
    6.     int val;
    7.     struct node* next;
    8. } node;
    9. //循环队列先进先出
    10. typedef struct {
    11.     node* head;
    12.     node* tail;
    13.     int size;
    14.     int capacity;
    15. } MyCircularQueue;
    16.  
    17. //创建循环队列
    18. MyCircularQueue* myCircularQueueCreate(int k) {
    19.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    20.     obj->head=obj->tail=NULL;
    21.     obj->size=0;
    22.     obj->capacity=k;
    23.     return obj;
    24. }
    25. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    26.    if(obj->size==0)
    27.    return true;
    28.    else
    29.    return false;
    30. //return obj->size==0;
    31. }
    32.  
    33. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    34.     return obj->size==obj->capacity;
    35. }
    36. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    37.     if(myCircularQueueIsFull(obj))
    38.     return false;
    39.     node* newnode=(struct node*)malloc(sizeof(node));
    40.     newnode->val=value;
    41.     newnode->next=NULL;
    42.     if(obj->size==0)
    43.     {
    44.         obj->head=newnode;
    45.         obj->tail=newnode;
    46.     }
    47.     else{
    48.     obj->tail->next=newnode;
    49.     obj->tail=newnode;
    50.     }
    51.     obj->size++;
    52.     return true;
    53. }
    54.  
    55. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    56.     if(myCircularQueueIsEmpty(obj))
    57.     return false;
    58.     node*del=obj->head;
    59.     obj->head=obj->head->next;
    60.     free(del);
    61.     obj->size--;
    62.     return true;
    63.  
    64. }
    65.  
    66. int myCircularQueueFront(MyCircularQueue* obj) {
    67.     if(myCircularQueueIsEmpty(obj))
    68.     return -1;
    69.     return obj->head->val;
    70. }
    71.  
    72. int myCircularQueueRear(MyCircularQueue* obj) {
    73.     if(myCircularQueueIsEmpty(obj))
    74.     return -1;
    75.     return obj->tail->val;
    76. }
    77.  
    78. void myCircularQueueFree(MyCircularQueue* obj) {
    79.     node* curr = obj->head;
    80.     while (curr != NULL) {
    81.         node* next = curr->next;
    82.         free(curr);
    83.         curr = next;
    84.     }
    85.     
    86.     obj->size = obj->capacity = 0;
    87.     obj->head = obj->tail = NULL;
    88.     free(obj);
    89. }
    90.  
    91. //手动测试部分
    92. int main() {
    93.     MyCircularQueue* obj = myCircularQueueCreate(5);
    94.     myCircularQueueEnQueue(obj, 1);
    95.     myCircularQueueEnQueue(obj, 2);
    96.     myCircularQueueEnQueue(obj, 3);
    97.     myCircularQueueEnQueue(obj, 4);
    98.     myCircularQueueEnQueue(obj, 5);
    99.     printf("%d\n", myCircularQueueRear(obj));
    100.     printf("%d\n", myCircularQueueFront(obj));
    101.     myCircularQueueDeQueue(obj);
    102.     printf("%d\n", myCircularQueueFront(obj));
    103.     myCircularQueueFree(obj);
    104.     return 0;
    105. }

    OK，本节内容到此结束，各位友友留下三连和评论吧，有更好的方法希望各位佬私信交流！！！

  • 相关阅读:
    什么是多维数组？怎样定义多维数组？
    为什么电力公司很少用轨道式的电表？
    基于Citespace、vosviewer、R语言的文献计量学可视化分析技术及全流程文献可视化SCI论文高效写作
    【LeetCode算法系列题解】第41~45题
    机器学习工作岗位
    c: dat file
    动动嘴即可搜视频 抖音与Siri达成合作
    关于防重复提交踩的一次坑
    Cholesterol-PEG-Maleimide|胆固醇-聚乙二醇-马来酰亚胺修饰蛋白用
    直播预告 | 全新定义业务观测新范式，让稳定更有力量
  • 原文地址：https://blog.csdn.net/2302_79376097/article/details/139223675