6.栈与队列操作

• 栈：后进先出（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