232栈实现队列 ​
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
输入：
["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
C
//队列需要符合FIFO，所以用两个stack来模拟
class MyQueue {
stack<int> stkTail;
stack<int> stkHead;
public:
MyQueue() {
}
void push(int x) {
stkTail.push(x);
}
int pop() {//只有当stkHead为空，需要把stkTail里的都入栈stkHead
if(stkHead.empty()){
while(!stkTail.empty()){
stkHead.push(stkTail.top());
stkTail.pop();
}
}
int num=stkHead.top();
stkHead.pop();
return num;
}
int peek() {
if(stkHead.empty()){
while(!stkTail.empty()){
stkHead.push(stkTail.top());
stkTail.pop();
}
}
return stkHead.top();;
}
bool empty() {
return stkHead.empty()&&stkTail.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/java
//既然是栈，尽量都用LinkedList的push pop
class MyQueue {
LinkedList<Integer> stackTail;//队尾栈，用来入队
LinkedList<Integer> stackHead;//对头栈，用来出队
MyQueue() {
stackTail =new LinkedList<>();
stackHead =new LinkedList<>();
}
void push(int x) {
stackTail.push(x);
}
int pop() {
if(stackHead.isEmpty()){
while(stackTail.isEmpty()==false){
stackHead.push(stackTail.pop());
}
}
return stackHead.pop();
}
int peek() {
if(stackHead.isEmpty()){
while(stackTail.isEmpty()==false){
stackHead.push(stackTail.pop());
}
}
return stackHead.peek();
}
boolean empty() {
return stackHead.isEmpty()&&stackTail.isEmpty();
}
}225用队列实现栈 ​
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
注意:
- 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）
java
//队列实现栈
//既然用队列模拟，尽量都用offer peek poll
class MyStack {
LinkedList<Integer> queue;//出栈入栈用到的队列
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.offer(x);
//添加之后，将除了最新元素之外的所有都出队
//再依次入队
for (int i = 0; i < (queue.size() - 1); i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}栈 ​
20有效的括号 ​
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：falseC
//遍历字符串中的所有字符
//1，如果遇到了左括号，就把对应的右括号压栈（比如遇到了字符'('，就把字符')'压栈）。
//2，如果遇到了右括号
// 1）查看栈是否为空，如果为空，说明不能构成有效的括号，直接返回false。
// 2）如果栈不为空，栈顶元素出栈，然后判断出栈的这个元素是否等于这个右括号，如果不等于，说明不匹配，直接返回false。如果匹配，就继续判断字符串的下一个字符。
//3，最后如果栈为空，说明是完全匹配，是有效的括号，否则如果栈不为空，说明不完全匹配，不是有效的括号。
class Solution {
public:
bool isValid(string s) {
if (s.size() <= 1) return false;
std::stack<char> stk;
unordered_map<char,char>mmp;
mmp[')'] = '('; mmp[']'] = '['; mmp['}'] = '{';
for(int i=0;i<s.size();i++){
if(s[i]=='('||s[i]=='{'||s[i]=='['){//左括号就入栈
stk.push(s[i]);
}else{
if(stk.empty()||stk.top()!=mmp[s[i]]){//没匹配上，或者空
return false;
}
else stk.pop();
}
}
return stk.empty();
}
};5逆波兰表达式求值 ​
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
C
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for(string &s : tokens){
if(s=="+"||s=="-"||s=="*"||s=="/"){
int num1=stk.top();stk.pop();
int num2=stk.top();stk.pop();
if(s=="+") stk.push(num1+num2);
if(s=="-") stk.push(num2-num1);//减法和除法顺序反过来
if(s=="*") stk.push(num1*num2);
if(s=="/") stk.push(num2/num1);
}
else stk.push(stoi(s));
}
return stk.top();
}1047删除字符串所有相邻重复 ​
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
C
//遍历string，入栈，如果和栈顶相同就出栈
//最后栈里的元素就是结果
string removeDuplicates(string s) {
stack<char> stk;
for(char &c: s){
if(stk.empty()||stk.top()!=c){
stk.push(c);
}else stk.pop();
}
string res;
while(!stk.empty()){
res+=stk.top();
stk.pop();
}
reverse(res.begin(),res.end());
return res;
}C
//直接把字符串当成栈
class Solution {
public:
string removeDuplicates(string s) {
string res;
for(char &c: s){
if(res.empty()||res.back()!=c){
res.push_back(c);
}else res.pop_back();
}
return res;
}
};
队列 ​
36有效的数独 ​
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
输入：board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出：true 示例 2： 输入：board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出：false 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
C
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//定义三个二维整型向量，分别记录每一行、每一列、每个九宫格里每个数字出现的次数
vector<vector<int>> rowVec(9,vector<int>(9,0)); //行向量，rowVec[i][j]表示第i行数字j出现的次数
vector<vector<int>> culVec(9,vector<int>(9,0)); //列向量，culVec[i][j]表示第i列数字j出现的次数
//九宫格向量，nineVec[i][j][k]表示第i行第j列的九宫格里数字k出现的次数
vector<vector<vector<int>>> nineVec(9,vector<vector<int>>(9,vector<int>(9,0)));
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c=board[i][j];
if(c!='.'){
//将当前字符转换为数字并减去1，因为数字从1开始，而数组下标从0开始
int n=c-'0'-1;
rowVec[i][n]++;
culVec[n][j]++;
//在九宫格向量中将第i行第j列的九宫格里数字n的出现次数加1
nineVec[i/3][j/3][n]++;
//如果当前数字在行向量、列向量或九宫格向量中出现次数大于1，则表示不是有效的数独，返回false
if(rowVec[i][n]>1||culVec[n][j]>1||nineVec[i/3][j/3][n]>1)
return false;
}
}
}
//遍历结束后没有出现不符合规则的情况，则表示是有效的数独，返回true
return true;
}
};