栈:
名称的由来:这个名字来源于自动售货机中用弹簧顶住的一堆盘子的隐喻。
概念:这里提到的栈是一种抽象的数据结构
,而非空间内存分配处涉及的空间存储的概念。但是大同小异,原理还是来自于对栈空间的理解。这里的栈是有一系列对象组成的一个集合,这些对象的插入和删除操作遵循后进先出(LIFO)原则。用户可以在任意时刻向栈中插入一个对象,但只能取得或者删除最后一个插入的对象(即所谓的栈顶)。
目的:通过列表实现栈
有些同学可能认为,是不是还有其他操作没有完成,为什么不能在中间插入或者其他操作,因为栈不具备这些功能,所以实现的都是栈的常规功能。
利用栈实现数据的逆置
由于LIFO协议的限制,栈可以用作一种通用的工具,用于实现一个数据序列的逆置,这一思想可以用于很多方面,例如以降序
的方式显示一个数据集,我们可以通过先逐行读取数据,然后压如一个栈中,在按照从栈中弹出的顺序来写入。这个方法的实现过程如下:
5.1.1. 把列表当作堆栈使用列表方法使得列表可以很方便的做为一个堆栈来使用,堆栈作为特定的数据结构,最先进入的元素最后一个被释放(后进先出)。用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如:
>>>stack = [3, 4, 5]
>>>stack.append(6)
>>>stack.append(7)
>>>stack
[3, 4, 5, 6, 7]
>>>stack.pop()
7
>>>stack
[3, 4, 5, 6]
>>>stack.pop()
6
>>>stack.pop()
5
>>>stack
[3, 4]
python实现堆栈与队列的方法本文实例讲述了python实现堆栈与队列的方法。分享给大家供大家参考。具体分析如下:
1、python实现堆栈,可先将Stack类写入文件stack.py,在其它程序文件中使用from stack import Stack,然后就可以使用堆栈了。
stack.py的程序:
代码如下:class Stack():
def __init__(self,size):
self.size=size
self.stack=[]
self.top=-1
def push(self,ele): #入栈之前检查栈是否已满
if self.isfull():
raise exception("out of range")
else:
self.stack.append(ele)
self.top=self.top+1
def pop(self): # 出栈之前检查栈是否为空
if self.isempty():
raise exception("stack is empty")
else:
self.top=self.top-1
return self.stack.pop()
def isfull(self):
return self.top+1==self.size
def isempty(self):
return self.top==-1
再写一个程序文件,stacktest.py,使用栈,内容如下:
代码如下:#!/usr/bin/python
from stack import Stack
s=Stack(20)
for i in range(3):
s.push(i)
s.pop()
print s.isempty()
2、python 实现队列:
复制代码代码如下:class Queue():
def __init__(self,size):
self.size=size
self.front=-1
self.rear=-1
self.queue=[]
def enqueue(self,ele): #入队操作
if self.isfull():
raise exception("queue is full")
else:
self.queue.append(ele)
self.rear=self.rear+1
def dequeue(self): #出队操作
if self.isempty():
raise exception("queue is empty")
else:
self.front=self.front+1
return self.queue[self.front]
def isfull(self):
return self.rear-self.front+1==self.size
def isempty(self):
return self.front==self.rear
q=Queue(10)
for i in range(3):
q.enqueue(i)
print q.dequeue()
print q.isempty()
希望本文所述对大家的Python程序设计有所帮助。