Python数据结构—栈、队列
栈和队列的特性
-
.栈(stacks)是一种只能通过访问其一端来实现数据存储与检索的线性数据结构，具有后进先出(last in first out，LIFO)的特征
-
.队列(queue)是一种具有先进先出特征的线性数据结构，元素的增加只能在一端进行，元素的删除只能在另一端进行。能够增加元素的队列一端称为队尾，可以删除元素的队列一端则称为队首
-
.对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法，出栈使用pop()方法
另一个常用的操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek()方法则只返回栈顶元素，而不删除它
为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量top，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小
push()、pop()和peek()是栈的3个主要方法，但是栈还有其他方法和属性
stack通常的操作：
Stack() 建立一个空的栈对象
push() 把一个元素添加到栈的最顶层
pop() 删除栈最顶层的元素，并返回这个元素
peek() 返回最顶层的元素，并不删除它
isEmpty() 判断栈是否为空
size() 返回栈中元素的个数
#-*- coding:?UTF-8 -*-
__author__ = 'Administrator'
#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())
-
.队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。
队列的另外一项重要操作是读取队头的元素。这个操作叫做peek()。该操作返回队头元素，但不把它从队列中删除。除了读取队头元素，我们还想知道队列中存储了多少元素，可以使用size()满足该需求
queue通常的操作：
Queue() 定义一个空队列，无参数，返回值是空队列。
enqueue(item) 在队列尾部加入一个数据项，参数是数据项，无返回值。
dequeue() 删除队列头部的数据项，不需要参数，返回值是被删除的数据，队列本身有变化。
isEmpty() 检测队列是否为空。无参数，返回布尔值。
size() 返回队列数据项的数量。无参数，返回一个整数。
class Queue:
"""模拟队列"""
def init(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
q=Queue()
q.isEmpty()
q.enqueue('dog')
q.enqueue(4)
q=Queue()
q.isEmpty()
q.enqueue(4)
q.enqueue('dog')
q.enqueue(True)
