一、前言
前面学习了栈与队列的相关知识，及其基本实现。今天我们就来看看他们在题目中的应用吧。
此篇博客仅记录博主自己学习的一些有关栈与队列的基础OJ题，分享自己的做题过程和想法，如有错误，还请各位指出，这样能帮助我进步，谢谢。
话不多说，那我们就直接开始吧。
二、用队列实现栈
题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。实现 MyStack 类：
1、void push(int x) 将元素 x 压入栈顶。
2、int pop() 移除并返回栈顶元素。
3、int top() 返回栈顶元素。
4、boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
思路：
代码如下：
typedef int Datatype; typedef struct QueueNode { struct QueueNode* next; Datatype data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //销毁 void QueueDestory(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //队尾入队列 void QueuePush(Queue* pq, Datatype x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc is fail\n"); 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; } } //队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); QNode* cur = pq->head->next; if (cur == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { free(pq->head); pq->head = cur; } } //取队头的数据 Datatype QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } //取队尾的数据 Datatype QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; } //计算数据的个数 Datatype Queuesize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { cur = cur->next; size++; } return size; } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* st = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&st->q1); QueueInit(&st->q2); return st; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { Queue* EmptyQ = &obj->q1; Queue* NoEmptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { EmptyQ = &obj->q2; NoEmptyQ = &obj->q1; } while(Queuesize(NoEmptyQ) > 1) { QueuePush(EmptyQ, QueueFront(NoEmptyQ)); QueuePop(NoEmptyQ); } int top = QueueFront(NoEmptyQ); QueuePop(NoEmptyQ); 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) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); }
三、用栈实现队列
题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。实现 MyQueue 类：
1、void push(int x) 将元素 x 推到队列的末尾。
2、int pop() 从队列的开头移除并返回元素。
3、int peek() 返回队列开头的元素。
4、boolean empty() 如果队列为空，返回 true ；否则，返回 false。
思路：
代码如下：
//初始化 void StackInit(SK* ps) { assert(ps); ps->top = 0;//每次指向栈顶的下一个 Datatype* newnode = (Datatype*)malloc(sizeof(Datatype) * 4); if (newnode == NULL) { printf("malloc fail"); exit(-1); } else { ps->a = newnode; } ps->size = 4; } //销毁 void StackDestory(SK* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->size = 0; } //入栈 void StackPush(SK* ps, Datatype x) { assert(ps); //满了就扩容 if (ps->top == ps->size) { Datatype* newnode = (Datatype*)realloc(ps->a, ps->size * 2 * sizeof(Datatype)); if (newnode == NULL) { printf("realloc fail"); exit(-1); } else { ps->a = newnode; ps->size *= 2; } } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(SK* ps) { assert(ps); //如果栈空了还去调用Delete就直接报错 assert(ps->top > 0); ps->top--; } //取栈顶元素 Datatype StackTop(SK* ps) { assert(ps); //如果栈空了还去调用Top就直接报错 assert(ps->top > 0); return ps->a[ps->top - 1]; } //求数据个数 Datatype StackNum(SK* ps) { return ps->top; } //判空 bool StackEmpty(SK* ps) { assert(ps); return ps->top == 0; } typedef struct { SK pushSK; SK popSK; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->pushSK); StackInit(&obj->popSK); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushSK, x); } int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->popSK)) { while(!StackEmpty(&obj->pushSK)) { StackPush(&obj->popSK, StackTop(&obj->pushSK)); StackPop(&obj->pushSK); } } int top = StackTop(&obj->popSK); StackPop(&obj->popSK); return top; } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popSK)) { while(!StackEmpty(&obj->pushSK)) { StackPush(&obj->popSK, StackTop(&obj->pushSK)); StackPop(&obj->pushSK); } } return StackTop(&obj->popSK); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushSK) && StackEmpty(&obj->popSK); } void myQueueFree(MyQueue* obj) { StackDestory(&obj->pushSK); StackDestory(&obj->popSK); free(obj); }
四、括号匹配
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 每个右括号都有一个对应的相同类型的左括号。
思路：这道题就可以使用我们学到的栈数据结构了。遍历字符串，如果是左括号就入栈，如果是右括号，就取栈顶元素与其进行比较判断。如果匹配就继续遍历，直到结束。一旦有不匹配就直接结束，返回false。如果最后栈为空了，就返回true。
代码实现如下：(栈的实现见题目二中)
bool isValid(char* s) { SK sk; StackInit(&sk); while(*s) { if(*s == '(' || *s == '[' || *s == '{') { StackPush(&sk, *s); s++; } else { if(StackEmpty(&sk))//如果第一个就是右括号，那么栈为空，直接返回false { StackDestory(&sk);//防止内存泄漏 return false; } Datatype top = StackTop(&sk); StackPop(&sk); if( (top == '(' && *s == ')') || (top == '{' && *s == '}') || (top == '[' && *s == ']') ) { s++; } else { StackDestory(&sk);//防止内存泄漏 return false; } } } bool ret = StackEmpty(&sk); StackDestory(&sk); return ret; }
五、设计循环队列
题目描述：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
* MyCircularQueue(k): 构造器，设置队列长度为 k 。
* Front: 从队首获取元素。如果队列为空，返回 -1 。
* Rear: 获取队尾元素。如果队列为空，返回 -1 。
* enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
* deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
* isEmpty(): 检查循环队列是否为空。
* isFull(): 检查循环队列是否已满。
思路：用数组实现更加方便。
解题代码：
typedef struct { int* a; int head; int tail; int k; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = malloc(sizeof(int) * (k+1)); obj->head = obj->tail = 0; obj->k = k; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->tail] = value; obj->tail++; if(obj->tail == obj->k+1) obj->tail = 0; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->head++; if(obj->head == obj->k + 1) obj->head = 0; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; int prev = obj->tail-1; if(prev == -1) prev = obj->k; return obj->a[prev]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head == obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { int next = obj->tail + 1; if(next == obj->k+1) next = 0; return next == obj->head; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
六、结尾
以上四个题就是今天的全部内容了。三个题充分体现出了栈和队列这两种特殊的线性结构的特点。栈和队列依靠他们各自特殊的结构特点方便了人们的操作，简化了程序设计的问题。
