Python数据结构——栈

evin2016 发布于2019-07-31 10:49 / 1901人阅读

摘要：栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出，的数据结构。对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用方法，出栈使用方法。方法则只返回栈顶元素，而不删除它。

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。

由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法，出栈使用pop()方法。下图演示了入栈和出栈的过程。

另一个常用的操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek()方法则只返回栈顶元素，而不删除它。

为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量top，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。

push()、pop()和peek()是栈的3个主要方法，但是栈还有其他方法和属性。

stack通常的操作：

Stack()    建立一个空的栈对象
push()     把一个元素添加到栈的最顶层
pop()      删除栈最顶层的元素，并返回这个元素
peek()     返回最顶层的元素，并不删除它
isEmpty()  判断栈是否为空
size()     返回栈中元素的个数

简单案例以及操作结果：

Stack Operation	Stack Contents	Return Value
s.isEmpty()	[]	True
s.push(4)	[4]
s.push("dog")	[4,"dog"]
s.peek()	[4,"dog"]	"dog"
s.push(True)	[4,"dog",True]
s.size()	[4,"dog",True]	3
s.isEmpty()	[4,"dog",True]	False
s.push(8.4)	[4,"dog",True,8.4]
s.pop()	[4,"dog",True]	8.4
s.pop()	[4,"dog"]	True
s.size()	[4,"dog"]	2

这里使用python的list对象模拟栈的实现：

class Stack: 
    """模拟栈""" 
    def __init__(self): 
        self.items = [] 

    def isEmpty(self): 
        return len(self.items)==0  

    def push(self, item): 
        self.items.append(item) 

    def pop(self): 
        return self.items.pop()  

    def peek(self): 
        if not self.isEmpty(): 
            return self.items[len(self.items)-1] 

    def size(self): 
        return len(self.items)

创建一个栈对象，并加入操作方法：

s=Stack() 
print(s.isEmpty()) 
s.push(4) 
s.push("dog") 
print(s.peek()) 
s.push(True) 
print(s.size()) 
print(s.isEmpty()) 
s.push(8.4) 
print(s.pop()) 
print(s.pop()) 
print(s.size())

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44179.html

线性结构队列与栈

摘要：线性结构队列与栈栈栈是一种遵循先进后出原则的有序列表，新添加或待删除的元素都保存在栈的一端，这一端被称作为栈顶，另一端被称作为栈底。将字符串的每个字符按顺序亚入栈。线性结构队列与栈栈栈(Stack)是一种遵循先进后出(LIFO)原则的有序列表，新添加或待删除的元素都保存在栈的一端，这一端被称作为栈顶，另一端被称作为栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。栈的操作 ...

Turbo 2019-07-31 11:13 评论0 收藏0
线性结构队列与栈

摘要：线性结构队列与栈栈栈是一种遵循先进后出原则的有序列表，新添加或待删除的元素都保存在栈的一端，这一端被称作为栈顶，另一端被称作为栈底。将字符串的每个字符按顺序亚入栈。线性结构队列与栈栈栈(Stack)是一种遵循先进后出(LIFO)原则的有序列表，新添加或待删除的元素都保存在栈的一端，这一端被称作为栈顶，另一端被称作为栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。栈的操作 ...

Turbo 2019-08-23 12:23 评论0 收藏0
Python全栈之路系列之列表数据类型

摘要：列表同字符串一样都是有序的，因为他们都可以通过切片和索引进行数据访问，且列表的的是可变的。列表(list)同字符串一样都是有序的，因为他们都可以通过切片和索引进行数据访问，且列表的的是可变的。创建列表的几种方法第一种 name_list = [Python, PHP, JAVA] 第二种 name_list ＝ list([Python, PHP, JAVA]) 创建一个空列表 ...

琛ｈ。 2019-07-25 11:19 评论0 收藏0
python入门

摘要：零预备知识字符编码计算机只能处理数字，所以为文本需要转化为数字才能被计算机处理，计算机里八个比特作为一个字节，这是数据的存储基础单位。零、预备知识 0.1 字符编码计算机只能处理数字，所以为文本需要转化为数字才能被计算机处理，计算机里八个比特（bit）作为一个字节(byte)，这是数据的存储基础单位。计算机为了处理文本，有以下三种编码方式： ASCII码：只有大小写英文字母，数字...

xeblog 2019-07-30 17:59 评论0 收藏0
《JavaScript快速全栈开发》作者Azat Mardanov：现在是拥抱Node技术栈的最佳时

摘要：长期以来，他都是和等机构的讲师，其技术课程获得一致好评。但是，如果让我预测的话，我认为未来是很光明的，而现在就是拥抱技术栈的最佳时机。所以在浏览器和服务器之间代码不需要上下文切换。如果没有上下文切换，那么生产力也会更高。非商业转载请注明作译者、出处，并保留本文的原始链接：http://www.ituring.com.cn/article/195742 Azat Mardan...

Rango 2019-08-21 10:28 评论0 收藏0