栈和队列相关|有效的括号|用队列实现栈|用栈实现队列|设计循环队列(C)

20. 有效的括号

---

判断左右括号是否匹配，匹配返回true，不匹配返回false
通过栈来实现，类型和顺序，数量都要匹配
控制数量通过size
每个右括号都要找最近的左括号去判断类型匹配不匹配，顺序匹配不匹配
最后来判断数量匹配不匹配

1. 左括号，入栈
2. 右括号，出栈顶括号，进行匹配

栈接口

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);// 11:40if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);// assert(ps->top > 0);--ps->top;
}STDataType STTop(ST* ps)
{assert(ps);// assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

if版本

bool isValid(char * s){ST st;STInit(&st);char top;while(*s){if (*s == '[' || *s == '(' || *s == '{'){STPush(&st, *s);}else{//数量不匹配if (STEmpty(&st)){STDestroy(&st);return false;}top = STTop(&st);STPop(&st);//顺序不匹配if((*s == ']' && top != '[')|| (*s == ')' && top != '(')|| (*s == '}' && top != '{')){STDestroy(&st);return false;}}++s;}// 栈不为空，false，说明数量不匹配bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

switch版本

bool isValid(char * s){ST st;STInit(&st);char top;while (*s){switch(*s){case '[':case '(':case '{':STPush(&st, *s);break;case '}':// 数量不匹配if (STEmpty(&st))return false;top = STTop(&st);STPop(&st);// 顺序不匹配if (top != '{')return false;break;case ']':// 数量不匹配if (STEmpty(&st))return false;top = STTop(&st);STPop(&st);//顺序不匹配if (top != '[')return false;break;case ')':// 数量不匹配if (STEmpty(&st))return false;top = STTop(&st);STPop(&st);//顺序不匹配if (top != '(')return false;break;}++s;}//数量不匹配bool ret = STEmpty(&st);STDestroy(&st);return ret;
}

225. 用队列实现栈

---

用两个队列实现栈

Push 1 2 3 4

Pop 4
分别出1 2 3，插入到另一个队列，最后剩下4，把最后一个数据Pop掉

Push 5 6
入到不为空的那个队列里

空队列是用来倒数据的

Pop 6

入队列：不为空的队列
出队列：不为空队列前N-1个出队列，插入空队列；删除剩余数据

队列接口

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

队列实现栈

typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&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) {Que* empty = &obj->q1;Que* nonempty = &obj->q2;if (!QueueEmpty(&obj->q1)){nonempty = &obj->q1;empty = &obj->q2;}while(QueueSize(nonempty) > 1){// 前size-1个导入空队列QueuePush(empty, QueueFront(nonempty));QueuePop(nonempty);}int top = QueueFront(nonempty);QueuePop(nonempty);return top;
}int myStackTop(MyStack* obj) {if (!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{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);
}

232. 用栈实现队列

---

用两个栈来实现队列
Push 1 2 3 4

Pop 1
把数据往另一个栈里倒

Push 5 6

存数据的栈称为pushst，出数据的栈称为popst

栈接口

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);// 11:40if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);// assert(ps->top > 0);--ps->top;
}STDataType STTop(ST* ps)
{assert(ps);// assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

栈实现队列

typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->pushst);STInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst, x);
}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);
}int myQueuePop(MyQueue* obj) {int front = myQueuePeek(obj);STPop(&obj->popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->popst);STDestroy(&obj->pushst);free(obj);
}

622. 设计循环队列

---

循环队列
Pop 1

Push 5

Pop 2

Push 6

当队列为空

front和rear相等，队列为空
插入一个数据，rear往后走
rear不是指向最后一个数据，而是指向最后一个数据的下一个位置

如何判断队列满

多开一个空间
k == 4，表示队列只能存四个数

front == rear 空
rear的下一个就是front 满

• rear在中间的情况
  

(rear + 1)% (k + 1) == front

取队尾

(rear + (k + 1) - 1) % (k + 1)

循环队列实现

typedef struct {int* a;int front;int rear;int k;
} 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->k + 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front %= (obj->k + 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;else//(rear + (k + 1) - 1) % (k + 1)return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}