C++——stack和queue

目录

前言

一、接口

二、 模拟实现

三、deque双端队列（了解）

1.大致思路

2.迭代器

3.缺陷

4.为什么选择deque作为queue和stack的默认容器

前言

        不管是stack还是queue，我们都可以通过调用vector来对其进行模拟实现，实际上库里面也是这么做的，只需要在vector的外层套一层娃即可实现stack和queue。

        其实，实现stack和queue不一定必须要用vector，也可以用list，这样就会影响它的底层。比如有些时候，链式栈更能解决需求，底层就用list，顺序栈更能解决需求，就用vector。

        所以在实现stack和queue的过程中，我们除存储数据类型外要新加一个模板参数来传容器，再给这个容器一个初始值，那么这就是容器适配器。

一、接口

        这些接口看名字就能秒懂，在之前学过的容器基础上，这些已经很简单了。

stack

queue

二、 模拟实现

        stack与queue的实现都用了复用其它容器的手段，所有接口基本上也就是一行搞定

        实现过程中容器默认是deque，后面我会简单介绍一下这个容器。

stack.h

#pragma once
#include <deque>
namespace muss
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		bool empty()
		{
			return _con.empty();
		}

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

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

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

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

		void swap(const queue<T>& q)
		{
			std::swap(_con, q._con);
		}
	private:
		Container _con;
	};

	void stack_test1()
	{
		stack<int> q;
		cout << q.empty() << endl;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		cout << q.size() << endl;
		cout << q.top() << endl;
		q.pop();
		cout << q.top() << endl;
		q.pop();
		q.pop();
		cout << q.size() << endl;
		q.pop();
		cout << q.size() << endl;
		cout << q.empty() << endl;
	}

	void stack_test2()
	{
		stack<int> q1;
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);
		stack<int> q2;
		q2.push(11);
		q2.push(22);
		q2.push(33);
		swap(q1, q2);

	}
}

queue.h

#pragma once
#include <deque>
namespace muss
{
	//             数据类型   queue的底层，默认是deque，双端队列，链表和顺序表的缝合怪
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		bool empty()
		{
			return _con.empty();
		}

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

		T& front()
		{
			return _con.front();
		}

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

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

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

		void swap(const queue<T>& q)
		{
			std::swap(_con, q._con);
		}

	private:
		Container _con;
	};

	void queue_test1()
	{
		queue<int> q;
		cout << q.empty() << endl;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		cout << q.size() << endl;
		cout << q.front() << endl;
		cout << q.back() << endl;
		q.pop();
		q.pop();
		cout << q.front() << endl;
		cout << q.back() << endl;
		q.pop();
		cout << q.size() << endl;
		q.pop();
		cout << q.size() << endl;
		cout << q.empty() << endl;
	}

	void queue_test2()
	{
		queue<int> q1;
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);
		queue<int> q2;
		q2.push(11);
		q2.push(22);
		q2.push(33);
		swap(q1, q2);

 	}
}

test.cpp

#include <iostream>

using namespace std;

#include "queue.h"
#include "stack.h"

int main()
{
	//muss::queue_test2();
	muss::stack_test2();

	return 0;
}

一共也没几行

三、deque双端队列（了解）

        总所周知，vector与list各有优势，vector强在它的随机访问效率极高，但是插入删除效率很低，而list不能支持随机访问，但是插入删除效率很高。所以，有人想着能不能把vector与list整合到一块去，使这个具有两者的优势，于是deque诞生了。

1.大致思路

        把list的一个一个结点改为储存数据的定长数组，再额外搞出一个中控数组来储存各个定长数组的地址。这样，扩容只需要这个中控数组扩容，不需要挪动数据。

        可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高

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

2.迭代器

        双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂。

        它的迭代器封装了四个指针，cur是当前位置的指针，first和last分别是当前数组（结点）首位元素的指针，node是当前数组（结点）的地址，在中控数组中，依靠这四个指针，它们才能实现遍历操作。

3.缺陷

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

4.为什么选择deque作为queue和stack的默认容器