栈： 先进后出
对于栈的算法题常见的技巧： 通过辅助栈实现排序，最小值搜索、元素位置交换。
同时注意栈的判空。
队列：先进先出
普通队列（数组构成的）： 判空： 头指针==尾指针； 判满： 尾指针==n
对于生存者消费者模式： 常用阻塞队列。当队列满，等待队列阻塞，无法入队；当队列空，等待队列阻塞，队列不能出队。
循环队列： 为了充分利用队列空间。当尾指针指向最后一个位置，此时头指针也后移，新的元素无法入队。循环队列让数组首尾相连，当尾指针指向队尾，新的元素从数组第一个位置开始入队。（注意判空和判满）
1: 实现最小栈
思路： 建立两个栈，一个栈用来存放数据；一个栈用来存放当前最小栈。
最小栈就是： 栈底到栈顶，元素递减，栈底元素最大，栈顶元素最小。
class MinStack {
public:
MinStack() {
// 构造函数 初始化最小栈
my_min_stack.push(INT_MAX);
}
void push(int x) {
my_stack.push(x);
my_min_stack.push(::min(x, my_min_stack.top())); // 最小栈，元素逐渐变小, 因此取最小值。
}
void pop() { // 两者都要弹出来
my_stack.pop();
my_min_stack.pop();
}
int top() {
return my_stack.top();
}
int min() {
return my_min_stack.top();
}
public:
stack my_stack;
stack my_min_stack; // 最小栈
};
2: 栈实现队列；
思路： 一个栈存放栈数据；一个栈存放队列数据。栈到队列是通过栈顶出栈压入另一个栈实现。
class CQueue {
public:
stack my_stack;
stack my_stack_queue;
public:
CQueue() {
;
}
void appendTail(int value) {
my_stack.push(value);
return;
}
int deleteHead() {
// 都没有元素
if (my_stack_queue.empty() && my_stack.empty()) {
return -1;
}
int res = 0;
if (!my_stack_queue.empty()) {
res = my_stack_queue.top();
my_stack_queue.pop();
return res;
}
// 栈实现队列
while (!my_stack.empty()) {
my_stack_queue.push(my_stack.top());
my_stack.pop();
}
res = my_stack_queue.top();
my_stack_queue.pop();
return res;
}
};
3: 有效的括号
思路：枚举判断是否符合有效的括号，符合就弹出栈顶，不符合就压入栈
class Solution {
public:
bool isValid(string s) {
// 声明一个栈
stack my_stack;
for (int i = 0; i < s.size(); i++) {
// 非空场景判断
if (my_stack.empty()) {
my_stack.push(s[i]);
continue;
}
// () [] {} 只有这种场景是符合的，需要弹出栈顶元素的
if ((s[i] == ')' && my_stack.top() == '(') ||
(s[i] == '}' && my_stack.top() == '{') ||
(s[i] == ']' && my_stack.top() == '[') ) {
my_stack.pop();
} else {
my_stack.push(s[i]);
}
}
if (my_stack.empty()) return true;
return false;
}
};
4: 逆波兰表达式
思路：栈
class Solution {
public:
int evalRPN(vector& tokens) {
// 声明一个栈
stack my_stack;
int res = 0;
//
int tmp_val1 = 0;
int tmp_val2 = 0;
for (int i = 0; i = 1 && isNum(tokens[i])) {
my_stack.push(atoi(tokens[i].c_str()));
} else {
GetStackNum(tmp_val1, tmp_val2, my_stack);
if (strcmp("+", tokens[i].c_str()) == 0) {
res = tmp_val1 + tmp_val2;
cout << res << endl;
} else if (strcmp("-", tokens[i].c_str()) == 0) {
res = tmp_val2 - tmp_val1;
} else if (strcmp("*", tokens[i].c_str()) == 0) {
res = tmp_val1 * tmp_val2;
} else if (strcmp("/", tokens[i].c_str()) == 0) {
res = tmp_val2 / tmp_val1;
}
my_stack.push(res);
}
}
return my_stack.top();
}
void GetStackNum(int& val1, int& val2, stack& my_stack)
{
val1 = my_stack.top();
my_stack.pop();
val2 = my_stack.top();
my_stack.pop();
}
int isNum(string& s)
{
for (int i = 0; i < s.size(); i++) {
if (s[i] == '-' && s.size() != 1) {
continue;
}
if (s[i] >= '0' && s[i] <= '9') {
;
} else {
return false;
}
}
return true;
}
};
5: 栈的排序
思路： 辅助栈，注意原栈一定是个从栈底到栈顶递减的栈，所以出栈到辅助栈，就是一个递增的，这样保证了原本的顺序。
class SortedStack {
public:
stack my_stack;
stack my_help_stack;
public:
SortedStack() {
;
}
void push(int val) {
if (my_stack.empty() || val <= my_stack.top()) {
my_stack.push(val);
return;
}
while (!my_stack.empty() && val > my_stack.top()) {
my_help_stack.push(my_stack.top());
my_stack.pop();
}
my_stack.push(val);
while (!my_help_stack.empty()) {
my_stack.push(my_help_stack.top());
my_help_stack.pop();
}
return;
}
void pop() {
if (my_stack.empty())
return;
my_stack.pop();
return;
}
int peek() {
if (my_stack.empty())
return -1;
return my_stack.top();
}
bool isEmpty() {
return my_stack.empty();
}
};
6: 栈转化为队列
思路：
class MyQueue {
public:
stack my_stack;
stack my_queue;
public:
MyQueue() {
;
}
void push(int x) {
my_stack.push(x);
}
int pop() {
if (my_queue.empty())
StackToQueue(my_stack, my_queue);
if (my_queue.empty())
return -1;
int res = my_queue.top();
my_queue.pop();
return res;
}
int peek() {
if (my_queue.empty())
StackToQueue(my_stack, my_queue);
if (my_queue.empty())
return -1;
return my_queue.top();
}
bool empty() {
if (my_queue.empty())
StackToQueue(my_stack,my_queue);
return my_queue.empty();
}
private:
void StackToQueue(stack& s, stack& q)
{
while (!s.empty()) {
q.push(s.top());
s.pop();
}
return;
}
};
7: 化队列为栈
思路：在push时候进行 追加+反转
class MyStack {
public:
queue my_queue;
queue my_stack;
public:
MyStack() {
;
}
void push(int x) {
my_queue.push(x);
QueueToStack(my_queue, my_stack);
}
int pop() {
if (my_stack.empty())
return -1;
int res = my_stack.front();
my_stack.pop();
return res;
}
int top() {
if (my_stack.empty())
return -1;
int res = my_stack.front();
return res;
}
bool empty() {
return my_stack.empty();
}
private:
void QueueToStack(queue& q, queue& s)
{
// 将s数据放在q的后面，之后清空s
while(!s.empty()) {
q.push(s.front()); //
s.pop(); //
}
//对q和s互换反转，这样s就是一个和q存放顺序相反的
swap(s, q);
}
};
