C嘎嘎探索篇:和stack,queue的再次相遇
前言:
小编在前几日刚完成了关于list容器的介绍,中间由于我牙齿出现了问题所以断更了不少天,如今我牙齿已经恢复,我也要开始继续新内容的讲解了,各位读者朋友要好好爱护牙齿,今天小编要讲述的是我们所熟知的老朋友——栈和队列,它们都是适配器,可能很多读者朋友好奇适配器是个什么东西,不要着急,下面就进入今天的教学时间。
文章目录
- C嘎嘎探索篇:和stack,queue的再次相遇
- 1.容器适配器
- 1.1.什么是适配器
- 1.2.STL标准库中的stack和queue的底层结构
- 2.stack
- 2.1.stack的介绍
- 2.2.stack的使用
- 2.2.1.stack()
- 2.2.2.empty()
- 2.2.3.size()
- 2.2.4.push()
- 2.2.5.pop()
- 2.2.6.top()
- 3.queue
- 3.1.queue的介绍
- 3.2.queue的使用
- 3.2.1.queue()
- 3.2.2.empty()
- 3.2.3.size()
- 3.2.4.push()
- 3.2.5.pop()
- 3.2.6.front()
- 3.2.7.back()
- 4.总结
正文:
1.容器适配器
1.1.什么是适配器
适配器是一种设计模式(设计模式是一种被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。可能刚开始读者朋友看不懂我说的这句话到底是什么意思,其实这部分内容最好是在我进行stack和queue的模拟实现中才能体现的淋漓尽致,不过我在开头说过,stack和queue并不是容器,而是一个适配器,如果我不说的话各位可能懵逼的看完全文,索性我先提前说一说,对于适配器,各位肯定不陌生,我们日常给笔记本充电的时候,就是用的电源适配器,就是把我们日常使用的电转换到了笔记本里面,这就对应着了将一个类的接口转换成客户希望的另外一个接口这一句话。等会我要讲述的容器适配器也和这个原理差不多,下面我们就揭开容器适配器的神秘面纱。
1.2.STL标准库中的stack和queue的底层结构
虽然stack和queue中也可以存放元素,但在STL库中并没有把其划分为容器的行列,而是将称之为容器适配器,这是因为stack和queue只是对其他容器进行包装罢了,在STL库中stack和queue都默认使用的是deque,deque的中文是双端队列的意思,它是STL库中的容器,它是小编从开学容器到现在觉着最复杂的一个容器,因为它是介于list和vector容器之间的一个容器,小编目前是不会讲这个容器的,因为我也没有掌握它,所以就不误人子弟了,等我以后学到一定程度的话,希望我会写一篇文章来弥补deque这个大坑。
下面小编将会分别讲述stack和queue是如何进行运用的,相信之前学过数据结构的读者朋友对着两个数据结构都是不陌生的,所以我就不在详细介绍他们的样子了,下面小编先讲述一下stack的使用~
2.stack
2.1.stack的介绍
stack就是我们熟知的栈,栈的结构是典型的后进先出结构,其结构图如上图所示,可以看出它是从一端进一端出,由于进出都是同一端,所以很好明白最后一个进入的元素肯定是第一个出去,对于栈更详细的介绍,感兴趣的读者朋友可以瞅一眼我之前写过的一篇文章:数据结构——栈的讲解(超详细)_栈数据结构-CSDN博客,这是我之前写过的关于栈的文章,还没学过的可以看一眼(按理说开始学STL了应该都知道一些基础的数据结构了,当然不能排除一些没学过的读者朋友),这便是对于stack的介绍,下面小编讲述一下关于stack的使用。
2.2.stack的使用
上图便就是stack的一些接口,和小编之前讲述的容器一对比,简直就是大巫见小巫,可能很多人会想stack的使用想必是很简单的,这确实是正确的,想必经过前面容器的“洗礼”以后,各位对于stack的使用会变的非常熟练,值得注意的是,stack并没有[]运算符的重载,也没有迭代器,这样做的原因是因为顺应栈的结构,栈的结构是不支持随便遍历数据的,我们只能访问栈顶的数据,严格来说栈里面的数据我们是访问不到的,所以就不会有这些遍历相关的函数实现,下面小编就要讲述栈相关接口的使用,当然我还是讲述部分功能,学完了这些功能的读者朋友可以自行去学习一下其他接口的使用。
函数说明 | 接口说明 |
---|---|
stack() | 构造空的栈 |
empty() | 检测stack是否为空 |
size() | 返回stack中元素的个数 |
top() | 返回栈顶元素的引用 |
push() | 将元素va压入stack中 |
pop() | 将stack中尾部的元素弹出 |
2.2.1.stack()
这个函数作用是很简单的,学过STL其中一个容器的朋友都知道,这个函数作用就是构造一个空的stack,这是stack众多构造函数的其中一种,下面小编展示它的用法:
using namespace std;
stack<int> s1; //stack也是一个模板类,所以想要实例化对象就要显示实例化对象
2.2.2.empty()
这个函数的功能也是很好理解的,它的名字就是它的功能,所以它的功能就是判断一个栈是否为空,如果为空的话就返回0(假),如果不为空的话就返回非0(真),下面小编展示它的用法:
using namespace std;
stack<int> s1;
if(s1.empty())return 1;
elsereturn 0; //此时这个栈我并没有去插入数据,所以肯定是返回1,我就不打印展示了。
2.2.3.size()
这个函数想必各位也是不陌生了,它的功能就和它的名字一样,返回栈中元素的个数,由于难度不大,我就直接展示用法了:
using namespace std;
stack<int> s1;
s1.push(1); //先超纲一下,这个是插入函数
cout << s1.size() << " "; //此时我们仅仅往栈里插入了一个元素,所以栈里面元素的个数其实是1个,所以打印出1
2.2.4.push()
这个函数我在上面浅浅的用了一下,其实这个名字也是告知了我们它的功能是插入元素,因为栈是一个比较特殊的结构,它想要插入元素就必须在栈顶进行插入,也就是我们熟知的入栈操作,所以只有一个插入函数,它的用法其实很简单的,下面我就简单的介绍一下:
using namespace std;
stack<int> s1;
s1.push(1);
s1.push(3);
s1.push(4);
s1.push(3); //大抵就是这么使用的,此时的栈里面是3 4 3 1从顶到底
2.2.5.pop()
这个函数的功能也是很容易知道的,它在多个容器都出现过,它的作用就是删除元素,由于栈结构的特殊性,它仅仅可以删除栈顶的元素,也就是我们熟知的出栈操作,下面小编就展示它的用法:
using namespace std;
stack<int> s1;
s1.push(1);
s1.push(3);
s1.push(4);
s1.pop(); //此时把栈顶删除了,所以里面还有3 1.
2.2.6.top()
这个函数的功能看起来比较新奇,其实写过栈的读者朋友都知道它是来干什么的,它的功能和它的名字一样,top有顶的意思,所以它的功能和栈顶有关,它的作用是返回栈顶元素,这是我们可以遍历栈里面元素唯一的方式,我们一般通过它来遍历一个栈,下面小编就展示一下它的复合用法:
using namespace std;
stack<int> s1;
s1.push(1);
s1.push(3);
s1.push(4);
s1.push(2);
while(!s1.empty())
{cout << s1.top() << " ";s1.pop();
}
以上便就是stack一些接口的使用,stack的使用其实是很简单的,当然我还是那一句话,如果有的读者朋友没学过数据结构,最好是学完了数据结构的栈再看本文章,这样的话就是如鱼得水了,看的会很顺畅,用的也会很顺畅,当然如果学过了一些容器后,就是纯纯的享受学习栈的过程了,栈的讲解就到这了,下面小编就讲述一下栈的另一个兄弟,队列的讲解。
3.queue
3.1.queue的介绍
queue也是我们之前学过的数据结构,他就是队列,与栈一样,队列也是一种容器适配器,专门用于FIFO上下文(先进先出)中操作,它是从容器的一端插入元素,从容器的另一端取出元素。也就是”双开门“的结构,对于队列更加详细的介绍,小编也写过相关的文章,没学过队列的读者朋友可以去看一看:数据结构——队列的讲解(超详细)_队列数据结构csdn-CSDN博客,这就是对于queue的介绍,下面进入queue的功能的讲解。
3.2.queue的使用
上图便就是queue一些接口的使用,和栈一样,它的接口也是蛮少的,因为队列的结构也是很特殊的,他也是只有一个插入函数和删除函数,毕竟队列一般只能从一端进入,从一端出去,所以一个插入和删除函数就好了,当然因为队列是双向的,所以对于它元素的取出,既可以从头拿去,也可以从结尾拿起,但是一般我们都是从尾部进,头部出元素,所以都是取的队头的元素,下面小编就开始对这些接口的讲述。
3.2.1.queue()
这个函数小编在上面的stack就展示过用法了,它的作用就是构造一个空的队列,当然构造函数不止这一个,不过我们一般也就是这么使用队列,下面小编给出它的用法:
using namespace std;
queue<int> s1(); //括号也可以不用写,编译器会自动调用默认构造的。
3.2.2.empty()
这个函数我前面也说过了,它的作用就是检测队列是否为空,如果队列为空的话,那么会返回真(非0);反之则会返回加(0),它的作用在我们遍历队列的时候会很明显,下面小编就展示它的使用方法:
using namespace std;
queue<int> s1;
if(s1.empty())return 1;
elsereturn 0; //因为此时的队列我并没有插入元素,所以此时的队列是个空队列,所以会返回1,我就不打印展示了
3.2.3.size()
这个函数的作用也是很容易的,它的作用就是返回队列中有效元素的个数的,其实当我讲述完了栈的相关接口以后,队列的接口各位也会很好去理解,因为它俩的关联性很大,只有在底层实现的时候才会看出它们细微的差别的,下面小编展示这个函数的用法:
using namespace std;
queue<int> s1;
s1.push(1); //超纲一下
cout << s1.size() << " "; //这里我插入了一个元素,所以队列里面有一个元素,所以会打印出1
3.2.4.push()
这个函数的作用就是入队列,由于队列结构的特殊性,所以它是从一端进入(一般就是从队尾进),所以插入函数仅有一个,它就代表着入队列,下面小编展示它的用法:
using namespace std;
queue<int> s1;
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4); //此时队列的元素从队头到队尾依次是:1,2,3,4.
3.2.5.pop()
有入队列自然就有出队列,这个函数的作用就是出队列,从另一端进入了,自然可以从另一端出队列(一般是队头出),下面我直接展示它的用法:
using namespace std;
queue<int> s1;
s1.push(1);
s1.push(3);
s1.push(4);//此时队列元素的分布式1,3,4
s1.pop();//此时经过一次出队列以后就变成了3,4
3.2.6.front()
这个函数算是一个比较新的函数了,当然我记着很多容器都有这个接口,但我似乎懒了一下就没讲(没想到报应还是来了(╥╯^╰╥)),这个函数的作用是返回第一个位置的元素,在队列中就是返回队头的元素,它搭配别的接口可以实现一个队列的遍历,下面小编就展示一下它的使用方法:
using namespace std;
queue<int> s1;
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
while(!s1.empty())
{cout << s1.front() << " ";s1.pop();
}
3.2.7.back()
这个函数也是一个比较新的函数,很多容器也是有这个接口的使用,我依旧没讲(没想到报应来的这么快(╥╯^╰╥)),这个函数的作用就是返回最后一个有效元素的数据,在队列中就是返回队尾的数据,不过它是不可以进行遍历队列了,因为队列默认是队尾进,堆头出,所以我们知晓最后一个元素是什么没啥用,因为后进后出的原则,它是最后一个出去的,下面小编给出它的使用方法:
using namespace std;
queue<int> s1;
s1.push(1);
s1.push(2);
s1.push(3);
cout << s1.back() << endl; //此时打印的是3,我就不展示打印结果了
以上便就是对于queue的一些函数接口的说明,对于queue,我们要熟悉它的接口的使用方法,在很多题目上栈和队列是解决题目的关键,各位一定要好好掌握这些接口,当然不要死记硬背,死记硬背是学不好编程的,只要我们勤加练习,练习多了我们自然就学会了这些接口的使用。
4.总结
此时到这里,这篇文章就算结束了,栈和队列相比于其他容器讲起来还是挺轻松的,学习和用起来也是很简单的,本来我想在本文也写出它们的模拟实现的,但是我想了想似乎没必要,文章写的很多观感我认为不好,所以我就拆开进行讲解了,各位一定要好好的掌握好这部分内容,为了模拟实现做出铺垫,在文章的最后,我还是呼应一下开头,各位一定要好好爱护自己的牙齿,这牙齿痛起来是真要命┭┮﹏┭┮,那么各位大佬们,我们下一篇文章见啦。