stack和queue的学习

stack的介绍

stack的文档介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
   • empty：判空操作
   • back：获取尾部元素操作
   • push_back：尾部插入元素操作
   • pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque

---

stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中顶部的元素弹出
swap()	交换2个栈中的元素

来看一个不常用的函数。

• 解释：交换2个容器适配器中的内容
• 示例:

#include <iostream>       // std::cout
#include <stack>          // std::stack
using namespace std;
int main()
{stack<int> foo, bar;foo.push(10); foo.push(20); foo.push(30);bar.push(111); bar.push(222);foo.swap(bar);cout << "size of foo: " << foo.size() << '\n';  //size of foo: 2cout << "size of bar: " << bar.size() << '\n';  //size of bar: 3return 0;
}

这里主要展示一些常用的操作函数，至于使用方法跟其它的STL一样，所以就不在演示了。

---

queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   • empty：检测队列是否为空
   • size：返回队列中有效元素的个数
   • front：返回队头元素的引用
   • back：返回队尾元素的引用
   • push_back：在队列尾部入队列
   • pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
   

queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	把队尾元素val入队列
pop()	将队头元素出队列

容器适配器

容器适配器（Container Adapter）是一种设计模式，它允许将一种容器类（如 std::vector、std::list、std::deque 等）的接口适配到另一种容器类上。在C++标准模板库（STL）中，有三种容器适配器：stack、queue 和 priority_queue。
这些适配器提供了特定的接口，使得它们可以被当作特定的数据结构来使用，而底层实际使用的是其他容器。以下是每种容器适配器的简要说明：

1. stack（栈）：它提供了后进先出（LIFO）的数据结构接口。stack 适配器通常使用 std::deque 或 std::vector 作为底层容器。
2. queue（队列）：它提供了先进先出（FIFO）的数据结构接口。queue 适配器通常使用 std::deque 作为底层容器。
3. priority_queue（优先队列）：它提供了一个优先级队列的接口，其中元素按照优先级顺序排列，最高优先级的元素最先被移除。priority_queue 适配器通常使用 std::vector 作为底层容器，并使用堆（heap）数据结构来维护元素的顺序。

容器适配器的优点包括：

• 封装性：它们隐藏了底层容器的具体实现细节，使得用户可以专注于使用特定的数据结构口。
• 灵活性：通过改变底层容器，可以轻松地改变容器适配器的行为。
• 一致性：它们遵循STL的一致性原则，使得代码更加模块化和可重用

---

stack和queue的模拟实现

stack的模拟实现

先来看看栈的基本结构

template<class T>class stack{private:vector<int> _con;}_

这个结构的成员_con的类型是vector<int>，后续对stack进行操作，实际上就是对vector进行操作。在进行操作之前，我们要先想清楚用vector的头部还是尾部来做栈的顶部，答案是用vector的尾部来做栈的顶。因为当在头部进行插入或者删除数据时，其它元素也会跟着移动，这会降低程序的性能。所以用尾部是最合适的。
入栈：就是对vector尾插

void push(const T& x)
{_con.push_back(x);
}

出栈：就是对vector尾删

void pop()
{_con.pop_back();
}

取栈顶：就是对vector取尾部元素

T& top()
{return _con.back();
}

判空和元素个数：跟vector的操作一样

void empty()
{_con.empty();
}size_t size()
{return _con.size();
}

那么在上面既然讲到了容器适配器，就说明还能使用其它的容器来对stack进行操作。比如说用list进行操作的话，难道还需要重新写一个list<int>的版本吗?那肯定是不需要的，只需要传入第二个参数就行了，如下所示：

template<class T,class Container = vector<T>>class stack{private:Container _con;}

第二个参数Container的底层容器就是默认用vector实现的，如果不传入第二个参数就默认为vector。如果想用list容器来实现stack，形式如下：
stack<int, list<int>>

---

queue的模拟实现
这里就直接展示代码了，跟stack的原理一样。不过queue的实现使用list比较合适，因为queue需要头删，使用list进行头删代价比较小，而且vector没有头删，只有指定删除位置上的元素，代价比较大，而list有头删，所以使用list是最合适的。

template<class T,class Container = list<T>>
class queue
{
public:queue(){}void push(const T& x)
{_con.push_back(x);
}void pop()
{_con.pop_front();
}const T& front()
{return _con.front();
}const T& back()
{return _con.back();
}bool empty()
{return _con.empty();
}size_t size()
{return _con.size();
}private:Container _con;};

---

deque的简单介绍（了解）

deque的原理

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

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

如果想头插或者尾插元素，插入的顺序就如下图所示：

可以看到，我们进行头部插入，不会影响其他数据，这是它相对于vector的优势。而由于其内存是部分连续的，可以通过中控数组的指针偏移量与小数组的指针偏移量来锁定元素。所以其也可以支持下标随机访问。

deque的优缺点

优点：

1. 两端快速插入和删除：std::deque允许在队列的前端和后端进行快速的插入和删除操作，这比std::vector和std::list更有优势。
2. 内存分配：std::deque使用多个固定大小的块来存储元素，这可以减少内存分配和复制操作，特别是在频繁插入和删除时。
3. 随机访问：与std::list不同，std::deque提供了随机访问迭代器，这意味着可以快速访问任何元素，就像std::vector一样。
4. 灵活性：std::deque结合了std::vector的随机访问特性和std::list的快速两端操作特性。
   缺点：
5. 内存使用：由于std::deque使用多个块来存储元素，它可能会比std::vector使用更多的内存，因为每个块之间需要额外的空间来存储块的指针。
6. 连续性：与std::vector不同，std::deque中的元素不是存储在连续的内存块中的，这可能会影响某些算法的性能。
7. 迭代器失效：在std::deque中，除了在两端进行操作外，其他插入和删除操作可能会导致迭代器失效。

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

---

deque与vector和list的区别

	deque	vector	list
内存分配	非连续内存分配，使用多个块	连续内存分配，适合随机访问	节点链表，每个节点包含数据和指向前后指针的节点
插入和删除性能	在两端插入和删除元素时非常高效	在中间插入和删除元素时，可能需要移动大量的元素	在任意位置插入和删除元素时都非常高效
随机访问	支持随机访问	支持随机访问	不支持随机访问，只能顺序访问
内存局部性	由于使用多个块，内存局部性不如vector	由于元素存储在连续内存中，具有很好的内存局部性	不支持随机访问，只能顺序访问
迭代器失效	在中间插入或删除元素时，可能会使所有迭代器失效	在中间插入或删除元素时，可能会使部分迭代器失效	在任何位置插入或删除元素，都不会使迭代器失效

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

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

---

deque的使用

deque的文档介绍

• 示例：

#include <iostream>  
#include <deque>  int main ()  
{  unsigned int i;  // constructors used in the same order as described above:  deque<int> first;                                // 空的队列  deque<int> second (4,100);                       // 初始化为4个100的second队列 deque<int> third (second.begin(),second.end());  // 迭代器区间 deque<int> fourth (third);                       // 复制third // the iterator constructor can be used to copy arrays:  int myints[] = {16,2,77,29};  deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );  cout << "The contents of fifth are:";  for (deque<int>::iterator it = fifth.begin(); it!=fifth.end(); ++it)  cout << ' ' << *it;  //The contents of fifth are: 16 2 77 29cout << '\n';  return 0;  
}

下面直接展示deque的函数，就不介绍使用方法