文章目录
栈栈操作队列队列操作双端队列双端队列操作
栈
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。 由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。
栈操作
class Stack(object
):
"""栈"""
def
__init__(self
):
self
.__list
= []
def
is_empty(self
):
"""判断是否为空"""
return self
.__list
== []
def
push(self
, item
):
"""加入元素"""
#一般选择从尾部添加元素，因此这样的运算复杂度低
self
.__list
.append(item
)
def
pop(self
):
"""弹出元素"""
return self
.__list
.pop()
def
peek(self
):
"""返回栈顶元素"""
if self
.__list
:
return self
.__list
[-1]
else:
return None
def
size(self
):
"""返回栈的大小"""
return len(self
.__list
)
if __name__
== "__main__":
stack
= Stack()
stack
.push("1")
stack
.push("2")
stack
.push("3")
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开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。
队列操作
class Queue(object
):
"""队列"""
def
__init__(self
):
self
.__list
= []
def
is_empty(self
):
return self
.__list
== []
def
enqueue(self
, item
):
"""进队列"""
return self
.__list
.append(item
)
def
dequeue(self
):
"""出队列"""
return self
.__list
.pop(0)
def
size(self
):
"""返回大小"""
return len(self
.__list
)
if __name__
== "__main__":
q
= Queue()
q
.enqueue("1")
q
.enqueue("2")
q
.enqueue("3")
print(q
.size())
print(q
.dequeue())
print(q
.dequeue())
print (q
.dequeue())
双端队列
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。 双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
双端队列操作
class Deque(object
):
"""双端队列"""
def
__init__(self
):
self
.items
= []
def
is_empty(self
):
"""判断队列是否为空"""
return self
.items
== []
#因为是双端队列，使用append也可以进行添加元素，尾端作为头端
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())
