【C++】STL中stack、queue、deque的使用

前言：在前面我们学习了List的模拟实现与使用，今天我们进一步的来学习stack、queue、deque的使用方法，然后为后面的模拟实现做一下铺垫。

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:高质量Ｃ++学习 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！

注:这里不会注重讲什么是栈和队列，只会大概的解释一下，不懂的可以看看前面的博客有详细讲解:栈和队列

栈的常见功能

1. 入栈
2. 出栈
3. 获取栈顶元素
4. 检测栈是否为空
5. 获取栈中有效元素个数

stack的常见使用方法

1. 包含头文件：首先，需要包含 头文件

#include <stack>

2. 创建Stack对象：使用 std::stack 模板类创建Stack对象

std::stack<int> myStack;

3. 元素入栈：使用 push() 函数将元素添加到栈的顶部

myStack.push(10);//入栈
myStack.push(20);
myStack.push(30);

4. 元素出栈：使用 pop() 函数从栈的顶部移除元素

myStack.pop();//栈顶的元素出栈

5. 访问栈顶元素：使用 top() 函数访问栈顶的元素

int topElement = myStack.top();//获取栈顶元素

6. 获取栈中元素的个数：使用 size() 函数获取栈中元素的个数

int stackSize = myStack.size();//获取栈中元素个数

7. 检查栈是否为空：使用 empty() 函数检查栈是否为空

int main()
{
	stack<int>s1;
	s1.push(20);
	s1.push(30);
	s1.push(40);
	if (s1.empty())
	{
		cout << "空栈" << endl;
	}
	else
		cout <<"该栈的元素个数是: " << s1.size() << endl;
	return 0;
}

队列的常见功能

1. 队尾 入队列
2. 队头出队列
3. 获取队列头部元素
4. 获取队尾元素
5. 检测队列是否为空
6. 获取队列中有效元素个数

queue的常见使用方法

在C++中，我们可以使用STL（Standard Template Library）的queue容器来实现队列。以下是queue的常见使用方法：

1. 包含头文件：在使用queue之前，我们需要包含头文件。

#include <queue>

2. 创建队列：使用queue类来创建一个队列对象。

queue<int> q; // 创建一个整型队列

3. 入队操作：使用push()函数将元素添加到队列的末尾。

q.push(10); // 将元素10添加到队列末尾

4. 出队操作：使用pop()函数从队列的头部移除并返回元素。

q.pop(); // 移除队列的头部元素

5. 访问队头元素：使用front()函数可以访问队列的头部元素。

int frontElement = q.front(); // 获取队列头部元素,但不移除

6. 判断队列是否为空：使用empty()函数可以检查队列是否为空。

bool isEmpty = q.empty(); // 如果队列为空，则返回true，否则返回false

例子：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    
    q.push(10);
    q.push(20);
    q.push(30);
    
    std::cout << "Queue size: " << q.size() << std::endl;
    
    while (!q.empty())//将队列中的元素依次出队列，知道队列为空 
    {
        int frontElement = q.front();
        std::cout << frontElement << " ";
        q.pop();
    }
    
    return 0;
}

输出：

Queue size: 3
10 20 30

什么是deque

在C++中，deque（双端队列）是一种线性容器，允许在两端进行插入和删除操作。deque是 “double-ended queue” 的缩写。

deque类似于vector，但不同之处在于deque允许在容器的前端和后端进行高效的插入和删除操作，而vector只支持在末尾进行插入和删除操作。deque还提供了随机访问元素的能力，类似于数组。

deque的主要特点包括：

在两端进行高效的插入和删除操作。
随机访问元素的能力。
动态分配存储空间，自动扩展和收缩容量。

deque的常见功能

deque（双端队列）是C++标准库中的一种容器，提供了以下常见功能：

1. 在队列的前端和后端进行插入和删除操作。
2. 可以在常量时间内在队列的前端和后端访问元素。
3. 支持随机访问，可以通过索引访问元素。
4. 动态分配内存，可以根据需要自动扩展和收缩容量。
5. 可以在队列的任意位置插入或删除元素。
6. 可以使用迭代器进行遍历和操作。
7. 支持使用构造函数和初始化列表进行初始化。
8. 提供了一系列的成员函数来获取队列的大小、判断队列是否为空等。

总之，deque提供了灵活和高效的双端队列实现，适用于需要频繁在队列的前端和后端进行操作的场景。

deque的常见使用方法

在C++中，使用deque（双端队列）的常见方法如下：

1. 头文件引入：

   #include <deque>
   

2. 创建deque对象：

   std::deque<数据类型> dequeName;
   

3. 在队列的前端和后端插入元素：

   dequeName.push_front(element); // 在队列的前端插入元素，element为数据
   dequeName.push_back(element); // 在队列的后端插入元素
   

4. 在队列的前端和后端删除元素：

   dequeName.pop_front(); // 删除队列的第一个元素
   dequeName.pop_back(); // 删除队列的最后一个元素
   

5. 访问队列的前端和后端元素：

   dequeName.front(); // 访问队列的第一个元素
   dequeName.back(); // 访问队列的最后一个元素
   

6. 访问队列中的元素：

   dequeName[index]; // 使用索引访问元素，例如 dequeName[0]，类似于数组和vector支持下标访问
   

7. 获取队列的大小：

   dequeName.size(); // 获取队列中元素的个数
   

8. 判断队列是否为空：

   dequeName.empty(); // 如果队列为空返回 true，否则返回 false
   

9. 使用迭代器遍历队列：

   int main()
   {
   	deque<int>s1 = { 1,2,3,4,5 };
   	s1.push_front(10);//队头插入元素
   	s1.push_back(20);//队尾插入元素
   	deque<int>::iterator it = s1.begin();//使用迭代器遍历deque
   	while (it != s1.end())
   	{
   		cout << *it << " ";
   		it++;
   	}
   	cout << endl;
   	return 0;
   }
   

   

10. 清空队列：

    dequeName.clear(); // 清空队列中的所有元素
    

11. 修改deque的大小:

    注:修改deque的大小为newSize。如果newSize比deque的当前大小小，则删除多余的元素；如果newSize比deque的当前大小大，则在deque的尾部添加默认值元素

    int main()
    {
    	deque<int> s1 = { 1,1,1,1,1 };
    	s1.resize(10, 2);//修改deque的大小，多余的全部变为2
    	deque<int>::iterator it = s1.begin();
    	for (auto e : s1)
    	{
    		cout << *it << " ";
    		it++;
    	}
    	return 0;
    }
    

    

这些是deque的常见使用方法，通过这些方法可以对deque进行插入、删除、访问、遍历等操作。

总结deque的优缺点:
deque（双端队列）是 C++ 标准库提供的一种容器，它允许在两端进行插入和删除操作。deque 的优点和缺点如下：

优点：

1. 支持高效的在两端进行插入和删除操作。deque 是由一系列块组成的，可以在两端分别进行操作，而不需要移动其他元素。
2. 可以动态地调整容器的大小。deque 是一个动态数组，可以根据需要动态地增加或减少容量。
3. 支持随机访问。deque 使用下标访问元素的时间复杂度为 O(1)。

缺点：

1. deque 的内存占用比较大。由于 deque 使用了一系列块来存储元素，相比于 vector 或 list，它需要额外的内存来存储块之间的指针。
2. 在插入和删除操作时可能会导致迭代器失效。当在中间位置进行插入或删除操作时，由于需要移动其他元素，可能导致迭代器失效。
3. 不支持连续的内存存储。由于 deque 的元素是存储在不同的块中的，因此它的存储不是连续的，这可能导致一些性能上的损失。
4. 不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到
   某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

总结：deque 适用于需要在两端频繁地进行插入和删除操作的场景，但如果对内存占用和连续存储有较高要求，可能需要考虑其他容器

好啦，今天的内容就到这里啦，下期内容预告stl中stack和queue的模拟实现.

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。