自学内容网 自学内容网

【C++】了解stack和queue

目录

stack介绍

栈的结构

栈接口的使用

栈的基本题目

最小栈

栈的弹出压入序列

二叉树的分层遍历

栈的模拟实现

stack.h文件

队列的介绍

队列的结构

队列接口的使用

队列的模拟实现

priority_queue的介绍和使用

接口使用

优先级队列的题目应用

数组中第k大的数字

优先级队列的模拟实现

priority_queue.h文件

deque的介绍

deque的缺陷


stack介绍

我们可以搜一些资料学习栈:栈文档

栈的结构

我们很熟悉了,栈的结构:

栈接口的使用

这些接口比较简单,这里不过多赘述!

栈的基本题目

最小栈

地址:最小栈

思路:

题目的本质是,我们要得到一个栈中的最小元素!

我们可以用两个栈实现一个栈的功能:

定义一个栈_st,里面存储所有插入进来的数据,定义另一个栈_minst,存储小数据,不管在什么时候我们都保证它的栈顶元素是所有数据最小的数。

于是,我们拿栈中的最小元素,只需要返回_minst的栈顶元素即可!

那么关键就在于怎么进行插入和删除的操作而已!

插入时,无论什么数据,_st都要插入,当_minst是空的时候,或者插入的元素小于_minst的栈顶元素时,_minst也插入!

删除时,无论什么数据,_st都要删除,当要删除的元素等于_minst的栈顶元素时,_minst也删除!

代码:

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
        //无论如何_st,_st都要push
        _st.push(val);
        //当_minst为空,或者栈顶元素小于或等于val,_minst也push
        if(_minst.empty()||val<=_minst.top())
           _minst.push(val);
    }
    
    void pop() {
        //当_st栈顶的元素和_minst栈顶元素相等,_minst也pop
        if(_st.top()==_minst.top())
            _minst.pop();
        //无论如何,_st都要pop
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
private:
    stack<int> _st;//存储所有数据
        //存储小数据,无论什么时候,它的栈顶一定是所有数据最小的那个
        stack<int> _minst;
};

栈的弹出压入序列

地址:栈的弹出压入序列

思路:

我们需要模拟入栈出栈即可!

遍历压入序列,入栈,用 i 记录出栈序列的下标,当栈顶元素和出栈序列相等时,出栈,同时 i++,往前走,当栈顶元素和出栈序列不相等时,继续遍历入栈!

有一种情况:比如压入序列:2,1,0,弹出序列:1,2,0。

当入栈到1时,一直出栈到空,此时0还没有入栈,然后判断条件栈顶元素和出栈序列相等,判断不了,因为此时栈是空的,没有栈顶元素,所以我们需要加一个判断条件:栈不为空!

代码:

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> _st;
        size_t i=0;//遍历popV
        //遍历插入
        for(auto& e:pushV)
        {
            _st.push(e);
            //当栈顶元素和popV的元素相等,栈pop
            while(!_st.empty()&&_st.top()==popV[i])
            {
                _st.pop();
                i++;
            }
        }
        return _st.empty();
    }

二叉树的分层遍历

地址:二叉树的层序遍历

思路:

我们首先让根节点先进入队列,根据对头左右节点有就继续进队列,然后队头出队列,循环往复。

只是我们需要插入进一个二维数组,我们可以将这颗树的每一层有多少个节点记录下来!

代码:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        int lsize;
        if(root)
        {
            q.push(root);
            lsize=1;
        }
        while(!q.empty())
        {
            vector<int> v;
            while(lsize--)
            {
                if(q.front()->left)
                    q.push(q.front()->left);
                if(q.front()->right)
                    q.push(q.front()->right);
                v.push_back(q.front()->val);
                q.pop();
            }
            lsize=q.size();
            vv.push_back(v);
        }
        return vv;
    }
};

栈的模拟实现

我们仔细观察栈的结构(先进后出),仔细想一下,发现我们可以用一个动态数组来实现它(也可以用链表),

所以我们可以用vector来包装它!

这样就简单很多!

stack.h文件

#include<iostream>
#include<vector>
namespace ywc
{
template<class T>
class stack
{
public:
bool empty()
{
return _s.empty();
}
size_t size()
{
return _s.size();
}
const T& top()
{
return _s.back();
}
void push(const T& x)
{
_s.push_back(x);
}
void pop()
{
_s.pop_back();
}
private:
std::vector<T> _s;
};
}

当然,也能用链表实现!这里不过多赘述!

队列的介绍

文档:队列文档

队列的结构

队列接口的使用

这里也不过多赘述,比较简单!

队列的模拟实现

队列是先进先出,需要头删,用一个动态数组效率太慢,所以我们采用链表!

我们可以用一个list来包装!

代码:

#include<iostream>
#include<list>
namespace ywc
{
  template<class T>
   class queue
   {
public:
bool empty()
{
return _lt.empty();
}
size_t size()
{
return _lt.size();
}
const T& front()
{
return _lt.front();
}
const T& back()
{
return _lt.back();
}
void push(const T& x)
{
_lt.push_back(x);
}
void pop()
{
_lt.pop_front();
}
private:
std::list<T> _lt;
   };
}

priority_queue的介绍和使用

优先级队列的文档:优先级队列文档

简单介绍一下优先级队列:

不管什么时候,它的第一个元素总是最大的!也能随时插入元素,且只能检索顶部数据,且要删除数据也是删除顶部数据

所以:

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用 priority_queue。注意:默认情况下priority_queue是大堆。

简单赘述:

优先级队列是底层是一个动态数组(堆),在数组尾部插入,然后利用向上调整法调整数据的分布从而符合堆的特性(大小堆),删除数据时,删除第一个数据,然后利用向下调整法调整数据的分布从而符合堆的特性!

接口使用

接口比较简单,这里不过多赘述!

我们来看一下它的大小堆特性:

但当我们的类型是自定义类型的话:

如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重 载。

如:

优先级队列的题目应用

数组中第k大的数字

地址:数组中第k个大的数字​​​​​​

思路:

我们可以将数组中的数全部放进一个大堆中,然后将前k-1个数删掉,然后栈顶就是我们的第k个大的数字!

代码:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //将数组中的数全部放在一个大堆中
        priority_queue<int> q;
        for(auto& e:nums)
           q.push(e);
        while(--k)//将前k-1个数字pop掉
            q.pop();
        return q.top();
    }
};

优先级队列的模拟实现

根据刚才我们所说的它的特点来包装它,并且参照STL库中的方式!

我们的思路:

priority_queue.h文件

#pragma once

#include<iostream>
#include<vector>
#include<algorithm>
namespace ywc
{
template<class T>
struct less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
template<class T>
struct greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
template<class T,class Container=std::vector<T>,class Compare=less<T>>
class priority_queue
{
public:
void push(const T& x)
{
_c.push_back(x);
//向上调整
AdjustUp(size() - 1);
}
void pop()
{
std::swap(_c[0], _c[size() - 1]);
_c.pop_back();
//向下调整
AdjustDown(0);
}
bool empty()
{
return size() == 0;
}
const T& top()
{
return _c.front();
}
size_t size() const
{
return _c.size();
}
private:
//向上调整
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)//当孩子等于0时跳出
{
if (Compare()(_c[parent],_c[child]))
{
std::swap(_c[child], _c[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < size())
{
//假设法,假设左右孩子大小
if (child + 1 < size() && Compare()(_c[child ] , _c[child+1]))
{
child++;
}
if (Compare()(_c[parent] , _c[child]))
{
std::swap(_c[child], _c[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
Container _c;
};
}

deque的介绍

先前讲过stack底层是vector,queue底层是list,但其实在STL库中,stack和queue底层默认的容器是deque.

我们现在来介绍一下deque:

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与 list比较,空间利用率比较高。

结构:

注意:deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个 动态的二维数组。

如图:

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问 的假象,落在了deque的迭代器身上。

deque的缺陷

与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩 容时,也不需要搬移大量的元素,因此其效率是必vector高的。

与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。

deque有一个致命缺陷不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实 际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

为什么选择deque作为stack和queue的底层默认容器?

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进 行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的 元素增长时,deque不仅效率高,而且内存使用率高。

我们下期见!!!


原文地址:https://blog.csdn.net/Qiwaw/article/details/145230462

免责声明:本站文章内容转载自网络资源,如侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!