目录
L232 用两个栈实现队列
#include<iostream>
#include<stack>
using namespace std;
// 用栈实现队列：使用两个栈——主栈和辅助栈
// 主栈顶——>队列头（弹出）；主栈底 <——队列尾（插入）
class MyQueue{
private:
stack<int> myqueue; // 主栈
public:
MyQueue(){}
// 队尾插入元素：将新元素放到栈低，没有返回值
void push(int x){
stack<int> tmp;
// 将主栈中所有元素先搬到辅助栈
while(!myqueue.empty()){
tmp.push(myqueue.top());
myqueue.pop();
}
// 将新元素压入主栈
myqueue.push(x);
// 将辅助栈的所有元素搬回主栈
while(!tmp.empty()){
myqueue.push(tmp.top());
tmp.pop();
}
}
// 弹出队头元素：将主栈顶元素弹出
int pop(){
int x = myqueue.top();
myqueue.pop();
return x;
}
/* 实际上弹出元素是没有返回值的
void pop(){
myqueue.pop();
}
*/
// 获得队头
int front(){
return myqueue.top();
}
// 判空
bool empty(){
return myqueue.empty();
}
};
int main(){
MyQueue que;
que.push(1);
que.push(2);
que.push(3);
cout << que.front() << endl;
cout << que.empty() << endl;
que.pop();
cout << que.front() << endl;
return 0;
}
JS9 用两个栈实现队列
class CQueue {
public:
CQueue() {
}
void appendTail(int value) {
stack<int> tmp;
while(!myqueue.empty()){
tmp.push(myqueue.top());
myqueue.pop();
}
myqueue.push(value);
while(!tmp.empty()){
myqueue.push(tmp.top());
tmp.pop();
}
}
int deleteHead() {
if(myqueue.empty()) return -1;
int x = myqueue.top();
myqueue.pop();
return x;
}
private:
stack<int> myqueue; // 主栈
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
L225 JO5 两个队列实现栈
#include<iostream>
#include<queue>
using namespace std;
// 用队列实现栈：使用两个队列——主队列和辅助队列
// 主队列头——>栈顶（弹出）；主队列头 <——栈顶（插入）
class MyStack{
private:
queue<int> mystack;
public:
MyStack(){}
// 栈顶插入元素：将新元素放到主队头，没有返回值
void push(int x){
queue<int> tmp;
// 先将新元素进辅助队列
tmp.push(x);
// 然后将主队列中的元素搬到辅助队列
while(!mystack.empty()){
tmp.push(mystack.front());
mystack.pop();
}
// 最后将辅助队列中的所有元素挪回主队列
while(!tmp.empty()){
mystack.push(tmp.front());
tmp.pop();
}
}
// 弹出栈顶元素
void pop(){
mystack.pop();
}
// 输出栈顶元素
int top(){
return mystack.front();
}
// 判断栈空
bool empty(){
return mystack.empty();
}
};
int main(){
MyStack stk;
stk.push(1);
stk.push(2);
stk.push(3);
cout << stk.top() << endl;
cout << stk.empty() << endl;
stk.pop();
cout << stk.top() << endl;
return 0;
}
JS30 JO20最小栈设计：包含min函数的栈（使用非严格单调栈）
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
// 最小栈的实现
class MinStack{
public:
stack<int> mainstack, minstack;
MinStack(){}
// 入栈push
void push(int x){
// 入主栈
mainstack.push(x);
// 判断是否要入最小栈：最小栈为空或新元素小于最小栈栈顶元素
if(minstack.empty() || x <= minstack.top()){
minstack.push(x);
}
}
// 出栈pop
void pop(){
// 判断最小栈是否要弹出元素:主栈栈顶元素与最小栈栈顶元素同
if(mainstack.top() == minstack.top()){
minstack.pop();
}
// 主栈弹出栈顶元素
mainstack.pop();
}
// 获取栈顶元素
int top(){
return mainstack.top();
}
// 获得最小值
int min(){
return minstack.top();
}
};
int main(){
MinStack stk;
stk.push(-2);
stk.push(0);
stk.push(-3);
cout << stk.min()<< endl;
stk.pop();
cout << stk.top() << endl;
cout << stk.min() << endl;
return 0;
}
JS59II 最大队列设计：使用单调队列（双向队列deque实现）
#include<deque>
#incllude<queue>
using namespace std;
class MaxQueue {
queue<int> mainque;
deque<int> maxdeq;
public:
MaxQueue() {
}
//当双向队列 deque 为空，则返回 -1 ；否则，返回 deque 首元素；
int max_value() {
return maxdeq.empty() ? -1 : maxdeq.front();
}
// （1）将元素 value 入队 queue
// （2）将deque中队尾所有小于value的元素弹出（以保持 deque 非单调递减），并将元素 value 入队 deque
void push_back(int value) {
mainque.push(value);
while(!maxdeq.empty() && value > maxdeq.back()){
maxdeq.pop_back();
}
maxdeq.push_back(value);
}
//（1）若队列 queue 为空，则直接返回 -1；
//（2）否则，将 queue 首元素出队；
// (3) 若 deque 首元素和 queue 首元素 相等 ，则将 deque 首元素出队（以保持两队列 元素一致 ）
int pop_front() {
if(mainque.empty()) return -1;
int val = mainque.front();
if(val == maxdeq.front()){
maxdeq.pop_front();
}
mainque.pop();
return val;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
JS31 JO21 栈的压入、弹出序列（辅助栈）
class Solution {
public:
/*
整体思路：
借用一个辅助栈 stack，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
复杂度：
时间复杂度：O(n)。 n 为入栈序列的长度
空间复杂度：O(n)。 辅助栈最多存储 n 个元素
算法流程
• 建立一个辅助栈
• 遍历入栈序列
• 元素入栈
• 若辅助栈栈顶元素等于弹出序列元素，则执行出栈操作
返回结果
*/
// poped是弹出元素顺序
// 逐个将pushed的元素压入栈，并判断该元素是否与poped的目前弹出元素相同，如果相同则从栈中又pop出该元素
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> tmp;
int index = 0; // popped当前弹出元素
for(int i = 0; i< pushed.size(); ++i){
tmp.push(pushed[i]);
while(!tmp.empty()&&tmp.top()==popped[index]){
tmp.pop();
index++;
}
}
return tmp.empty();
}
};
L20 有效括号（字节常考!!!!!字符串+栈）
class Solution {
public:
bool isValid(string s) {
// 用栈检查括号有效性:
if(s.size()%2 !=0) return false; // 长度不是偶数，肯定出错
stack<char> tmp;
for(int i=0; i<s.size();++i){
if(s[i]=='(' || s[i]=='{' || s[i]=='['){
// 如果是左括号压入栈
tmp.push(s[i]);
}else if(s[i]==')'){
if(tmp.empty() || tmp.top() != '(') return false;
tmp.pop();
}else if(s[i]=='}'){
if(tmp.empty() || tmp.top() != '{') return false;
tmp.pop();
}else {
if(tmp.empty() || tmp.top() != '[') return false;
tmp.pop();
}
}
// 左括号栈为空，则返回True，否则false
return tmp.empty();
}
};