栈和队列题目练习

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

有效的括号

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

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

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

typedef  char  datatype;
typedef struct stack {datatype* a;int top;//栈顶int capacity;
}ST;
void STInit(ST* pst){assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置,可以理解为下标pst->top = 0;pst->capacity = 0;
}
void STDestory(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
//容量检查
void Checkcapacity(ST* pst) {assert(pst);if (pst->top == pst->capacity) {int newcapacity = pst->capacity==0?4:pst->capacity * 2;datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype));if (temp == NULL) {perror("relloc fail");return;}pst->a = temp;pst->capacity = newcapacity;}
}
//入栈和出栈
void STPush(ST* pst, datatype x) {assert(pst);Checkcapacity(pst);pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst) {assert(pst);assert(pst->top>0);pst->top--;
}
//获取栈顶数据
datatype STTop(ST* pst) {assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}
//判空
bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;//表达式判断
}
//栈的数据个数
int STSize(ST* pst) {assert(pst);return pst->top;
}
bool isValid(char* s) {ST st;STInit(&st);while(*s){//左括号入栈if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{//空集的情况，入栈结束后检查是否为空，if(STEmpty(&st)){STDestory(&st);return false;}char top=STTop(&st);STPop(&st);//通过括号不匹配的情况判断if((top=='('&& *s!=')') ||(top=='['&& *s!=']')||(top=='{'&& *s!='}')){STDestory(&st);return false;//STPop(&st);}}s++;}
//看最后是否栈为空，探讨左右括号数量不匹配的情况。bool ret=(STEmpty(&st));STDestory(&st);return ret;
}

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

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

bool isValid(char* s) {char stack[10000];int top = -1;int len = strlen(s);for (int i = 0; i < len; i++) {if (s[i] == '(' || s[i] == '{' || s[i] == '[') {stack[++top] = s[i];} else {if (top == -1) {return false;}if ((s[i] == ')' && stack[top] == '(') || (s[i] == '}' && stack[top] == '{') || (s[i] == ']' && stack[top] == '[')) {top--;} else {return false;}}}return top == -1;
}

设计循环队列

方法1:使用动态数组

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

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

//循环队列先进先出
typedef struct {int *arr;int head;int tail;//指向尾下一个int k;
} MyCircularQueue;//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开辟一个空间obj->arr=(int*)malloc(sizeof(int)*(k+1));obj->head=0;obj->tail=0;obj->k=k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//头尾相等时队列为空return (obj->head)==obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//当tail+1=head时，为满，通过取模解决回绕问题return((obj->tail+1)%(obj->k+1))==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满的时候，返回falseif(myCircularQueueIsFull(obj))return false;//插入一个数据，tail后移obj->arr[obj->tail]=value;obj->tail++;//解决回绕，重头再来obj->tail %=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;//head前进，删除数据obj->head++;//解决回绕问题obj->head %=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->arr[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;else//分类讨论取尾元素return obj->tail==0?obj->arr[obj->k]:obj->arr[obj->tail-1];//return obj->arr[(obj->tail-1+obj->k+1)%(obj->k+1)];//取模的方法很巧妙
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}

方法2：双向链表实现

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

//节点建立
typedef struct Node {int val;struct Node* prev;struct Node* next;
} Node;
//双向链表实现队列
typedef struct {Node* head;Node* tail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->head = NULL;obj->tail = NULL;obj->size = 0;obj->capacity = k;return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}
//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) {return false;}Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = value;newNode->prev = NULL;newNode->next = NULL;//队列为空时if (myCircularQueueIsEmpty(obj)) {obj->head = newNode;obj->tail = newNode;newNode->next = newNode;newNode->prev = newNode;} // 不为空时else {newNode->prev = obj->tail;newNode->next = obj->head;obj->tail->next = newNode;obj->head->prev = newNode;obj->tail = newNode;}obj->size++;return true;
}
//数据的删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) {return false;}Node* del = obj->head;if (obj->size == 1) {obj->head = NULL;obj->tail = NULL;} else {obj->head = obj->head->next;obj->head->prev = obj->tail;obj->tail->next = obj->head;}obj->size--;free(del);return true;
}
//头数据
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) {return -1;}return obj->head->val;
}
//尾数据
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) {return -1;}return obj->tail->val;
}
//队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {Node* curr = obj->head;while (curr != obj->tail) {Node* next = curr->next;free(curr);curr = next;}obj->tail=NULL;free(obj);
}

补充方法3：

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

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

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

循环队列的属性如下:

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

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

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//中间节点创建和函数主体
typedef struct node {int val;struct node* next;
} node;
//循环队列先进先出
typedef struct {node* head;node* tail;int size;int capacity;
} MyCircularQueue;//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->head=obj->tail=NULL;obj->size=0;obj->capacity=k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->size==0)return true;elsereturn false;
//return obj->size==0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->capacity;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;node* newnode=(struct node*)malloc(sizeof(node));newnode->val=value;newnode->next=NULL;if(obj->size==0){obj->head=newnode;obj->tail=newnode;}else{obj->tail->next=newnode;obj->tail=newnode;}obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;node*del=obj->head;obj->head=obj->head->next;free(del);obj->size--;return true;}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->tail->val;
}void myCircularQueueFree(MyCircularQueue* obj) {node* curr = obj->head;while (curr != NULL) {node* next = curr->next;free(curr);curr = next;}obj->size = obj->capacity = 0;obj->head = obj->tail = NULL;free(obj);
}//手动测试部分
int main() {MyCircularQueue* obj = myCircularQueueCreate(5);myCircularQueueEnQueue(obj, 1);myCircularQueueEnQueue(obj, 2);myCircularQueueEnQueue(obj, 3);myCircularQueueEnQueue(obj, 4);myCircularQueueEnQueue(obj, 5);printf("%d\n", myCircularQueueRear(obj));printf("%d\n", myCircularQueueFront(obj));myCircularQueueDeQueue(obj);printf("%d\n", myCircularQueueFront(obj));myCircularQueueFree(obj);return 0;
}