栈和队列
栈和队列的使用场景和相关算法题实现。
✏️ 1、栈(Stack)& 队列(queue)
🖋️ 1.1、栈实现队列
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
m_stack1 = new std::stack<int>();
m_stack2 = new std::stack<int>();
}
/** Push element x to the back of queue. */
void push(int x) {
m_stack1->push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(m_stack2->empty()){
while(!m_stack1->empty()){
m_stack2->push(m_stack1->top());
m_stack1->pop();
}
}
int re = m_stack2->top();
m_stack2->pop();
return re;
}
/** Get the front element. */
int peek() {
if(m_stack2->empty()){
while(!m_stack1->empty()){
m_stack2->push(m_stack1->top());
m_stack1->pop();
}
}
return m_stack2->top();
}
/** Returns whether the queue is empty. */
bool empty() {
return m_stack1->empty() && m_stack2->empty();
}
private:
std::stack<int> *m_stack1;
std::stack<int> *m_stack2;
};
用两个栈实现队列,两个栈的容量大小分别为P和Q,且Q>P,则队列的最大容量为 。
🖋️ 1.2、队列实现栈
class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {
m_queue1 = new std::queue<int>();
m_queue2 = new std::queue<int>();
}
/** Push element x onto stack. */
void push(int x) {
m_queue1->push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
while(m_queue1->size() > 1){
m_queue2->push(m_queue1->front());
m_queue1->pop();
}
int re = m_queue1->front();
m_queue1->pop();
std::queue<int> *tmp = m_queue1;
m_queue1 = m_queue2;
m_queue2 = tmp;
return re;
}
/** Get the top element. */
int top() {
while(m_queue1->size() > 1){
m_queue2->push(m_queue1->front());
m_queue1->pop();
}
int re = m_queue1->front();
m_queue1->pop();
m_queue2->push(re);
std::queue<int> *tmp = m_queue1;
m_queue1 = m_queue2;
m_queue2 = tmp;
return re;
}
/** Returns whether the stack is empty. */
bool empty() {
return m_queue1->empty();
}
private:
std::queue<int> *m_queue1;
std::queue<int> *m_queue2;
};
🖋️ 1.3、双端队列(deque: double-ended queue)
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
🖋️ 1.4、最小栈
在常数时间内检索到最小元素的栈。(题目链接)
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {}
void push(int x) {
m_stack.push(x);
if(min_stack.empty() || x <= min_stack.top()) // 等于的情况不能少
min_stack.push(x);
}
void pop() {
if(!m_stack.empty()){
if(m_stack.top() == min_stack.top())
min_stack.pop();
m_stack.pop();
}
}
int top() {
return m_stack.top();
}
int getMin() {
return min_stack.top();
}
private:
std::stack<int> m_stack;
std::stack<int> min_stack;
};
🖋️ 1.5、题型
一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序?
void StackAndQueue::sortStack(std::stack<int>& stk){
stack<int> t_stk;
while(!stk.empty()){
int k = stk.top();
stk.pop();
while(!t_stk.empty() && k > t_stk.top()){ // >= 不可以,全相等的特例会死循环
stk.push(t_stk.top());
t_stk.pop();
}
t_stk.push(k);
}
while(!t_stk.empty()){
stk.push(t_stk.top());
t_stk.pop();
}
}
✏️ 2、单调栈和单调队列
🖋️ 2.1、单调栈(维护凸包)
单调栈中存放的数据是有序的,所以单调栈也分为单调递增栈和单调递减栈
单调递增栈:栈中数据出栈的序列为单调递增序列
单调递减栈:栈中数据出栈的序列为单调递减序列
PS
:这里一定要注意所说的递增递减指的是出栈的顺序,而不是在栈中数据的顺序。
stack<int> istack;
//此处一般需要给数组最后添加结束标志符,具体下面例题会有详细讲解
for (遍历这个数组)
{
if (栈空 || 栈顶元素大于等于当前比较元素)
{
入栈;
}
else
{
while (栈不为空 && 栈顶元素小于当前元素)
{
栈顶元素出栈;
更新结果;
}
当前数据入栈;
}
}
🖋️ 2.2、单调队列
单调队列中存放的数据也是有序的,所以单调队列也分为单调递增队列和单调递减队列
单调递增队列:队列中数据出队的序列为单调递增序列
单调递减队列:队列中数据出队的序列为单调递减序列
PS
:这里一定要注意所说的递增递减指的是出队(队头出)的顺序,和数据在队列中的顺序是一样的。
单调队列只能从队尾插入,但可以从两头删除。可以用双端队列实现。
// 假设有 n 个元素的序列,要求解的是长度为 k 的区间的最大值
// 队列que是STL的双向队列deque
// 队列存放的是元素在序列中的序号
deque<int> iqueue;// 双向队列
for(遍历这个数组)
{
while(!iqueue.empty() && a[iqueue.back()]<a[i])
{
iqueue.pop_back(); // 去尾操作
}
iqueue.push_back(i); // 新元素(的序号) 入队列
if(i >= k) // 这个很明显
{
while(!iqueue.empty() && iqueue.front() < i-k+1)
{
iqueue.pop_front(); // 删头操作
}
cout << a[iqueue.front()] << " ";// 取解操作
}
}
💎 2.2.1、特点:
维护区间最值;
去除冗杂状态;
保持队列单调(最大值是单调递减序列,最小值是单调递增序列);
最优选择在队首。
💎 2.2.2、单调队列的原理:
在处理f[i]
时,去除冗杂、多余的状态,使得每个状态在队列中只会出现一次;同时维护一个能瞬间得出最优解的队列,减少重新访问的时间;在取得自己所需的值后,为后续的求解做好准备。
单调队列:擅长维护区间最大 / 最小值,最小值对应着递增队列,最大值对应着递减队列;
单调栈:擅长维护最近大于 / 小于关系,从左侧先入栈就是维护左侧最近关系,从右侧先入栈就是维护右侧最近关系。
🖋️ 2.3、单调队列和单调栈的性质
具有单调性
容器中的元素个数永远不为空。(因为当添加一个元素时,它要么直接被添加到“尾部”,要么弹出k个比它小的数后再被添加到“尾部”)
对于一个元素
i
,我们可以知道在它左边区间,第一个比它小的值,也就是Max(v[x]|x<i&&v[x]<v[i])
在元素添加的过程中,我们会不断弹出比它小的值,最后一个弹出的值,即为所求。如果没有元素被弹出,那就无法求出,虽然这个数一定存在。 顺便在这里多提一句,第二个比它小的数是一定不知道的,因为不确定是否被弹出对于一个元素
i
,我们可以知道在它左边区间,第一个比它大的值,也就是Min(v[x]|x<i&&v[x]>v[i])
在弹出比i小的所有元素后,栈顶的元素即为所求。如果栈为空,也无法求出。根据2和3,它们是元素插入时所获得的信息,我们可以推出当元素被弹出时能获得的信息:在右边区间,第一个比它大的值。
我们可以统计在添加元素过程中,弹出了多少个元素。
注:这里的大于和小于并不严谨,是为了表述尽量简单。请读者自己注意大于/大于等于,小于/小于等于。根据原则:容器中等于e
的元素也会被弹出,进行判断即可。
🖋️ 2.4、单调队列和单调栈的应用
单调队列
可以查询区间最值(不能维护区间k大,因为队列中很有可能没有k个元素)
优化DP:单调队列一般是用于优化动态规划方面问题的一种特殊数据结构,且多数情况是与定长连续子区间问题相关联
单调栈
对于某个元素i
:
左边区间第一个比它小的数,第一个比它大的数
确定这个元素是否是区间最值
右边区间第一个大于它的值
到 右边区间第一个大于它的值 的距离
确定以该元素为最值的最长区间
🖋️ 2.5、题型
1、保留最大的数
给定一个十进制的正整数number,选择从里面去掉一部分数字,希望保留下来的数字组成的正整数最大。
输入描述:输入为两行内容,第一行是正整数number,1 ≤ length(number) ≤ 50000
。第二行是希望去掉的数字数量cnt 1 ≤ cnt < length(number)
。(字节一面)
std::string getMaxStr(const std::string & str, int K){
if(K == 0){
return str;
}else{
int idx = 0;
string result;
while(K > 0 && idx < str.size()){
if(result.empty() || result.back() >= str[idx]){
result.push_back(str[idx++]);
}else{
while(K > 0 && !result.empty() && result.back() < str[idx]){
result.pop_back();
K--;
}
result.push_back(str[idx++]);
}
}
if(K > 0)
result = result.substr(0, result.size() - K);
if(idx < str.size())
result = result.append(str.substr(idx, str.size()));
idx = 0;
while(idx < result.size() && result[idx++] == '0');
return result.substr(idx - 1, result.size());
}
}
4、视野总和(摩天大楼)
8、发射站
9、牛宫
✏️ 3、优先队列
🖋️ 3.1、优先队列 & 左式堆
优先队列和普通队列不同的地方在于,在优先队列中,每个记录保存一个优先级值或关键字(本文使用关键字表示),任意记录正常从队尾入队,按照优先级大小或关键字的大小进行出队。最大关键字先出队,称为最大优先队列或降序优先队列;最小关键字先出队,称为最小优先队列或升序优先队列
堆是另一种与优先队列不同的数据结构,一般来说,优先队列是用堆实现的。堆是满足堆序性的树结构,分为二叉堆、d-堆、左式堆、斜堆和二项堆。
🖋️ 3.2、题型
最后更新于
这有帮助吗?