【力扣刷题篇】栈与队列相关OJ题及题解

20 . 有效的括号

1> 题目介绍

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

2> 题目解析

条件一 指: 左右括号类型必须一致。 例如左括号是圆括号 ( ， 那么其对于的右括号也必须是 )
条件二指: 左右括号的内外顺序必须一致， 也就是由外向内的顺序必须一致 [ { ( ) } ]
条件三指: 每个右括号都必须对应一个相同类型相同顺序的左括号， 且右括号必须在左括号的右侧

3> 题解

采取 栈 这种数据结构来解决该题， 比较容易
依次遍历string对象存储的字符串， 遇到左括号时， 将其存入栈对象，
遇到右括号， 弹出栈顶元素， 判断是否满足条件

思路一 – 依次遍历栈顶元素， 采取键值匹配的形式

#include<stack>
class Solution 
{
public:bool isValid(string s) {if(s.size() % 2)return false;stack<char> stk;int i = 0;char A;while(i<s.size()){switch(s[i]){case '(': stk.push(s[i]);          break;case '[':stk.push(s[i]);break;case '{':stk.push(s[i]);break;case ')':if(stk.empty())return false;A = stk.top();stk.pop();if(A != '(')return false;break;case ']':if(stk.empty())return false;A = stk.top();stk.pop();if(A != '[')return false;break;case '}':if(stk.empty())return false;A = stk.top();stk.pop();if(A != '{')return false;break;}++i;}return stk.empty();}
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(n)

225 . 用队列实现栈

1 . 题目介绍

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

2 . 题目解析

注意 : 只可使用队列结构中的 push pop empty size front这几项接口来实现栈
使用先进先出的队列， 来实现后进先出的栈

3 . 题解

思路一 – 双队列实现栈

思路描述 : 每次进行插入后， 通过一个循环， 让队列前面的元素依次弹出队列并插入到队尾中 。 这样就使得插入到队尾的元素成功的跑到了队首的位置。

class MyStack {
public:queue<int> queue1;queue<int> queue2;MyStack() {}void push(int x) {if(queue1.empty()){queue1.push(x);return;}queue2.push(x);while(!queue1.empty()){int a = queue1.front();queue2.push(a);queue1.pop();}queue1 = queue2;while(!queue2.empty()){queue2.pop();}}int pop() {int a = queue1.front();queue1.pop();return a;}int top() {return queue1.front();}bool empty() {return queue1.empty();}
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(n)

思路二 – 单队列实现栈

class MyStack {
public:queue<int> queue1;MyStack() {}void push(int x) {if(queue1.size() == 0){queue1.push(x);}else{queue1.push(x);int num = 0;while(num < queue1.size()-1){int a = queue1.front();queue1.pop();queue1.push(a);++num;}cout << queue1.back() << " ";}}int pop() {int a = queue1.front();queue1.pop();return a;}int top() {return queue1.front();}bool empty() {return queue1.empty();}
};

232 . 用栈实现队列

1 . 题目介绍

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

2 . 本题要求

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

3 . 题解

思路一 – 单栈模拟队列的进或出

class MyQueue {
public:stack<int> stk1;stack<int> stk2;MyQueue() {}void push(int x) {while(!stk2.empty()){stk1.push(stk2.top());stk2.pop();}stk1.push(x);while(!stk1.empty()){stk2.push(stk1.top());stk1.pop();}}int pop() {int a = stk2.top();stk2.pop();return a;}int peek() {return stk2.top();}bool empty() {return stk2.empty();    }
};
作者 : Joker不是Joker
时间复杂度 : O(n)
空间复杂度 : O(1)

思路一 – 代码优化

代码优化了 每次进行插入都将来回颠倒stk1与stk2中的元素
改为了 如果只进行插入， 那么就会一直将元素插入至stk1中， 当进行删除时，再将stk1中的元素依次弹出且进入栈stk2 。
当 执行出栈后 ，在执行入栈， 会将stk2中的元素依次弹出且进入栈stk1中

lass MyQueue {
public:stack<int> stk1;stack<int> stk2;MyQueue() {}void push(int x) {if(stk2.empty()){stk1.push(x);}else{while(!stk2.empty()){stk1.push(stk2.top());stk2.pop();}stk1.push(x);}}int pop() {int a = 0;if(stk2.empty()){while(!stk1.empty()){stk2.push(stk1.top());stk1.pop();}a = stk2.top();stk2.pop();}else{a = stk2.top();stk2.pop();}return a;}int peek() {if(stk2.empty()){while(!stk1.empty()){stk2.push(stk1.top());stk1.pop();}}return stk2.top();}bool empty() {if(stk1.empty() && stk2.empty())return true;return false;}
};

622 . 设计循环队列

1 . 题目描述

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

循环队列的优势:

• 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

2 . 题目解析

实现一个循环队列， 意思是队头被删除的元素所占用的空间可以循环利用。
队列是一端进入， 另一端退出。
可以看为队尾进入， 队头退出。
当队头的元素被删除后， 其所在的队头变为队尾， 它的下一个元素变为队头。
这就需要两个指针， 一个头指针指向队头， 一个尾指针指向队尾。
两个指针在这个队列中不断循环移动， 因此实际意义上的队头和队尾是在不断变动的
由此可知， 应该通过顺序表来实现循环队列。

3 . 题解

思路一 – n+1个空间实现n个有效长度

typedef int QDataType;
class MyCircularQueue 
{
public:QDataType* arr;int head; int tail;int n;MyCircularQueue(int k) {arr = new QDataType[k+1];n=k+1;head = 0;tail = 0;}bool enQueue(int value) {if((tail-head+n)%n == (n-1))return false;if(tail == (n-1)){arr[tail] = value;tail = 0;}else{arr[tail] = value;++tail;}return true;}bool deQueue() {if(head == tail)return false;if(head == (n-1)){head = 0;}else{++head;}return true;}int Front() {if(head == tail)return -1;return arr[head];}int Rear() {if(head == tail)return -1;if(tail == 0)return arr[n-1];return arr[tail-1];}bool isEmpty() {return head == tail;}bool isFull() {return ((tail-head+n)%n == (n-1));}
};
作者 : Joker不是Joker
时间复杂度 : O(1)
空间复杂度 : O(n)