有效的括号
题目链接:力扣(LeetCode)
思路:这道题可以用栈来解决,先让字符串中的左括号' ( ',' [ ',' { '入栈,s指向字符串下一个字符,如果该字符也是左括号,那就继续入栈,如果是右括号,那就让其与栈顶元素相匹配(每次都要弹出栈顶元素),匹配上了,继续循环,匹配不上就返回false,注意在每次返回false之前都要销毁栈。
还要考虑极端情况,如果全是左括号,我们要在代码最后进行判空,不为空,返回false,同时,这次判空也能解决前面几对都匹配上,只有最后一个左括号没匹配上的问题(例如:"()[]{}{")。
如果全是右括号,说明整个过程中没有入栈元素,此时判空,如果为空返回false,同时,这次判空也能解决前面几对都匹配上,只有最后一个右括号没匹配上的问题(例如:"()[]{}}")。
如果用C语言来解题的话,栈需要自己写。
代码如下:
typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; //初始化栈 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } //入栈 void STPush(ST* pst, STDatatype x) { //开辟空间 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入 pst->a[pst->top] = x; pst->top++; } //判空函数 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } //出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } //获取栈顶元素 STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } //获取栈中有效数据的个数 int STSize(ST* pst) { assert(pst); return pst->top; } //销毁栈 void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } 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; } } ++s; } bool ret=STEmpty(&st); STDestory(&st); return ret; }
用队列实现栈
题目链接:力扣(LeetCode)
思路:队列是先入先出,栈是先入后出,要用队列实现栈,我们可以定义两个栈q1和q2,当它们都为空时,随便选一个存入数据,假设q1中有数据1 2 3 4,我们可以把q1中的1 2 3 push进q2中,然后把q1中的4pop出去,接着把q2中的1 2 push进q1,然后把q2中的3pop出去,这样循环在q1和q2中倒数据,就实现了4 3 2 1依次出栈,即先入后出。
当我们在出栈的同时,想要入栈,就把数据push进有数据的队列即可。
想要用C语言做这道题,队列的实现代码也要自己写。
注意,我们下列代码是结构体的三层嵌套,所以销毁时要先销毁q1和q2,再销毁obj,如果只销毁obj,由于我们的队列q1和q2中分别有两个头尾指针还有节点,会造成内存泄漏的问题。
它们的关系图如下:
代码如下:
typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化队列 void QueueInit(Queue* pq) { pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } //队尾入队列 void QueuePush(Queue* pq, QDatatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail=newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } //判空函数 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size ==0 ; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //一个节点 //多个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail= NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } //获取队列头部元素 QDatatype QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } //获取队列尾部元素 QDatatype QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } //获取队列中有效元素个数 int Queuesize(Queue* pq) { assert(pq); return pq->size; } //销毁队列 void DestoryQueue(Queue* pq) { assert(pq); while (pq->phead) { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); if(obj==NULL) { perror("malloc fail"); return NULL; } QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue* pemptyq=&obj->q1; Queue* pnoemptyq=&obj->q2; if(!QueueEmpty(&obj->q1)) { pemptyq=&obj->q2; pnoemptyq=&obj->q1; } while(Queuesize(pnoemptyq)>1) { QueuePush(pemptyq,QueueFront(pnoemptyq)); QueuePop(pnoemptyq); } int top=QueueFront(pnoemptyq); QueuePop(pnoemptyq); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) return QueueBack(&obj->q1); else return QueueBack(&obj->q2); } bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { DestoryQueue(&obj->q1); DestoryQueue(&obj->q2); free(obj); }
用栈实现队列
题目链接:力扣(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。
代码如下:
typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; //初始化栈 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0; pst->capacity = 0; } //入栈 void STPush(ST* pst, STDatatype x) { //开辟空间 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } //插入 pst->a[pst->top] = x; pst->top++; } //判空函数 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } //出栈 void STPop(ST* pst) { assert(pst); assert(!STEmpty(pst)); pst->top--; } //获取栈顶元素 STDatatype STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } //获取栈中有效数据的个数 int STSize(ST* pst) { assert(pst); return pst->top; } //销毁栈 void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } typedef struct { ST pushst; ST popst; } MyQueue; MyQueue* myQueueCreate() { MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("malloc fail\n"); return NULL; } STInit(&obj->pushst); STInit(&obj->popst); return obj; } void myQueuePush(MyQueue* obj, int x) { STPush(&obj->pushst,x); } int myQueuePop(MyQueue* obj) { int front= myQueuePeek(obj); STPop(&obj->popst); return front; } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->popst)) { while(!STEmpty(&obj->pushst)) { STPush(&obj->popst,STTop(&obj->pushst)); STPop(&obj->pushst); } } return STTop(&obj->popst); } bool myQueueEmpty(MyQueue* obj) { assert(obj); return STEmpty(&obj->pushst)&&STEmpty(&obj->popst); } void myQueueFree(MyQueue* obj) { STDestory(&obj->pushst); STDestory(&obj->popst); free(obj); }
设计循环队列
题目链接:力扣(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)]这段代码是为了返回队尾元素。
代码如下:
typedef struct { int front; int rear; int k; int*a; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->rear=0; obj->k=k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1)==obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if( myCircularQueueIsFull(obj)) return false; obj->a[obj->rear]=value; obj->rear++; obj->rear=(obj->rear)%(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front=(obj->front)%(obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[(obj->rear+obj->k)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
栈与队列的内容到这里就结束了,下节开始学习堆与二叉树,
未完待续。。。