OJ题
1.有效的括号
链接：20. 有效的括号
描述：
给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例1：
输入：s = “()”
输出：true
示例2：
输入：s = “()[]{}”
输出：true
示例3：
输入：s = “(]”
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
1.1 思路：
这道题目的解题思路是十分符合 栈 的。
首先，我们先要实现一个栈，并创建变量和初始化。题目要求 左括号 需要以正确的顺序闭合，且左右括号成对，那么我们可以遍历字符串s。
遍历过程中让 左括号入栈，一旦遇到 右括号 便 取栈顶元素 和右括号匹配，并 出栈元素。
这道题目的解题思路是十分符合 栈 的。
首先，我们先要实现一个栈，并创建变量和初始化。题目要求 左括号 需要以正确的顺序闭合，且左右括号成对，那么我们可以遍历字符串s。
遍历过程中让 左括号入栈，一旦遇到 右括号 便 取栈顶元素 和右括号匹配，并 出栈元素。
1.2 易错情况
1.字符串遍历结束，栈中仍有元素：
输入：s = “() [] {”
输出：false
2.只有右括号，无左括号，栈空，取元素时越界访问：
输入：s = “) ] }”
输出：false
注：只有右括号时为提前返回状况。提前返回需要注意栈的销毁，否则会内存泄漏 ！内存泄漏不会报错，一定要仔细！[如果在公司里面就可能造成事故，奖金没了(bushi) ]
typedef char STDataType;//栈中存储的元素类型 typedef struct Stack { STDataType* a;//栈 int top;//栈顶 int capacity;//容量，方便增容 }Stack; //初始化栈 void StackInit(Stack* pst) { assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素 pst->top = 0;//初始时栈中无元素，栈顶为0 pst->capacity = 4;//容量为4 } //销毁栈 void StackDestroy(Stack* pst) { assert(pst); free(pst->a);//释放栈 pst->a = NULL;//及时置空 pst->top = 0;//栈顶置0 pst->capacity = 0;//容量置0 } //入栈 void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity)//栈已满，需扩容 { STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capacity *= 2;//栈容量扩大为原来的两倍 } pst->a[pst->top] = x;//栈顶位置存放元素x pst->top++;//栈顶上移 } //检测栈是否为空 bool StackEmpty(Stack* pst) { assert(pst); return pst->top == 0; } //出栈 void StackPop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 pst->top--;//栈顶下移 } //获取栈顶元素 STDataType StackTop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 return pst->a[pst->top - 1];//返回栈顶元素 } //获取栈中有效元素个数 int StackSize(Stack* pst) { assert(pst); return pst->top;//top的值便是栈中有效元素的个数 } /*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/ bool isValid(char * s){ Stack st;//创建一个栈 StackInit(&st);//初始化栈 char* cur = s;//cur用于遍历字符串 while(*cur) { if(*cur == '('||*cur == '{'||*cur == '[')//前括号统一入栈 { StackPush(&st, *cur); cur++; } else { if(StackEmpty(&st))//若遇到后括号，且栈为空，则字符串无效 { StackDestroy(&st); return false; } char top = StackTop(&st);//获取栈顶元素 if((top == '('&&*cur != ')') ||(top == '{'&&*cur != '}') ||(top == '['&&*cur != ']'))//后括号与栈顶的前括号不匹配 { StackDestroy(&st); return false; } else//匹配 { StackPop(&st); cur++; } } } bool ret = StackEmpty(&st);//检测栈是否为空 StackDestroy(&st); return ret;//栈为空返回true，栈不为空返回false }
2.用队列实现栈
描述：
请你仅使用两个队列实现一个后入先出（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
提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
2.1思路：
队列 是 先进先出，栈 是 后进先出，要用队列实现栈，那么就要使用两个队列完成后进先出的操作。
栈的结构设计就是两个队列 q1、q2。而实现栈，我们的重点就在于 后进先出。
可以这样思考：
1.1 我们需要时刻需要保持一个队列为空。
1.2 入数据时，往不为空的队列入数据，如果两个队列都为空，则入任意一个。
出数据时，将不为空的队列中的元素转移到空队列中直到队列中元素只剩一个，出栈原先非空队列的数据，原先非空队列变为空，出栈数据就是模拟栈的栈顶数据。
typedef int QDataType;//队列中存储的元素类型 typedef struct QListNode { struct QListNode* next;//指针域 QDataType data;//数据域 }QListNode; typedef struct Queue { QListNode* head;//队头 QListNode* tail;//队尾 }Queue; //初始化队列 void QueueInit(Queue* pq) { assert(pq); //起始时队列为空 pq->head = NULL; pq->tail = NULL; } //销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QListNode* cur = pq->head;//接收队头 //遍历链表，逐个释放结点 while (cur) { QListNode* next = cur->next; free(cur); cur = next; } pq->head = NULL;//队头置空 pq->tail = NULL;//队尾置空 } //队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申请新结点 if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x;//新结点赋值 newnode->next = NULL;//新结点指针域置空 if (pq->head == NULL)//队列中原本无结点 { pq->head = pq->tail = newnode;//队头、队尾直接指向新结点 } else//队列中原本有结点 { pq->tail->next = newnode;//最后一个结点指向新结点 pq->tail = newnode;//改变队尾指针指向 } } //检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//检测队列是否为空 if (pq->head->next == NULL)//队列中只有一个结点 { free(pq->head); pq->head = NULL; pq->tail = NULL; } else//队列中有多个结点 { QListNode* next = pq->head->next; free(pq->head); pq->head = next;//改变队头指针指向 } } //获取队列头部元素 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); QListNode* cur = pq->head;//接收队头 int count = 0;//记录结点个数 while (cur)//遍历队列 { count++; cur = cur->next; } return count;//返回队列中的结点数 } /*---以上代码是队列的基本功能实现，以下代码是题解主体部分---*/ typedef struct { Queue q1;//第一个队列 Queue q2;//第二个队列 } MyStack; /** Initialize your data structure here. */ MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//申请一个MyStack类型的栈 QueueInit(&pst->q1);//初始化第一个队列 QueueInit(&pst->q2);//初始化第二个队列 return pst; } /** Push element x onto stack. */ void myStackPush(MyStack* obj, int x) { //数据压入非空的那个队列 if (!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } /** Removes the element on top of the stack and returns that element. */ int myStackPop(MyStack* obj) { Queue* pEmpty = &obj->q1;//记录空队列 Queue* pNoEmpty = &obj->q2;//记录非空队列 if (!QueueEmpty(&obj->q1))//&obj->q1 q1,q2是结构体，结构体传参取地址& { pEmpty = &obj->q2; pNoEmpty = &obj->q1; } while (QueueSize(pNoEmpty) > 1)//pEmpty,pNoEmpty本身就是结构体的指针了，指针传参不用取地址了，可以直接传 { QueuePush(pEmpty, QueueFront(pNoEmpty)); QueuePop(pNoEmpty); }//将非空队列中的数据放入空队列中，只留下一个数据 int front = QueueFront(pNoEmpty);//获取目标数据 QueuePop(pNoEmpty);//删除目标数据 return front; } /** Get the top element. */ int myStackTop(MyStack* obj) { //获取非空队列的队尾数据 if (!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } /** Returns whether the stack is empty. */ bool myStackEmpty(MyStack* obj) { //两个队列均为空，则MyStack为空 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1);//释放第一个队列 QueueDestroy(&obj->q2);//释放第二个队列 free(obj);//释放MyStack }
3.用栈实现队列
描述：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
思路：
队列 要求先进先出，而 栈 为后进先出。
我们将队列的结构设定为两个栈，接下来思考该如何实现操作？
我们把两个栈分别叫做 pushST 和 popST。
1.当入队列时，就把数据入到 pushST 中。
2.当出队列时，如果 popST 中无数据，就把 pushST 中元素导入 popST 中，出栈；如果有数据则直接出栈。
这样就保证了入队列数据在 pushST 中，只要出队列，那么就把元素全部导入 popST 中出掉，栈在出数据时会改变顺序，恰好就对应了队列的规律。
typedef int STDataType;//栈中存储的元素类型 typedef struct Stack { STDataType* a;//栈 int top;//栈顶 int capacity;//容量，方便增容 }Stack; //初始化栈 void StackInit(Stack* pst) { assert(pst); pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素 pst->top = 0;//初始时栈中无元素，栈顶为0 pst->capacity = 4;//容量为4 } //销毁栈 void StackDestroy(Stack* pst) { assert(pst); free(pst->a);//释放栈 pst->a = NULL;//及时置空 pst->top = 0;//栈顶置0 pst->capacity = 0;//容量置0 } //入栈 void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst->top == pst->capacity)//栈已满，需扩容 { STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } pst->a = tmp; pst->capacity *= 2;//栈容量扩大为原来的两倍 } pst->a[pst->top] = x;//栈顶位置存放元素x pst->top++;//栈顶上移 } //检测栈是否为空 bool StackEmpty(Stack* pst) { assert(pst); return pst->top == 0; } //出栈 void StackPop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 pst->top--;//栈顶下移 } //获取栈顶元素 STDataType StackTop(Stack* pst) { assert(pst); assert(!StackEmpty(pst));//检测栈是否为空 return pst->a[pst->top - 1];//返回栈顶元素 } //获取栈中有效元素个数 int StackSize(Stack* pst) { assert(pst); return pst->top;//top的值便是栈中有效元素的个数 } /*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/ typedef struct { Stack pushST;//插入数据时用的栈 Stack popST;//删除数据时用的栈 } MyQueue; /** Initialize your data structure here. */ MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//申请一个队列类型 StackInit(&obj->pushST);//初始化pushST StackInit(&obj->popST);//初始化popST return obj; } /** Push element x to the back of queue. */ void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST, x);//插入数据，向pushST插入 } /** Get the front element. */ int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popST))//popST为空时，需先将pushST中数据导入popST { while(!StackEmpty(&obj->pushST))//将pushST数据全部导入popST { StackPush(&obj->popST, StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST);//返回popST栈顶的元素 } /** Removes the element from in front of queue and returns that element. */ int myQueuePop(MyQueue* obj) { int top = myQueuePeek(obj); StackPop(&obj->popST);//删除数据，删除popST中栈顶的元素 return top; } /** Returns whether the queue is empty. */ bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);//两个栈均为空，则“队列”为空 } void myQueueFree(MyQueue* obj) { //先释放两个栈，再释放队列的结构体类型 StackDestroy(&obj->pushST); StackDestroy(&obj->popST); free(obj); }
