一、用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[ [ ], [1], [2], [ ], [ ], [ ] ]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
链接：https://leetcode-cn.com/problems/implement-stack-using-queues
1.题干分析
队列的特点---先进先出，后进后出；栈的特点---先进后出，后进先出； 用两个队列实现一个栈，那么他们入数据都是一样的，知识出数据的时候相反；为什么要用两个队列呢？假设q1和q2两个队列；q1队列用来入数据（入1,2,3,4），q2队列用来入q1队列的数据（就是依次取q1队列的队头的数据，入1,2,3），当q2队列只剩下一个数据（4）的时候，就把这个数据取出；数字4是后进队列的，此时取出就相当于数字4后进先出，这不就是栈的特点嘛。如果继续出数据，把q1里的数据入到q2里，当q1只剩下一个数据时，就出数据；那么两个队列实现一个栈就完成了；
如何创建一个栈呢？还要有两个队列呢？
我们之前在C语言实现的队列中，是这样定义的：
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head;//队头 QueueNode* tail;//队尾 }Queue;
题目中给了这样的代码：
typedef struct { } MyStack;
这是栈的结构体；栈是用两个队列实现的，那么栈里面肯定是需要两个队列来实现的；
typedef struct { Queue q1;//队列1 Queue q2;//队列2 } MyStack;
因为嵌套了几个结构体，很容易搞混，尤其是在调用的时候，下面是关系图：
2.动图解析
3.代码实现
在没有学习C++之前，用C语言实现这道题，我们可以将C语言实现的队列直接调过来 ；
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; //队列的初始化 void QueueInit(Queue* pq); //队列的销毁 void QueueDestroy(Queue* pq); //队尾入队列 void QueuePush(Queue* pq, QDataType x); // 队头出队列 void QueuePop(Queue* pq); //取队头的数据 QDataType QueueFront(Queue* pq); //取队尾的数据 QDataType QueueBack(Queue* pq); //计算有多少个数据 int QueueSize(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //队列的初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } //队列的销毁 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //队尾入队列(尾插） void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } // 队头出队列（删除数据） void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; free(pq->head); pq->head = next; //此时head和tail同时指向最后一个空间，释放head后，要注意也要把tail释放了 if (pq->head == NULL) { pq->tail = NULL; } } //取队头的数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } //取队尾的数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } //计算有多少个数据 int QueueSize(Queue* pq) { assert(pq); int n = 0; QueueNode* cur = pq->head; while (cur) { ++n; cur = cur->next; } return n; } //判断队列是否为空 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* noneemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; noneemptyQ = &obj->q1; } while(QueueSize(noneemptyQ) > 1) { QueuePush(emptyQ,QueueFront(noneemptyQ)); QueuePop(noneemptyQ); } int top = QueueFront(noneemptyQ); QueuePop(noneemptyQ); 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); }.
二、有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = " ( ) "
输出：true
示例 2：
输入：s = " ( ) [ ] { } "
输出：true
示例 3：
输入：s = " ( ] "
输出：false
示例 4：
输入：s = " ( [ ) ] "
输出：false
示例 5：
输入：s = " { [ ] } "
输出：true
链接：https://leetcode-cn.com/problems/valid-parentheses
1.题干分析
本题向要表达的意思就是给定了一个含有左右括号的字符串，如果形如‘（ ）’则为有效，形如‘（ }’则为无效；我们该如何入手呢？，我们可以用栈的特点来实现，先进栈的左括号后匹配，配对成功则删除这对括号，直至全部匹配成功；
2.动图解析
3.代码实现
typedef char STDataType; typedef struct Stack { STDataType* a; int top;//栈顶 int capacity; }ST; //栈的初始化 void StackInit(ST* ps); //栈的销毁 void StackDestroy(ST* ps); //栈的栈顶插入 void StackPush(ST* ps, STDataType x); //栈的删除 void StackPop(ST* ps); //取栈顶的数据 STDataType StackTop(ST* ps); //栈的元素个数 int StackSize(ST* ps); //判断栈是不是空 bool StackEmpty(ST* ps); //栈的初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //栈的销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //栈的栈顶插入 void StackPush(ST* ps, STDataType x) { assert(ps); if (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) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } //栈的删除 void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } //取栈顶的数据 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } //栈的元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; } //判断栈是不是空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } bool isValid(char * s){ ST st; StackInit(&st); while(*s) { //入左括号 if(*s == '(' || *s== '{' || *s== '[') { StackPush(&st,*s); ++s; } else { //遇到右括号，但是栈里面没有数据，说明前面没有左括号，不匹配 if(StackEmpty(&st)) { StackDestroy(&st); return false; } //取栈顶的数据，进行比对 STDataType top = StackTop(&st); StackPop(&st); if((*s == ')' && top != '(') ||(*s == '}' && top != '{') ||(*s == ']' && top != '[')) { StackDestroy(&st); return false; } else { s++; } } } //如果不是空，说明还有左括号未出； //没有匹配返回的是false bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
