一、栈结构和实现:
1. 栈:
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。
2. 栈的操作:
Stack() 创建一个新的空栈push(item) 添加一个新的元素item到栈顶pop() 弹出栈顶元素peek() 返回栈顶元素is_empty() 判断栈是否为空size() 返回栈的元素个数
class Stack(object):
"""栈"""
def __init__(self
):
self
.items
= []
def is_empty(self
):
"""判断是否为空"""
return self
.items
== []
def push(self
, item
):
"""加入元素"""
self
.items
.append
(item
)
def pop(self
):
"""弹出元素"""
return self
.items
.pop
()
def peek(self
):
"""返回栈顶元素"""
return self
.items
[len(self
.items
)-1]
def size(self
):
"""返回栈的大小"""
return len(self
.items
)
if __name__
== "__main__":
stack
= Stack
()
stack
.push
("hello")
stack
.push
("world")
stack
.push
("itcast")
print stack
.size
()
print stack
.peek
()
print stack
.pop
()
print stack
.pop
()
print stack
.pop
()
二、对列:
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。
1. 队列的实现:
1.1 操作:
Queue() 创建一个空的队列enqueue(item) 往队列中添加一个item元素dequeue() 从队列头部删除一个元素is_empty() 判断一个队列是否为空size() 返回队列的大小
class Queue(object):
"""队列"""
def __init__(self
):
self
.items
= []
def is_empty(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
)
if __name__
== "__main__":
q
= Queue
()
q
.enqueue
("hello")
q
.enqueue
("world")
q
.enqueue
("itcast")
print q
.size
()
print q
.dequeue
()
print q
.dequeue
()
print q
.dequeue
()
2. 双端队列:
2.1 双端队列的结构
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除 操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
2.2 操作:
Deque() 创建一个空的双端队列add_front(item) 从队头加入一个item元素add_rear(item) 从队尾加入一个item元素remove_front() 从队头删除一个item元素remove_rear() 从队尾删除一个item元素is_empty() 判断双端队列是否为空size() 返回队列的大小
2.3 实现
class Deque(object):
"""双端队列"""
def __init__(self
):
self
.items
= []
def is_empty(self
):
"""判断队列是否为空"""
return self
.items
== []
def add_front(self
, item
):
"""在队头添加元素"""
self
.items
.insert
(0,item
)
def add_rear(self
, item
):
"""在队尾添加元素"""
self
.items
.append
(item
)
def remove_front(self
):
"""从队头删除元素"""
return self
.items
.pop
(0)
def remove_rear(self
):
"""从队尾删除元素"""
return self
.items
.pop
()
def size(self
):
"""返回队列大小"""
return len(self
.items
)
if __name__
== "__main__":
deque
= Deque
()
deque
.add_front
(1)
deque
.add_front
(2)
deque
.add_rear
(3)
deque
.add_rear
(4)
print deque
.size
()
print deque
.remove_front
()
print deque
.remove_front
()
print deque
.remove_rear
()
print deque
.remove_rear
()
