- 栈:后进先出(LIFO-last in first out):最后插入的元素最先出来,通常会对栈执行以下两种操作:
向栈中添加元素,此过程被称为”进栈”(入栈或压栈);
从栈中提取出指定元素,此过程被称为”出栈”(或弹栈);
应用:浏览器前进后退功能、word撤销crtl+z功能、等等 - 队列:先进先出(FIFO-first in first out):最先插入的元素最先出来。
应用:redis中间件、排队买票、医院挂号功能、等等
栈的实现
#!/usr/bin/env python
#coding:utf8
#++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site:
@software: PyCharm
@file: 6_stack_and_queue.py
@time: 2019/11/18 上午8:36
"""
#+++++++++++++++++++++++++++++++++++#
class stack(object):
def __init__(self,arg=None):
self.arg=[]
def push(self,item):
"""入栈"""
return self.arg.append(item)
def pop(self):
"""出栈"""
return self.arg.pop()
def len(self):
"""判断长度"""
return len(self.arg)
def travel(self):
"""遍历"""
return self.arg
def is_empty(self):
"""判断是否为空"""
if self.arg:
return False
else:
return True
def peek(self):
"""返回栈顶元素"""
if self.is_empty():
return None
else:
return self.arg[-1]
# return self.__items[len(self.__items)-1]
class queue(object):
def __init__(self):
pass
if __name__ == '__main__':
s=stack()
s.push(1)
s.push(2)
s.push(3)
print('is_empty: ',s.is_empty())
print('travel: ',s.travel())
print('len: ',s.len())
s.pop()
print('pop(): ',s.travel())
print('peek: ',s.peek())
-------------------------结果------------------------------------
is_empty: False
travel: [1, 2, 3]
len: 3
pop(): [1, 2]
peek: 2
队列的实现
class Queue(object):
def __init__(self,arg=None):
self.arg = []
def enqueue(self, item):
"""
:param item: 往队列中添加一个item元素
:return: None
"""
self.arg.append(item)
def dequeue(self):
"""
从队列头部删除一个元素
:return: 队列头元素
"""
return self.arg.pop(0)
def is_empty(self):
"""
判断一个队列是否为空
:return: True or False
"""
return self.arg == []
def size(self):
return len(self.arg)
def travel(self):
"""遍历"""
# print(self.arg)
return self.arg
if __name__ == '__main__':
q = Queue()
print('is_empty: ',q.is_empty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
print('enqueue_is_empty: ',q.is_empty())
print('size: ',q.size())
print('travel: ',q.travel())
q.dequeue()
print('dequeue_travel: ',q.travel())
-------------------------结果------------------------------------
is_empty: True
enqueue_is_empty: False
size: 4
travel: [1, 2, 3, 4]
dequeue_travel: [2, 3, 4]
双端队列
'''
Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小
'''
class Deque(object):
"""双端队列"""
def __init__(self):
self.arg = []
def is_empty(self):
"""
判断双端队列是否为空
:return:True or False
"""
return self.arg == []
def size(self):
return len(self.arg)
def add_front(self, item):
"""从队头加入一个item元素"""
self.arg.insert(0, item)
def add_rear(self, item):
"""从队尾加入一个item元素"""
self.arg.append(item)
def remove_front(self):
"""从队头删除一个item元素"""
return self.arg.pop(0)
def remove_rear(self):
"""从队尾删除一个item元素"""
return self.arg.pop()
def travel(self):
"""遍历"""
# print(self.arg)
# for item in self.arg:
# print(item)
return self.arg
if __name__ == '__main__':
d = Deque()
print('is_empty',d.is_empty())
d.add_front(1)
d.add_rear(2)
d.add_rear(3)
print('add_travel: ',d.travel())
d.remove_front()
print('remove_front_travel: ', d.travel())
d.remove_rear()
print('remove_rear_travel: ', d.travel())
print('size: ',d.size())
-------------------------结果------------------------------------
is_empty True
add_travel: [1, 2, 3]
remove_front_travel: [2, 3]
remove_rear_travel: [2]
size: 1
#!/usr/bin/env python
#coding:utf8
#++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site:
@software: PyCharm
@file: 6_stack_and_queue.py
@time: 2019/11/18 上午8:36
"""
#+++++++++++++++++++++++++++++++++++#
class stack(object):
def __init__(self,arg=None):
self.arg=[]
def push(self,item):
"""入栈"""
return self.arg.append(item)
def pop(self):
"""出栈"""
return self.arg.pop()
def len(self):
"""判断长度"""
return len(self.arg)
def travel(self):
"""遍历"""
return self.arg
def is_empty(self):
"""判断是否为空"""
if self.arg:
return False
else:
return True
def peek(self):
"""返回栈顶元素"""
if self.is_empty():
return None
else:
return self.arg[-1]
# return self.__items[len(self.__items)-1]
class queue(object):
def __init__(self):
pass
if __name__ == '__main__':
s=stack()
s.push(1)
s.push(2)
s.push(3)
print('is_empty: ',s.is_empty())
print('travel: ',s.travel())
print('len: ',s.len())
s.pop()
print('pop(): ',s.travel())
print('peek: ',s.peek())
-------------------------结果------------------------------------
is_empty: False
travel: [1, 2, 3]
len: 3
pop(): [1, 2]
peek: 2
class Queue(object):
def __init__(self,arg=None):
self.arg = []
def enqueue(self, item):
"""
:param item: 往队列中添加一个item元素
:return: None
"""
self.arg.append(item)
def dequeue(self):
"""
从队列头部删除一个元素
:return: 队列头元素
"""
return self.arg.pop(0)
def is_empty(self):
"""
判断一个队列是否为空
:return: True or False
"""
return self.arg == []
def size(self):
return len(self.arg)
def travel(self):
"""遍历"""
# print(self.arg)
return self.arg
if __name__ == '__main__':
q = Queue()
print('is_empty: ',q.is_empty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
print('enqueue_is_empty: ',q.is_empty())
print('size: ',q.size())
print('travel: ',q.travel())
q.dequeue()
print('dequeue_travel: ',q.travel())
-------------------------结果------------------------------------
is_empty: True
enqueue_is_empty: False
size: 4
travel: [1, 2, 3, 4]
dequeue_travel: [2, 3, 4]
双端队列
'''
Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小
'''
class Deque(object):
"""双端队列"""
def __init__(self):
self.arg = []
def is_empty(self):
"""
判断双端队列是否为空
:return:True or False
"""
return self.arg == []
def size(self):
return len(self.arg)
def add_front(self, item):
"""从队头加入一个item元素"""
self.arg.insert(0, item)
def add_rear(self, item):
"""从队尾加入一个item元素"""
self.arg.append(item)
def remove_front(self):
"""从队头删除一个item元素"""
return self.arg.pop(0)
def remove_rear(self):
"""从队尾删除一个item元素"""
return self.arg.pop()
def travel(self):
"""遍历"""
# print(self.arg)
# for item in self.arg:
# print(item)
return self.arg
if __name__ == '__main__':
d = Deque()
print('is_empty',d.is_empty())
d.add_front(1)
d.add_rear(2)
d.add_rear(3)
print('add_travel: ',d.travel())
d.remove_front()
print('remove_front_travel: ', d.travel())
d.remove_rear()
print('remove_rear_travel: ', d.travel())
print('size: ',d.size())
-------------------------结果------------------------------------
is_empty True
add_travel: [1, 2, 3]
remove_front_travel: [2, 3]
remove_rear_travel: [2]
size: 1
'''
Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小
'''
class Deque(object):
"""双端队列"""
def __init__(self):
self.arg = []
def is_empty(self):
"""
判断双端队列是否为空
:return:True or False
"""
return self.arg == []
def size(self):
return len(self.arg)
def add_front(self, item):
"""从队头加入一个item元素"""
self.arg.insert(0, item)
def add_rear(self, item):
"""从队尾加入一个item元素"""
self.arg.append(item)
def remove_front(self):
"""从队头删除一个item元素"""
return self.arg.pop(0)
def remove_rear(self):
"""从队尾删除一个item元素"""
return self.arg.pop()
def travel(self):
"""遍历"""
# print(self.arg)
# for item in self.arg:
# print(item)
return self.arg
if __name__ == '__main__':
d = Deque()
print('is_empty',d.is_empty())
d.add_front(1)
d.add_rear(2)
d.add_rear(3)
print('add_travel: ',d.travel())
d.remove_front()
print('remove_front_travel: ', d.travel())
d.remove_rear()
print('remove_rear_travel: ', d.travel())
print('size: ',d.size())
-------------------------结果------------------------------------
is_empty True
add_travel: [1, 2, 3]
remove_front_travel: [2, 3]
remove_rear_travel: [2]
size: 1