今天学习了栈与队列这两个数据结构，栈是一个先进后出的结构，在C++中用stack进行表示，有push、pop、top、empty这些属性；队列是一个先进后出的结构，有push、pop、front、back。empty这些属性。在底层实现上，他们都是用deque双向队列进行实现的。
232.用栈实现队列
题目链接：232. 用栈实现队列 - 力扣（LeetCode）
想用栈实现队列，一个栈是不够的，我们需要用到两个栈来实现队列的模拟。
主要难点在于pop操作。我们设置stackin和stackout两个栈，push的元素全部放入stackin中，当需要pop操作时，我们将stackin的元素依次push入stackout，然后使用stackout进行弹出。
具体代码实现如下：
class MyQueue {
public:
stack<int> stackin;
stack<int> stackout;
MyQueue() {
}
void push(int x) {
stackin.push(x);
}
int pop() {
if(stackout.empty())
{
while(!stackin.empty())
{
int result=stackin.top();
stackin.pop();
stackout.push(result);
}
}
int result=stackout.top();
stackout.pop();
return result;
}
int peek() {
int result=this->pop();
stackout.push(result);
return result;
}
bool empty() {
if(stackin.empty()&&stackout.empty()) return true;
else return false;
}
};
/**
* 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();
*/225.用队列实现栈
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
用队列实现栈，一个队列就够了。对于pop操作，只需要把size-1个元素pop后重新push如队列中，这样位于队尾的元素就到了队首位置，直接弹出即可。
代码实现如下：
class MyStack {
public:
queue<int> q;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int size=q.size();
size=size-1;
for(int i=0;i<size;i++)
{
int result=q.front();
q.pop();
q.push(result);
}
int result=q.front();
q.pop();
return result;
}
int top() {
return q.back();
}
bool empty() {
if(q.empty()) return true;
else return false;
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/20.有效的括号
这个题目是去判断括号的匹配问题，一般都是用栈来解决的。括号不匹配在此题中有三种情况
1.遍历完字符串后栈内有多余的元素
2.匹配过程中发现栈顶元素和对应的数组元素不相等
3.还没遍历完字符串时，栈就为空了。
这里还有一个小技巧。例如当遍历到一个左括号时，我们直接向栈插入一个右括号。这样的好处是当栈顶元素和字符串元素进行匹配时，可以直接进行比较，比较方便。
代码实现如下：
class Solution {
public:
bool isValid(string s) {
stack<char> stackc;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(') stackc.push(')');
else if(s[i]=='[') stackc.push(']');
else if(s[i]=='{') stackc.push('}');
else if(stackc.empty()||stackc.top()!=s[i]) return false;
else stackc.pop();
}
return stackc.empty();
}
};1047. 删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
这个题目要求删除字符串里相邻且相同的元素。也是直接用栈就可以解决，将字符串元素和栈顶元素进行匹配即可。题目比较简单，代码实现如下：
class Solution {
public:
string removeDuplicates(string s) {
stack<char> stackc;
for(int i=0;i<s.size();i++)
{
if(stackc.empty()) stackc.push(s[i]);
else
{
if(s[i]==stackc.top()) stackc.pop();
else stackc.push(s[i]);
}
}
string temp;
while(!stackc.empty())
{
temp+=stackc.top();
stackc.pop();
}
int start=0;
int end=temp.size()-1;
int mid=(end-start+1)/2-1;
for(int i=0;i<=mid;i++) swap(temp[start+i],temp[end-i]);
return temp;
}
};