C++——栈和队列容器

很楠不爱 2024-07-24 11:35:02 阅读 74

前言:这篇文章我们将栈和队列两个容器放在一起进行分享,因为这两个要分享的知识较少,而且两者在结构上有很多相似之处,比如栈只能在栈顶操作,队列只能在队头和队尾操作。

不同于前边所分享的三种容器,这篇文章要介绍的两个容器,不再是单纯的空间创建存储,而是以vector、list等容器为底层来实现的容器。 


目录

一.栈

1.栈的框架

 2.功能实现

二.队列

1.队列框架

2.功能实现

三.扩展

总结


一.栈

栈的关键在于只能从栈顶进行入栈和出栈,那么我们就可以将vector或者list的头作为栈底,在尾进行操作


1.栈的框架

在数据结构的学习中我们已经知道,栈有顺序栈和链式栈两种,所以容器栈就可以按照需求,通过模板来选择是创建顺序栈还是链式栈

<code>#include<vector>

#include<list>

namespace Mystack

{

//stack<int vector<int>> 顺序栈

//stack<int list<int>> 链式栈

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

class stack

{

public:

private:

Container _con;

};

}

想要这样创建栈,就必须包含vector和list两个容器的头文件。 

通过使用两个模板参数,一个代表数据类型,一个代表栈的类型Container即英文"容器"

因为通常情况下所使用的栈都是顺序栈,所以我们为了方便栈的创建,可以将模板也写成缺省模板。缺省模板和缺省函数类似。 


 2.功能实现

我们直接来看:

//入栈

void push(const T& x)

{

_con.push_back(x);

}

//出栈

void pop()

{

_con.pop_back();

}

//数据个数

size_t size()

{

return _con.size();

}

//判空

bool empty()

{

return _con.empty();

}

//栈顶元素

const T& top()

{

return _con.back();

}

因为栈的底层是另外两种容器之一,所以我们可以直接去调用它们的成员函数来实现我们的成员函数入栈就是尾插,出栈即是尾删、依次类推。 

测试如下:


二.队列

队列不同于栈,队列是在队尾插入元素,在队头删除元素。但是我们知道,vector并不支持头部的插入删除操作,因为这样的效率很低,所以我们只推荐使用list来作为队列的底层


1.队列框架

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

class queue

{

public:

private:

Container _con;

};

2.功能实现

//入队

void push(const T& x)

{

_con.push_back(x);

}

//出队

void pop()

{

_con.pop_front();

}

//队尾元素

T& back()

{

return _con.back();

}

const T& back()const

{

return _con.back();

}

//队头元素

T& front()

{

return _con.front();

}

const T& front()const

{

return _con.front();

}

//数据个数

size_t size()const

{

return _con.size();

}

//判空

bool empty()const

{

return _con.empty();

}

仍然是调用list的成员函数来实现queue的成员函数,测试如下:

 


三.扩展

除了vector、list之外,还有一种容器可以作为队列的底层——deque

 deque的底层是由多个长度相同的数组组成,而这些数组则由一个指针数组来管理

deque能够同时支持下标随机访问和头尾的插入删除,所以除了队列之外,在C++的底层,栈和队列实际上都是由deque来实现的

 

这里我们不对deque进行展开讲解,仅供小伙伴们了解。 


总结

stack和queue的使用和模拟实现都非常简单,也算是为前边学习的复杂模拟的一点小放松。

喜欢本篇文章的小伙伴记得一键三连,我们下期再见!



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。