手撕算法题3 (附源码和思路)

1.有效的括号

有效的括号

思路
借助栈这样的数据结构，将所有左括号进行入栈，所有右括号与出栈的括号比较，相同循环继续，不同直接返回false。循环结束后检查栈是否为空，为空说明已经全部匹配了，若栈不为空说明并没有一一对应返回false，以上都没问题返回true。

---

设计程序
定义一个栈，字符串遍历若是左括号则入栈字符++，否则取栈顶元素出栈与此时的字符比较

（当然比较的条件这里我是用ASCII码写的，因为我查表发现它们的ASCII码差只为1或2），
注意取栈顶元素一定要栈不为空（如果此时栈为空说明绝对不匹配）

遍历完字符串，若果都一一对应了栈应该为空否则就不匹配，判断一下进行相应返回就行

---

编写代码

typedef char STDataType;
typedef struct Stack {STDataType* arr;int capacity; // 栈的空间大小int top;      // 栈顶
} ST;
void STInitialise(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}void STDestroy(ST* ps) {assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}void StackPush(ST* ps, STDataType x) {assert(ps);// 判断空间是否充足if (ps->top == ps->capacity) {// 增容//0*2 = 0// 若capacity为0，给个默认值，否则×2倍int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp =(STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = NewCapacity;}ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps) {if (ps->top) {return true;}return false;
}void StackPop(ST* ps) {assert(ps);assert(StackEmpty(ps));ps->top--;
}STDataType StackTop(ST* ps) {assert(ps);assert(StackEmpty(ps));return ps->arr[ps->top - 1];
}
//
bool isValid(char* s) {char*tmp=s;ST ps;STInitialise(&ps);while(*tmp){if(*tmp=='('||*tmp=='{'||*tmp=='['){StackPush(&ps,*tmp);}else{if(!StackEmpty(&ps))return false;char top=StackTop(&ps);StackPop(&ps);if(*tmp-top!=1&&*tmp-top!=2)return false;}tmp++;}if(StackEmpty(&ps))return false;return true;
}

---

2.用队列实现栈

用队列实现栈

思路

---

设计程序

借助两个队列实现栈
在不为空的队列中入数据（都为空我们默认在q2入数据），
出栈我们定义好空栈和非空栈（会变化），将非空栈的size-1个元素导入空栈中，取空栈栈顶元素出栈
取栈顶元素直接返回非空队列的队尾元素

---

编写代码

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;
void QueueInitialise(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->phead == NULL && pq->ptail == NULL){return false;}return true;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));if (NewNode == NULL){perror("malloc fail!");exit(1);}NewNode->data = x;NewNode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = NewNode;}else{pq->ptail->next = NewNode;pq->ptail = NewNode;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(QueueEmpty(pq));QueueNode* Next = pq->phead->next;if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}free(pq->phead);pq->phead = NULL;pq->phead = Next;pq->size--;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(QueueEmpty(pq));return pq->ptail->data;
}
int QueueSize(Queue* pq)
{assert(pq);/*size_t size = 0;QueueNode* pcur = pq->phead;while (pcur){size++;pcur = pcur->next;}*/return pq->size;
}
void QueueDestroy(Queue* pq)
{assert(pq);//assert(QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* Next = pcur->next;free(pcur);pcur = Next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(QueueEmpty(pq));return pq->phead->data;
}
///
typedef struct{Queue q1;Queue q2;
}MyStack;
MyStack* myStackCreate() {MyStack*pst=(MyStack*)malloc(sizeof(MyStack));QueueInitialise(&pst->q1);QueueInitialise(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {//找不为空的队列Queue*empQ=&obj->q1;Queue*noneQ=&obj->q2;if(QueueEmpty(&obj->q1)){noneQ=&obj->q1;empQ=&obj->q2;}while(QueueSize(noneQ)>1){int front=QueueFront(noneQ);QueuePush(empQ,front);QueuePop(noneQ);}int pop=QueueFront(noneQ);QueuePop(noneQ);return pop;
}int myStackTop(MyStack* obj) {if(QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}return QueueBack(&obj->q2);
}bool myStackEmpty(MyStack* obj) {return !QueueEmpty(&obj->q1)&&!QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj=NULL;
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

---

3.用栈实现队列

用栈实现队列

思路

这样就实现了队列的先进先出了，程序思路大体与上述相同不过简单的是我们空队列和非空列是固定的。

---

编写代码

typedef int STDataType;
typedef struct Stack
{STDataType*arr;int capacity;//栈的空间大小int top;//栈顶
}ST;
void STInitialise(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}void STDestroy(ST* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}void StackPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否充足if (ps->top == ps->capacity){//增容//0*2 = 0//若capacity为0，给个默认值，否则×2倍int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = NewCapacity;}ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps)
{if (ps->top){return true;}return false;
}void StackPop(ST* ps)
{assert(ps);assert(StackEmpty(ps));ps->top--;
}STDataType StackTop(ST* ps)
{assert(ps);assert(StackEmpty(ps));return ps->arr[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}
//typedef struct {ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*pst=(MyQueue*)malloc(sizeof(MyQueue));STInitialise(&pst->pushST);STInitialise(&pst->popST);return pst;
}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 ret=StackTop(&obj->popST);StackPop(&obj->popST);return ret;
}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) {STDestroy(&obj->pushST);STDestroy(&obj->popST);free(obj);obj=NULL;}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

---

3.设计循环队列

设计循环队列

思路
用数组实现循环队列，因为数组连续且不像链表需要自己去连接。其次数组实现的循环队列标识队列已满好实现，而链表实现的循环队列标识队列已满不好实现。

这就引出了这道题的难点怎么标识队列满了，接下来我们来实现

设计程序

rear=front时队列为空

（rear+1）%（capacity+1）==front我们表示为队列满了，比如我们队列的长度为4，多申请一个结点，当rare走到如图的黑色位置时（4+1）%(4+1)=0等于front此时就为空了，但是不是说当rare走到这个位置队列为满。
而是通过（rear+1）%（capacity+1）==front这个公式来判断是否为满，随着front的改变（队头出数据会导致front++），哨兵位置也会改变，但是我们申请的空间一定有一个结点来标识哨兵位。
我们对front++，rear++可能会越界它是一个循环队列所以要%=capacity，同时返回队尾元素，一定是rear-1，当rear为0减应该对应的元素为capacity的位置，如果是跟着我博客学习的粉丝可能对这道题有点遗憾，因为我们用链表实现队列的时候是返回队尾数据就直接返回了，不需要-1，但是严格来说队列不是只能队尾入数据吗而不是取数据，所以队尾是插入数据的地方而不是取数据的地方，希望这些能对大家有所帮助，如果还不能理解的话可以咨询博主。

typedef struct {int*arr;int front;int rear;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->arr=(int*)malloc(sizeof(int)*(k+1));obj->rear=obj->front=0;obj->capacity=k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->capacity+1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->arr[obj->rear++]=value;obj->rear%=obj->capacity+1;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj->front++;obj->front%=obj->capacity+1;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;int prev = obj->rear-1;if(obj->rear==0)prev=obj->capacity;return obj->arr[prev];
}void myCircularQueueFree(MyCircularQueue* obj) {obj->capacity=obj->front=obj->rear=0;free(obj->arr);obj->arr=NULL;free(obj);obj=NULL;
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/