有效的括号
思路: 我们可以使用一个栈来解决这个问题, 我们用栈来存储左括号,当遇见右括号就取出栈顶元素出来比较,如果符合就继续匹配,否则就返回false, 或者最后栈还要数据,或者栈没有数据但还要右括号都是不匹配成功的
typedef char TackDataType; typedef struct Stack { TackDataType * a; int top; //栈顶元素 int capacity; }Stack; //初始化 void TackInit(Stack *pst) { assert(pst); pst->a = NULL; pst->top = -1; pst->capacity = 0; } // 入栈 void TackPush(Stack *pst, TackDataType elemest) { assert(pst); //判断是否满了 if ((pst->top) +1 == pst->capacity) { pst->capacity = (pst->capacity == 0? 4 : pst->capacity * 2); TackDataType* tmp = (TackDataType*)realloc(pst->a,sizeof(Stack) * pst->capacity); if (tmp == NULL) { perror("realloc"); return; } pst->a = tmp; } pst->a[++(pst->top)] = elemest; } //出栈 void TackPop(Stack *pst) { assert(pst); if(pst->top != -1) pst->top--; } //长度 int TackSize(Stack *pst) { assert(pst); return (pst->top) + 1; } //是否为空 bool TackEmpty(Stack *pst) { assert(pst); return pst->top == -1; } //栈顶元素 TackDataType TackTop(Stack *pst) { assert(pst); return pst->a[pst->top]; } //释放 void TackDestroy(Stack *pst) { free(pst->a); pst->a = NULL; pst->top = -1; pst ->capacity = 0; } bool isValid(char* s) { Stack pst; //初始化 TackInit(&pst); while(*s) { if(*s == '{' || *s == '[' || *s == '(') { //入栈 TackPush(&pst, *s); } else { //是否为空 if (TackEmpty(&pst)) { TackDestroy(&pst); return false; } //栈顶元素 if ((*s == '}' && TackTop(&pst) == '{') || (*s == ']' && TackTop(&pst) == '[') ||(*s == ')' && TackTop(&pst) == '(')) { //出栈 TackPop(&pst); } else { return false; } } s++; } //是否为空 if (!TackEmpty(&pst)) { TackDestroy(&pst); return false; } TackDestroy(&pst); return true; }
用队列实现栈
这道题主要的就是在删除和插入数据中要下点功夫,
插入: 我们只需往不为空的队列插入,因为这样必定有一个队列为空,如果刚开始两个队列都为空,我们只需随意插入一个队列就行
删除: 我们删除栈的栈顶元素,是直接删除最新插入的元素,而队列的特点就是先进先出,我们可以借助空队列把非空队列的最后一个元素保留下来,然后把多余的元素插入到空队列中,需要注意的是,插入的最后一个元素的下一个next一定要修改为NULL,不然在释放会有野指针,然后保留的最后一个元素再free掉,
剩下的就是释放空间:
我们要先释放掉链表的空间,然后再释放两个队列的空间,
删除:
typedef int QDataType; //链表节点 typedef struct QNode { QDataType val; struct QNode *next; }QNode; //队列结构 typedef struct Queue { QNode* head; QNode* tail; //队尾 int size; }Queue; //创建两个队列 typedef struct { Queue stack1; Queue stack2; } MyStack; MyStack* myStackCreate() { //创建两个队列 MyStack * Queuetack = (MyStack*)malloc(sizeof(MyStack)); //创建哨兵位 Queuetack->stack1.head = (QNode*)malloc(sizeof(QNode)); Queuetack->stack1.head->next = NULL; Queuetack->stack1.size = 0; Queuetack->stack1.tail = Queuetack->stack1.head; //创建哨兵位 Queuetack->stack2.head = (QNode*)malloc(sizeof(QNode)); Queuetack->stack2.head->next = NULL; Queuetack->stack2.size = 0; Queuetack->stack2.tail = Queuetack->stack2.head; return Queuetack; } void myStackPush(MyStack* obj, int x) { assert(obj); if (obj->stack2.size) { //创建节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->val = x; newnode->next = NULL; //插入 obj->stack2.tail->next = newnode; obj->stack2.tail = newnode; obj->stack2.size++; } else { //创建节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->val = x; newnode->next = NULL; //插入 obj->stack1.tail->next = newnode; obj->stack1.tail = newnode; obj->stack1.size++; } } int myStackPop(MyStack* obj) { if (!obj->stack2.size && !obj->stack1.size) return 0; if (obj->stack2.size) { while (obj->stack2.head->next != obj->stack2.tail) { QNode* node = obj->stack2.head->next; obj->stack2.head->next = node->next; obj->stack1.tail->next = node; obj->stack1.tail = node; obj->stack1.size++; } obj->stack1.tail->next = NULL; int a = obj->stack2.tail->val; free(obj->stack2.tail); obj->stack2.tail = obj->stack2.head; obj->stack2.head->next = NULL; obj->stack2.size = 0; return a; } else { while (obj->stack1.head->next != obj->stack1.tail) { QNode* node = obj->stack1.head->next; obj->stack1.head->next = node->next; obj->stack2.tail->next = node; obj->stack2.tail = node; obj->stack2.size++; } obj->stack2.tail->next = NULL; int a = obj->stack1.tail->val; free(obj->stack1.tail); obj->stack1.tail = obj->stack1.head; obj->stack1.head->next = NULL; obj->stack1.size = 0; return a; } } int myStackTop(MyStack* obj) { if (!obj->stack2.size && !obj->stack1.size) return 0; if (!obj->stack2.size) { return obj->stack1.tail->val; } else { return obj->stack2.tail->val; } } bool myStackEmpty(MyStack* obj) { return obj->stack2.size== 0 && obj->stack1.size ==0; } void myStackFree(MyStack* obj) { QNode *cur = obj->stack1.head->next; while(cur) { QNode *cur1 = cur->next; free(cur); cur = cur1; } free(obj->stack1.head); obj->stack1.head = NULL; obj->stack1.size = 0; obj->stack1.tail = NULL; cur = obj->stack2.head->next; while(cur) { QNode *cur1 = cur->next; free(cur); cur = cur1; } free(obj->stack2.head); obj->stack2.head = NULL; obj->stack2.size = 0; obj->stack2.tail = NULL; free(obj); }
用栈实现队列
结构：
这道题的思路和上面的题目思路是相同的,我们借助两个栈来实现队列,
有点差别就是
插入：
我们插入要插入到stack1那里去，
删除:
如果stack2为空，我们就要把stack1的数据插入stack2，如果stack2有数据可以先删除stack2的数据，直到为空，然后再把stack1的数据插入到stack2里面去
查找头：
如果stack2为空，我们就要把stack1的数据插入stack2，如果stack2有数据可以先查找stack2的数据
删除我们不能从top那边开始拉数据,而是要从left开始,
我们还要注意的就是队列插入的时候一定判断 栈是否要扩大空间,
typedef int StackDAtaType; typedef struct Stack { StackDAtaType *data; int top;//栈顶元素下一个 int capacity; }Stack; typedef struct { Stack stack1; Stack stack2; } MyQueue; MyQueue* myQueueCreate() { //初始化 MyQueue *queue = (MyQueue*)malloc(sizeof(MyQueue)); //第一个栈 queue->stack1.data = NULL; queue->stack1.top = 0;//栈顶元素的下一个 queue->stack1.capacity = 0; //第二个栈 queue->stack2.data = NULL; queue->stack2.top = 0; queue->stack2.capacity = 0; return queue; } void myQueuePush(MyQueue* obj, int x) { //第一个栈插入 //判断是否满栈 if(obj->stack1.top == obj->stack1.capacity) { obj->stack1.capacity = (obj->stack1.capacity == 0 ? 4 : obj->stack1.capacity * 2); StackDAtaType *tmp = (StackDAtaType*)realloc(obj->stack1.data, sizeof(StackDAtaType) * obj->stack1.capacity); if (tmp == NULL) { perror("realloc"); return ; } obj->stack1.data = tmp; } obj->stack1.data[obj->stack1.top++] = x; } int myQueuePeek(MyQueue* obj) { if(!obj->stack2.top && !obj->stack1.top) return 0; if(obj->stack2.top) { return obj->stack2.data[obj->stack2.top -1]; } else { //取出第一栈的元素 插入到第二栈 while (obj->stack1.top) { //判断是否满栈 if (obj->stack2.top == obj->stack2.capacity) { obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2); StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity); if (tmp == NULL) { perror("realloc"); return 0; } obj->stack2.data = tmp; } obj->stack2.data[obj->stack2.top++] = obj->stack1.data[--obj->stack1.top]; } return obj->stack2.data[obj->stack2.top - 1]; } } int myQueuePeek(MyQueue* obj) { if(!obj->stack2.top && !obj->stack1.top) return 0; if(obj->stack2.top) { return obj->stack2.data[obj->stack2.top -1]; } else { //取出第一栈的元素 插入到第二栈 while (obj->stack1.top) { //判断是否满栈 if (obj->stack2.top == obj->stack2.capacity) { obj->stack2.capacity = (obj->stack2.capacity == 0 ? 4 : obj->stack2.capacity * 2); StackDAtaType* tmp = (StackDAtaType*)realloc(obj->stack2.data, sizeof(StackDAtaType) * obj->stack2.capacity); if (tmp == NULL) { perror("realloc"); return 0; } obj->stack2.data = tmp; } obj->stack2.data[obj->stack2.top++] = obj->stack1.data[--obj->stack1.top]; } return obj->stack2.data[obj->stack2.top - 1]; } } bool myQueueEmpty(MyQueue* obj) { return obj->stack1.top == 0 && obj->stack2.top == 0; } void myQueueFree(MyQueue* obj) { free(obj->stack1.data); obj->stack1.data = NULL; obj->stack1.top = 0; obj->stack1.capacity = 0; free(obj->stack2.data); obj->stack2.data = NULL; obj->stack2.top = 0; obj->stack2.capacity = 0; free(obj); }
循环队列
这道题主要就是判断空和满的情况
主要有顺序表和链表,
顺序表:
这里我们使用front指向队头,back指向队尾的下一个,当front和back相等就为空,但是如果顺序表只有一个元素,就会无法判断，那我们可以多创建一个空间，
当back+1等于front就是满的情况，由于是循环队列，back的值要使用（back+1 +k+1）%（k+1）
typedef struct { int *list; int front; int back; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue * obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); obj->list = (int*)malloc(sizeof(int) * (k + 1)); //多开创一个空间 obj->front = 0; obj->back = 0; //指向尾的下一个 obj->k = k + 1; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if ((obj->back + 1) % (obj->k) != obj->front) { obj->list[obj->back] = value; obj->back = (obj->back + 1 + obj->k) % (obj->k); return true; } return false; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj->back == obj->front) return false; obj->front = (obj->front + 1 + obj->k) % (obj->k); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(obj->back == obj->front) return -1; return obj->list[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(obj->back == obj->front) return -1; return obj->list[(obj->back-1 + obj->k) %(obj->k)]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->back == obj->front; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back + 1) % (obj->k) == obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->list); free(obj); }
链表：我们也可以通过类似的方法来，但是我们如果要找到队尾节点，就要标记好，如果是使用双向链表就可以不用标记
typedef int DataType; typedef struct ListNode1 { DataType val; struct ListNode1 *next; } ListNode; typedef struct { ListNode * head; ListNode* back; ListNode* tail; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { //创建一个循环队列 MyCircularQueue *obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->head = NULL; obj->back = NULL; obj->tail =NULL; int i= 0; for (i = 0; i < k+1; i++) { //创建节点 ListNode *newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->next = NULL; if(obj->tail == NULL) { obj->head = newnode; obj->back = newnode; obj->tail = newnode; } else { obj->tail->next = newnode; obj->tail = obj->tail->next; } } obj->tail->next = obj->head; obj->tail = obj->back; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(obj->head != obj->back->next) { obj->back->val = value; obj->tail = obj->back; obj->back = obj->back->next; return true; } return false; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { //为空返回false if(obj->head == obj->back) { return false; } obj->head = obj->head->next; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(obj->head == obj->back) { return -1; } return obj->head->val; } int myCircularQueueRear(MyCircularQueue* obj) { if(obj->head == obj->back) { return -1; } return obj->tail->val; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(myCircularQueueRear(obj) == -1) return true; return false; } bool myCircularQueueIsFull(MyCircularQueue* obj) { if(obj->head != obj->back->next) { return false; } return true; } void myCircularQueueFree(MyCircularQueue* obj) { ListNode *p = obj->tail->next; while(obj->back != p) { ListNode *pnode = obj->back->next; free(obj->back); obj->back = pnode; free(obj); } }
总结
这些题目主要还是考察我们对队列和栈的熟悉程度
