星星博客 »  > 

6-5-1:STL之stack和queue——stack和queue的快速入门、常用接口以及适配器的概念

文章目录

  • 一:简单介绍
    • (1)stack
    • (2)queue
  • 二:stack和queue的应用
  • 三:stack和queue的模拟实现——适配器

一:简单介绍

stackqueue是STL中的两个容器,分别对应数据结构中的栈和队列,在这里关于它的具体接口的使用就不做过多介绍了,逻辑上完全和数据结构一致,接口方面和之前我们学习过的vectorlist都十分相似

数据结构之栈和队列

(1)stack

在这里插入图片描述

(2)queue

在这里插入图片描述

二:stack和queue的应用

LeetCode有关栈的题目

stack经典题

LeetCode有关队列的题目

queue经典题

三:stack和queue的模拟实现——适配器

查看STL中stack的queue的源码,你会发现,它们代码的实现不倒100行,虽然我们知道stack和queue的确接口比较少,但是还是会有疑问,七八十行怎么可能完成一个容器的编写呢
在这里插入图片描述
观看STL的分类图,我们发现stack和queue与vector和list有点区别,它们不属于普通容器,而属于适配器(配接器)
在这里插入图片描述
我们先来讨论一下什么是适配器。一想到适配器,我们首先想到的就是电源适配器,电源适配器的作用就是将220v的电压转化为适合我们设备的充电电压,所有电子设备都需要充电,但不是所有电子设备都能承受得了220v的电压,所以电源适配器的作用就体现在了这里

类比上面的例子,其实我们在数据结构的那里就知道栈一般是用数组来实现的,队列一般是用链表实现的,数组和链表分别对应容器中的vector和list,你可以把vector和list想象成220v的电压,这两个容器可以完成栈和队列的所有操作,但是如果直接拿上这两个容器当作栈提供给别人使用的话,那搞不好会搞出栈的pop_front操作。所以我们必须在他们的基础上进行限制,限制某些操作,以达到我们的需求,stack和queue就是这样一个经典的例子。

下面是stack和queue的模拟实现
stack

#pragma once

#include <iostream>
using namespace std;

template <class T,class container>

class Mystack
{
public:
	void push(const T& x)
	{
		_stack.push_back(x);
	}
	void pop()
	{
		_stack.pop();
	}
	const T& top()
	{
		return _stack.back();
	}
	size_t size()
	{
		return _stack.size();
	}
	bool empty()
	{
		return _stack.empty();
	}

private:
	container _stack;
};

queue

#pragma once

#include <iostream>
using namespace std;

template <class T, class container>

class Myqueue
{
public:
	void push(const T& x)
	{
		_queue.push_back(x);
	}
	void pop()
	{
		_queue.pop();
	}
	const T& back()
	{
		return _queue.back();
	}
	const T& front()
	{
		return _queue.front();
	}
	size_t size()
	{
		return _queue.size();
	}
	bool empty()
	{
		return _queue.empty();
	}

private:
	container _queue;
};

大家可以发现,模板参数的第二个表示的就是容器,将来传参时传入的是容器,然后它就会根据这个容器在其上面封装(其实就是调用)处适合stack或queue的接口,比如stack就没有push_front这样的接口,因此也不会封装

#include "mystack.h"
#include <vector>
#include <list>
#include "myqueue.h"

int main()
{
	Mystack<int, vector<int>> test;
	test.push(1);
	test.push(2);
	test.push(3);
	test.push(4);

	Myqueue<int, list<int>> test1;
	test1.push(1);
	test1.push(2);
	test1.push(3);
	test1.push(4);

}

但是大家可能也发现了,在实际使用STL的stack和queue的时候,模板参数那里只需要传入第一个就可以了,但是我们现在实现的必须要传入第二个参数,这表明第二个模板参数应该是一个缺省值。但是这第二个参数中默认应该使用哪个容器呢?vector还是list?看来都不行,因为他们各自对stack和queue都有或多或少的局限性。在STL中使用的容器是双端队列,也就是deque

template <class T, class Sequence = deque<T> >

相关文章