栈(stack)是一种数据结构,它遵循一个简单的规则,即后进先出(Last in First out, LIFO)。
栈的工作方式很容易理解,用一个图表形象的表示就是这样,见图1:

图1

这个只有上端开口的容器,就是用来存放数据的栈,我们要取容器中的东西,必须从最顶端开始,一个一个拿掉,才能取到我们想要的,而如果要放一个元素呢,也只能放在最顶端,这也就是栈的后进先出原则。
这样的数据结构可以使用C++标准库来实现,非常简单,下面就对C++标准库中的栈做一点简介:
C++提供了三种顺序容器(sequential container)vector(支持快速随机访问)、list(支持快速插入删除)、deque(双端队列),vector比较类似与数组,而list则更加像链表结构。C++标准库为顺序容器提供了三种容器适配器(adaptor),

图2

不要被名字吓到,所谓适配器,就像你的电脑电源适配器一样,将交流电(这里是顺序容器)做出一定的调整,来适合电脑工作,也就是说,容器适配器,是利用容器来做一些更加具体事情的东西(图2)。

这三种适配器是stack(LIFO栈),queue(先进先出, First in First out, FIFO队列)以及priority_queue(有优先级管理的队列),在本篇文章中我们只介绍stack。

使用stack需要引用头文件:

初始化一个栈的方法是:

stack默认是以deque容器来实现的,如果要以其它顺序容器来实现,可以使用这样的方法创建栈:

栈的操作不多,最核心的的操作就是压栈(push),出栈(pop),如果想在栈中添加一个数据,只需要:

就可以把3这个数字,存入到容器的顶部。
如果要获取栈顶部元素的值,只需要

对于刚才的操作,就会返回一个数字3。
出栈操作,也就是删去栈顶的元素,其方法是:

需要注意一点,那就是出栈操作不会有任何返回值,所以如果要获取栈顶元素并出栈,就必须先进行获取栈顶元素的操作之后再进行出栈操作。
还有两个操作用于判断当前栈中数据的存数状况,比如:

就会告诉你目前栈内是否为空,如果什么都没有的话,那就会返回true。

则会返回栈中元素的个数,这个数字是stack<int>::size_type类型的,按理说是unsigned类型的整数,但是由于各个机器上的整数范围不同,所以使用标准库重定义的类型有助于使这个类型机器无关化,并且标准库重定义的这个类型也会保证数字的大小不会使得栈出现溢出情况。
在POJ中,一道经典的用到栈的基础题目是Web Navigation[1],该题目要求模拟出浏览器前进、后退、访问的功能,用栈来表达最为方便,访问就是压入一个元素进栈,后退就是出栈,而前进则是把后退出来的元素再按栈的规则弹出。
在这里,我给出我的代码,通过阅读这段代码,应该就可以很好的体会栈的作用,以及C++标准库中栈的使用方法。

[1] POJ 1028 Web Navigation

说点什么

1 评论 在 "栈"

提醒
排序:   最新 | 最旧 | 得票最多

[…] 队列(queue)是一种简单的数据结构,它所遵循的规则是先进先出(First in First out, FIFO),对比LIFO的数据结构“栈”,你可以阅读[这篇文章]。这里所说的队列和我们现实中的队列是一样的,就比如说公交车排队,早到的,排在靠前位置的人自然可以优先上车(假设大家都很文明),利用这种特性,人们可以用来管理各种各样需要按照先后循序的事物,比如银行,因为银行的服务窗口有限,不能同时给所有人提供服务,所以利用计算机提供一个队列系统,给客户一个排队号码,计算机系统可以根据这个排队号码的大小来决定为谁优先提供服务。 按照和栈类似的介绍方法,为了使代码的表意更加明确,我使用C++标准库提供的队列适配器queue来构造队列这种数据结构。 使用queue需要引用头文件: […]