Python如何实现堆栈和队列

缺乏、安全感 2024-03-31 05:33 63阅读 0赞

**python实现堆栈**

堆栈是一个后进先出的[数据结构][Link 1]，其工作方式就像一堆汽车排队进去一个死胡同里面，最先进去的一定是最后出来。

我们可以设置一个类，用列表来存放栈中元素的信息，利用列表的append()和pop()方法可以实现栈的出栈pop和入栈push的操作，list.append(obj)意思是向列表添加一个对象obj,list.pop(index=-1)意思是删除指定位置的对象，默认是最后一个对象，也就是说list.pop(),是删除列表中下标最大的元素。可先将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

*  1
 *  2
 *  3
 *  4

再写一个程序文件，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()

**Python实现队列**

[队列][Link 2]是一种先进先出的数据类型，它的跟踪原理类似于在超市收银处排队，队列里的的第一个人首先接受服务，新的元素通过入队的方式添加到队列的末尾，而出队就是将队列的头元素删除。

我们可以设置一个类，用列表来存放栈中元素的信息，利用列表的append()和pop()方法可以实现队列的入队enqueue和出队dequeue的操作，上面栈一个元素每次出去是列表的最后一个，直接用list.pop()出栈，而出队列每次是第一个，所以要用list.pop(0)出队列

代码如下:

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+1self.size  
def isempty(self):  
return self.frontself.rear

q=Queue(10);  
for i in range(3):  
q.enqueue(i)  
print q.dequeue()  
print q.isempty()

转自：[https://www.weidianyuedu.com][https_www.weidianyuedu.com]

[Link 1]: https://so.csdn.net/so/search?q=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E9%98%9F%E5%88%97&spm=1001.2101.3001.7020
[https_www.weidianyuedu.com]: https://www.weidianyuedu.com