【C++】—— stack & queue & deque

1 stack 与 queue 的函数接口2 适配器2.1 发现问题2.2 什么是适配器

3 stack 与 queue的模拟实现3.1 栈的基础框架3.2 栈的模拟实现3.3 队列的模拟实现

4 模板的按需实例化5 deque 的简单介绍5.1 vector 与list对比5.1.1 vector5.1.2 list

5.2 deque 的基本结构5.3 deque 的迭代器5.4 operator[] 的简单原理5.5 选择deque作为其底层容器原因

1 stack 与 queue 的函数接口

<code>stack 与 queue 的使用非常简单，相信大家看一眼他们的函数接口就会了，这里就不再过多介绍

函数说明	接口说明
s t a c k stack stack()	构造空的栈
e m p t y empty empty()	检测 s t a c k stack stack 是否为空
s i z e size size()	返回 s t a c k stack stack 中元素的个数
t o p top top()	返回栈顶元素的引用
p u s h push push()	将元素 v a l val val 压入 s t a c k stack stack 中
p o p pop pop()	将 s t a c k stack stack 中尾部的元素弹出

stack 函数接口

函数声明	接口说明
q u e u e queue queue()	构造空的队列
e m p t y empty empty()	检测队列是否为空，是返回 t r u e true true，否则返回 f a l s e false false
s i z e size size()	返回队列中有效元素的个数
f r o n t front front()	返回队列头元素的引用
b a c k back back()	返回队列尾元素的引用
p u s h push push()	在队尾元素 v a l val val 入队列
p o p pop pop()	将队头元素出队列

queue 函数接口

2 适配器

2.1 发现问题

我们看<code>stack或queue的文档，会发现有这样的介绍：

文档说<code>stack是一种容器适配器，那么适配器又是什么呢？以及它的模板参数为什么是两个，不是传一个类型就可以了吗？

d

e

q

u

e

deque

deque又是什么鬼

别急，我们现在就来学习，我们先来了解什么是适配器

2.2 什么是适配器

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另一个接口。

适配器其实就是适配器模式。设计模式总共有 23 种，设计模式就好比孙子兵法中的战术，是前人不断总结实践出来的经验方法。迭代器的设计某种程度上来说就是一种设计模式，为迭代器模式。

例如充电：现在插座是三孔的，两孔的插头想要充上电，可以用一个电源适配器进行转换

适配的本质是一种转换接口

虽然<code>stack和queue中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为栈和队列只是对其他容器的接口进行了包装。

3 stack 与 queue的模拟实现

3.1 栈的基础框架

根据我们前面学习STL库中的其他容器的经验

我们模拟实现栈，其基本结构可以是这样的

namespace my_stack

{

template<class T>

struct stack

{

public:

//成员函数···

private:

T* _a;

size_t _top;

size_t _capacity;

};

}

现在，我们学习了适配器模式，可以不用上述方式去实现。

我们尝试使用适配器的方式去实现。

我们想，可不可以像库中的一样用其他的容器进行封装转换一下，从而实现一个栈呢？

可以的，因为栈主要支持两个东西：在栈顶插入

p

u

s

h

push

push 和在栈顶删除

p

o

p

pop

pop。那理论上只要那个容器支持在同一端插入和删除就能够支持栈。那 vector 和 list 都支持，这样我们的栈就不需要我们自己去实现，直接封装一下

v

e

c

t

o

r

vector

vector 或

l

i

s

t

list

list 不就行了。

如下：

template<class T>

class stack

{

public:

//成员函数

private:

vector<T> _v;

};

但这样写，无疑就写死了，于是有人发明了如下写法：

template<class T, class Container = vector<T>>

class stack

{

public:

//成员函数

private:

Container _con;

};

这里，用

C

o

n

t

a

i

n

e

r

Container

Container 适配转换出

s

t

a

c

k

stack

stack

那

C

o

n

t

a

i

n

e

r

Container

Container 是什么类型呢？默认是

v

e

c

t

o

r

vector

vector，如果传

l

i

s

t

list

list 就是

l

i

s

t

list

list，传其他容器就是其他容器

3.2 栈的模拟实现

那接下来实现一个栈就很容易啦，只需复用 Container 中的成员函数即可

namespace my_stack

{

// Containerתstack

template<class T, class Container = vector<T>>

class stack

{

public:

void push(const T& x)

{

_con.push_back(x);

}

void pop()

{

_con.pop_back();

}

const T& top() const

{

//return _con.func();

return _con.back();

}

size_t size() const

{

return _con.size();

}

bool empty() const

{

return _con.empty();

}

private:

Container _con;

};

}

3.3 队列的模拟实现

学习了

s

t

a

c

k

stack

stack 的模拟实现，队列的模拟实现就很简单啦，他们都是类似的。

需要注意的是队列是先进后出，即一端进另一端出，就不再适合用

v

e

c

t

o

r

vector

vector，这里我们的默认容器改为

l

i

s

t

list

list

namespace my_list

{

template<class T, class Container = list<T>>

class queue

{

public:

void push(const T& x)

{

_con.push_back(x);

}

void pop()

{

_con.pop_front();

}

const T& front() const

{

return _con.front();

}

const T& back() const

{

return _con.back();

}

size_t size() const

{

return _con.size();

}

bool empty() const

{

return _con.empty();

}

private:

Container _con;

};

}

4 模板的按需实例化

我们使用自己实现的队列，使用

v

e

c

t

o

r

vector

vector 作为容器有没有问题呢？

int main()

{

my_list::queue<int, vector<int>> q1;

q1.push(1);

q1.push(2);

q1.push(3);

return 0;

}

可以看到，是没问题的。

可是不应该啊，因为模板中我们实现的<code>pop()函数调用了容器的pop_front()函数，而 vector 容器是没有 pop_front() 函数的，这不应该报错吗？

这里要讲一个新的知识点：按需实例化

类模板实例化时，编译器只会实例化那些显式调用了的函数，使用哪些成员函数就实例化哪些，不会全部实例化

my_list::queue<int, vector<int>> q1; 这一句代码是把类模板实例化了。但是将这个类模板实例化了，编译器会将这个类所有的成员函数都实例化吗？不会，编译器实例化这个类时，它的原则是：用什么成员函数实例化哪些成员函数。

而编译器对模板只会检查大框架（比如：漏了一个 ‘;’），而不会检查具体的实现细节。编译器只会对实例化了的东西进行细致的检查。

上述代码，编译器只实例化了

p

u

s

h

push

push 和 构造函数，剩下的函数都没实例化。而

p

o

p

pop

pop 函数并没有被实例化。没有实例化，没有生成具体的函数，里面的语法自然就不会细节地去检查

int main()

{

my_list::queue<int, vector<int>> q1;

q1.push(1);

q1.push(2);

q1.push(3);

q1.pop();

return 0;

}

调用了

p

o

p

pop

pop 函数才会报错。

所以模板没有全部使用之前，并不能保证里面的语法没有问题

5 deque 的简单介绍

不知大家发现没有，库中 <code>stack 和 queue 的默认容器并不是

v

e

c

t

o

r

vector

vector 或

l

i

s

t

list

list，而是 deque。

那么

d

e

q

u

e

deque

deque 是什么呢？我们一起来简单了解一下。

5.1 vector 与list对比

我们先来简单对比一下

v

e

c

t

o

r

vector

vector 与

l

i

s

t

list

list 的优缺点

5.1.1 vector

优点:

<code>尾插尾删效率不错，支持高效下标随机访问物理空间连续，所以高速缓存利用率高

缺点:

空间需要扩容，扩容有一些代价（效率和空间浪费）头部和中部插入删除效率低

5.1.2 list

优点：

按需申请释放空间，不需要扩容任意位置插入删除效率高

缺点:

不支持下标随机访问物理空间不连续，高速缓存利用率低

5.2 deque 的基本结构

deque 的中文名是：双端队列，虽然名字和

q

u

e

u

e

queue

queue 有点像，但它和

q

u

e

u

e

queue

queue 没有任何关系。

d

e

q

u

e

deque

deque 可以看成是

v

e

c

t

o

r

vector

vector 和

l

i

s

t

list

list 的缝合。

d

e

q

u

e

deque

deque 是由一段一段小数组（这里取名为

b

u

f

f

buff

buff 数组）和一个中控数组组成。

中控数组是一个指针数组，放着每一个 buff 数组的指针。而

b

u

f

f

buff

buff 数组则存放数据。第一个

b

u

f

f

buff

buff 的数组会放在中控数组的中间

如果进行头插，则在中控数组最前面增加一个数组指针，并在

b

u

f

f

buff

buff 数组从后往前插入数据；如果尾插，则在中控数组最后面增加数组指针，并在

b

u

f

f

buff

buff 数组中从前往后插入数据。

如果空间不够需进行扩容，<code>只需扩容中控数组拷贝中控数组的指针，并新开辟一个 buff 即可

5.3 deque 的迭代器

d

e

q

u

e

deque

deque 的迭代器由四个指针组成

<code>cur：指向当前访问

b

u

f

f

buff

buff 的数据first：指向一个

b

u

f

f

buff

buff 的开始last：指向一个

b

u

f

f

buff

buff 的结束node：为二级指针，反向指向中控数组

那么

d

e

q

u

e

deque

deque 的迭代器是如何管理整个结构的呢？

我们结合图来简单了解一下

d

e

q

u

e

deque

deque 中主要的成员变量由两个迭代器组成：<code>start 和 finish。

s

t

a

r

t

start

start 即

b

e

g

i

n

begin

begin() 返回的迭代器；

f

i

n

i

s

h

finish

finish 即

e

n

d

end

end() 返回的迭代器。

当用迭代器遍历整个

d

e

q

u

e

deque

deque：

iterator it = begin();

while(it != end())

{

cout << *it << " ";

++it;

}

while(it != end())，!= 其实比较的是迭代器中的

c

u

r

cur

cur 是否相等cout << *it << " "; *it，其本质是解引用

c

u

r

cur

cur++it;分为两种情况

当前的

b

u

f

f

buff

buff 没有走完（判断条件

c

u

r

cur

cur !=

l

a

s

t

last

last）：++cur当前

b

u

f

f

buff

buff 走完（判断条件

c

u

r

cur

cur ==

l

a

s

t

last

last）：通过

n

o

d

e

node

node 找到当前 buff 地址在中控数组的位置，++

n

o

d

e

node

node 找到下一个

b

u

f

f

buff

buff 的地址，解引用就是下一个

b

u

f

f

buff

buff。更新

f

i

r

s

t

first

first 与

l

a

s

t

last

last，

c

u

r

cur

cur 指向第一个位置。

5.4 operator[] 的简单原理

这里讲一下

o

p

e

r

a

t

o

r

operator

operator[] 的实现，即查找第 i 个数据。

因为第一个

b

u

f

f

buff

buff 前面的空的，所以先对第一个buff特殊处理，先判断是否在第一个

b

u

f

f

buff

buff 中。之后假设第一个buff是满的。比如第一个

b

u

f

f

buff

buff 只有后面三个位有数据，则假设补满；找第

i

i

i 个数据，改为找第

i

i

i + 5 个后通过 i / N 找到第

n

n

n 个

b

u

f

f

buff

buff，再通过 i % N 找到其在第

n

n

n 个

b

u

f

f

buff

buff 的第

m

m

m 个位置。（

N

N

N 为每个

b

u

f

f

buff

buff 的长度）

这里我们演示一下

d

e

q

u

e

deque

deque 的

o

p

e

r

a

t

o

r

operator

operator[] 效率：

void test1()

{

srand(time(0));

const int N = 1000000;

deque<int> dq;

vector<int> v;

for (int i = 0; i < N; ++i)

{

auto e = rand() + i;

v.push_back(e);

dq.push_back(e);

}

int begin1 = clock();

sort(v.begin(), v.end());

int end1 = clock();

int begin2 = clock();

sort(dq.begin(), dq.end());

int end2 = clock();

printf(" vector:%d\n", end1 - begin1);

printf(" deque:%d\n", end2 - begin2);

}

相差两倍左右

<code>void test1()

{

srand(time(0));

const int N = 1000000;

deque<int> dq1;

deque<int> dq2;

for (int i = 0; i < N; ++i)

{

auto e = rand() + i;

dq1.push_back(e);

dq2.push_back(e);

}

int begin1 = clock();

sort(dq1.begin(), dq1.end());

int end1 = clock();

int begin2 = clock();

// 拷贝到vector

vector<int> v(dq2.begin(), dq2.end());

sort(v.begin(), v.end());

dq2.assign(v.begin(), v.end());

int end2 = clock();

printf(" deque sort:%d\n", end1 - begin1);

printf(" deque copy vector sort, copy back deque:%d\n", end2 - begin2);

}

依然是

v

e

c

t

o

r

vector

vector 快，同时也可以看成拷贝的代价是很低的

5.5 选择deque作为其底层容器原因

d

e

q

u

e

deque

deque的优缺点：

d

e

q

u

e

deque

deque 的<code>头插尾插效率很高，更甚于

v

e

c

t

o

r

vector

vector 和

l

i

s

t

list

list下标随机访问也还不错，但相比

v

e

c

t

o

r

vector

vector 略逊一筹但中间插入效率很低，需要挪动数据，是 O(

n

n

n)deque 在实践中应用并不多，主要是用于

s

t

a

c

k

stack

stack 和

q

u

e

u

e

queue

queue 的底层结构

s

t

a

c

k

stack

stack 和

q

u

e

u

e

queue

queue 不需要遍历(因此

s

t

a

c

k

stack

stack 和

q

u

e

u

e

queue

queue 没有迭代器)，只需要在固定的一端或者两端进行操作，完美符合

d

e

q

u

e

deque

deque 头插尾插效率高的优点。

在

s

t

a

c

k

stack

stack 中元素增长时，

d

e

q

u

e

deque

deque 比

v

e

c

t

o

r

vector

vector 的效率高(扩容时不需要搬移大量数据)；

q

u

e

u

e

queue

queue 中的元素增长时，

d

e

q

u

e

deque

deque不仅效率高，而且内存使用率高（不需要频繁开辟细碎的空间）。 结合了

d

e

q

u

e

deque

deque 的优点，而完美的避开了其缺陷。

---

好啦，本期关于

s

t

a

c

k

stack

stack &

q

u

e

u

e

queue

queue &

d

e

q

u

e

deque

deque 的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！