- 1、括号匹配问题
- 2、用队列实现栈
- 3、用栈实现队列
- 4、设计循环队列
LeetCode链接: 【20. 有效的括号】
这道题就是经典的利用栈解决问题的例子;思路如下:
遍历一遍字符串,如果遇倒左括号就入栈,如果遇倒右括号取栈顶的元素进行匹配并出栈顶的元素,如果相匹配就继续,不匹配就返回false。
但是要注意这样只能检验出左右括号个数相等的情况下才可以,如果左右括号个数不相等呢?
- 如果左括号多于右括号,并且遍历结束后它们都是匹配的,这种情况并不是完全匹配的,因为栈里还有元素剩余;所以遍历字符串后要加一个判断栈是否为空,只要栈为空了才是全部匹配完,没有剩余。 比如:“[[[[[((()))”
- 如果右括号多余左括号,有可能导致栈是空的,栈里面没有元素可以取了,这种情况也是不匹配的;所以取栈顶元素的前面要加一个判断栈是否为空,如果栈为空说明右括号多余左括号,是不匹配的。比如:”((([[[ ]]]]]]]]]"
代码实现如下:
//C语言中没有栈,我们先实现一个栈 //构建栈如下: typedef char STDataType; struct Stack { STDataType* a; int top; int capacity; }; typedef struct Stack ST; //初始化栈 void StackInit(ST* ps); //销毁栈 void StackDestroy(ST* ps); //入栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //获取栈的元素个数 int StackSize(ST* ps); //获取栈顶的元素 STDataType StackTop(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); void StackInit(ST* ps) { ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackDestroy(ST* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps,STDataType x) { assert(ps); if (ps->capacity == ps->top) { ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2; STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType)); if (tmp == NULL) { return; } else { ps->a = tmp; } } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } int StackSize(ST* ps) { assert(ps); assert(ps->top > 0); return ps->top; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } bool isValid(char * s){ ST st; StackInit(&st); while(*s!='') { switch(*s) { //压栈 case '(': case '[': case '{': StackPush(&st,*s); s++; break; //取栈顶的数据进行匹配 case ')': case ']': case '}': //出栈,从栈里面取做括号,栈里面的元素不能为空, //防止右括号过多,导致取到栈里面没有元素可以取,这也是不匹配 if(StackEmpty(&st)) { StackDestroy(&st); return false; } //取栈顶的数据和字符比较 char top=StackTop(&st); StackPop(&st); if(top=='(' && *s==')' || top=='[' && *s==']' || top=='{' && *s=='}' ) { s++; } else { StackDestroy(&st); return false; } } } //最后要判断栈是否为空 //栈是空的说明才完全匹配,如果还要剩余说明没有是左括号多了,不匹配 if(StackEmpty(&st)) { StackDestroy(&st); return true; } else { StackDestroy(&st); return false; } }2、用队列实现栈
LeetCode链接: 【225. 用队列实现栈】
思路: 这是要我们利用队列的性质去实现栈,队列的性质是先入先出,而栈的性质是后入先出;
所以我们利用两个队列来实现栈,一个为空队列,一个不为空队列;入栈:就往不为空的队列里面入,而 出栈就是: 只保留不为空的队列的最后一个元素,前面的元素都插入空队列中;然后再把最后一个元素出掉就是出栈了。
代码实现如下:
//C语言中没有队列,我们先构建一个队列的各种接口 //队列实现如下: typedef int DataType; typedef struct Node { struct Node* next; DataType data; }Node; typedef struct Queue { Node* phead; Node* tail; }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestroy(Queue* pq); //队列插数据 void QueuePush(Queue* pq,DataType x); //队列出数据 void QueuePop(Queue* pq); //取队尾数据 DataType QueueBack(Queue* pq); //取队头数据 DataType QueueFront(Queue* pq); //取队列中元素个数 int QueueSize(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->tail = NULL; } void QueuePush(Queue* pq, DataType x) { Node* tmp = (Node*)malloc(sizeof(Node)); if (tmp == NULL) { perror("malloc "); exit(-1); } tmp->data = x; tmp->next = NULL; if (pq->tail == NULL) { pq->phead = tmp; pq->tail = tmp; } else { pq->tail->next = tmp; pq->tail = tmp; } } void QueuePop(Queue* pq) { assert(pq); assert(pq->phead); // 一个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = NULL; pq->tail = NULL; } //多个节点 else { Node* tmp = pq->phead->next; free(pq->phead); pq->phead = tmp; } } int QueueSize(Queue* pq) { assert(pq); int count = 0; Node* cur = pq->phead; while (cur != NULL) { cur = cur->next; count++; } return count; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } DataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->data; } DataType QueueBack(Queue* pq) { assert(pq); assert(pq->phead); return pq->tail->data; } void QueueDestroy(Queue* pq) { assert(pq); Node* tmp = pq->phead; while (tmp != NULL) { Node* next = tmp->next; free(tmp); tmp = next; } pq->phead = pq->tail = NULL; } //上面都是在实现队列的各种接口 //下面是利用两个队列来实现栈 //用两给队列来实现栈,两个队列不断倒元素即可 typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* tmp=(MyStack*)malloc(sizeof(MyStack)); if(tmp==NULL) { perror("erron "); exit(-1); } QueueInit(&tmp->q1); QueueInit(&tmp->q2); return tmp; } //往不为空的队列插数据,如果两个队列都为空,任意一个都行 void myStackPush(MyStack* obj, int x) { Queue* empty=&obj->q1; Queue* nonempty=&obj->q2; if(QueueEmpty(&obj->q2)) { Queue* empty=&obj->q2; Queue* nonempty=&obj->q1; } QueuePush(nonempty,x); } //先把不为空的队列往空队列里面倒数据,倒到只剩下1个元素 //而这不为空的队列最后一个元素就是栈顶的元素,出掉即可 int myStackPop(MyStack* obj) { Queue* empty=&obj->q1; Queue* nonempty=&obj->q2; if(QueueEmpty(&obj->q2)) { empty=&obj->q2; nonempty=&obj->q1; } while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } //最后一个元素就是栈顶的元素 //出掉即可,保证队列有一个为空队列 int tmp=QueueBack(nonempty); QueuePop(nonempty); return tmp; } //直接取不为空的队列的尾元素即可 int myStackTop(MyStack* obj) { Queue* empty=&obj->q1; Queue* nonempty=&obj->q2; if(QueueEmpty(&obj->q2)) { empty=&obj->q2; nonempty=&obj->q1; } return QueueBack(nonempty); } bool myStackEmpty(MyStack* obj) { //两给队列都为空,栈才是空 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }3、用栈实现队列
LeetCode链接: 【232. 用栈实现队列】
思路分析如下:
代码实现如下:
//C语言中没有栈,我们先实现一个栈 //构建栈如下: typedef int STDataType; struct Stack { STDataType* a; int top; int capacity; }; typedef struct Stack ST; //初始化栈 void StackInit(ST* ps); //销毁栈 void StackDestroy(ST* ps); //入栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //获取栈的元素个数 int StackSize(ST* ps); //获取栈顶的元素 STDataType StackTop(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); void StackInit(ST* ps) { ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackDestroy(ST* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps,STDataType x) { assert(ps); if (ps->capacity == ps->top) { ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2; STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType)); if (tmp == NULL) { return; } else { ps->a = tmp; } } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } int StackSize(ST* ps) { assert(ps); assert(ps->top > 0); return ps->top; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //两个栈,把不为空的栈往为空的栈里面倒过来就是队列了 //设计两个栈,一个用来入数据,一个用来出数据 //入数据就入pushst栈,出数据就出popst栈 typedef struct { ST Pushst; //入数据栈 ST Popst; //出数据栈 } MyQueue; MyQueue* myQueueCreate() { MyQueue* tmp=(MyQueue*)malloc(sizeof(MyQueue)); if(tmp==NULL) { perror("erron "); exit(-1); } StackInit(&tmp->Pushst); StackInit(&tmp->Popst); return tmp; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->Pushst,x); } //要检验出数据的栈是否为空,没有数据了就从入数据的栈里面取 int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->Popst)) { while(!StackEmpty(&obj->Pushst)) { StackPush(&obj->Popst,StackTop(&obj->Pushst)); StackPop(&obj->Pushst); } } int tmp=StackTop(&obj->Popst); StackPop(&obj->Popst); return tmp; } //取队列的头元素,检验出数据的栈是否为空,没有数据了就从入数据的栈里面取 int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->Popst)) { while(!StackEmpty(&obj->Pushst)) { StackPush(&obj->Popst,StackTop(&obj->Pushst)); StackPop(&obj->Pushst); } } return StackTop(&obj->Popst); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->Pushst) && StackEmpty(&obj->Popst); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->Pushst); StackDestroy(&obj->Pushst); free(obj); }4、设计循环队列
LeetCode链接: 【622. 设计循环队列】
做这道题之前,我们先来了解什么是循环队列?它的解释如下:
循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。
循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。
所以循环队列的结构搞清楚了,写起来就比较简单了,循环队列有两种实现方式,可以使用数组实现,也可以使用循环链表实现。下面分别来介绍。
链表实现如下:
//先创建一个结点类型 typedef struct Node { struct Node* next; int data; }Node; //创建一个循环队列类型结构体 //里面的头指针指向链表的头,尾指针指向链表的尾 typedef struct { Node* front; Node* tail; } MyCircularQueue; //创建循环队列 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //构造一个环链表 //要多构造一个结点,不然判断不了是否满了 Node* head=(Node*)malloc(sizeof(Node)); Node* a=head; Node* tail=head; while(k--) { a=tail; tail=(Node*)malloc(sizeof(Node)); a->next=tail; } tail->next=head; tmp->front=head; tmp->tail=head; return tmp; } //向循环队列插入一个元素 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(obj->tail->next==obj->front) { return false; } obj->tail->data=value; obj->tail=obj->tail->next; return true; } //从循环队列中删除一个元素 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(obj->front==obj->tail) { return false; } obj->front=obj->front->next; return true; } //从队首获取元素 int myCircularQueueFront(MyCircularQueue* obj) { if(obj->front==obj->tail) { return -1; } return obj->front->data; } //获取队尾元素 int myCircularQueueRear(MyCircularQueue* obj) { if(obj->front==obj->tail) { return -1; } //找队尾的前一个结点就是队尾数据 Node* cur=obj->front; while(cur->next!=obj->tail) { cur=cur->next; } return cur->data; } //检查循环队列是否为空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->tail; } //检查循环队列是否已满。 bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->tail->next==obj->front; } //释放内存 void myCircularQueueFree(MyCircularQueue* obj) { Node* cur=obj->front; while(cur!=obj->tail) { Node* next=cur->next; free(cur); cur=next; } free(cur); free(obj); }
数组方式实现如下:
代码实现如下:
//在循环队列结构中设计一个指针指向一段连续的空间 typedef struct { int* a; int maxSize; int head; int tail; } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj); //创建循环队列 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* tmp= (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //要多开辟一个空间 int* arr=(int*)malloc(sizeof(int)*(k+1)); tmp->a=arr; tmp->maxSize=k+1; tmp->head=0; tmp->tail=0; return tmp; } //向循环队列插入一个元素 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->a[obj->tail]=value; obj->tail++; //把下标tail控制在数组中,不能越界 if(obj->tail==obj->maxSize) { obj->tail=0; } return true; } //从循环队列中删除一个元素 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(obj->head==obj->tail) { return false; } obj->head++; if(obj->head==obj->maxSize) { obj->head=0; } return true; } //从队首获取元素 int myCircularQueueFront(MyCircularQueue* obj) { if(obj->head==obj->tail) { return -1; } return obj->a[obj->head]; } //获取队尾元素 int myCircularQueueRear(MyCircularQueue* obj) { if(obj->head==obj->tail) { return -1; } int i=0; if(obj->tail==0) { i=obj->maxSize-1; } else { i=obj->tail-1; } return obj->a[i]; } //检查循环队列是否为空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head==obj->tail; } //检查循环队列是否已满 bool myCircularQueueIsFull(MyCircularQueue* obj) { //方法1判断是否满了 // return obj->head==(obj->tail+1)%obj->maxSize; //方法2判断是否满了 int head=0; if(obj->head==0) { head=obj->maxSize-1; } else { head=obj->head-1; } return head==obj->tail; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)