Python中队列与栈的实现

writer：lIcht                      email：lIcht.gzl@gmail.com                 Date:  2019.9.15

        队列与栈是数据结构中很基础的数据类型，在python中同样可以通过list类型的.appen、.pop、.remove等方法可以很轻松的实现队列与栈的功能。为了更好的理解这两种基础的数据类型，同样可以通过类创建新的数据类型来实现栈和队列的操作。

​x
# 《栈的操作》
# Stack()创建一个新的空栈
# push()添加一个新的元素item到栈顶
# pop()弹出栈顶元素
# peek()返回栈顶元素
# is_empty()判断栈是否为空
# size()返回栈的元素个数
​
​
class Stack(object):
    """栈"""
    def __init__(self):
        self.__list = []
​
    def push(self, item):
        """添加一个新的元素item到栈顶"""
        # 栈顶选择在列表的尾部，因为复杂度更小为1
        self.__list.append(item)
​
    def pop(self):
        """弹出栈顶元素"""
        self.__list.pop()
        return
​
    def peek(self):
        """返回栈顶元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None
​
    def is_empty(self):
        """判断栈是否为空"""
        if len(self.__list):
            return False
        else:
            return True
​
    def size(self):
        """返回栈的元素个数"""
        return len(self.__list)
​
    def see(self):
        print(self.__list)
​
​
if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(6)
    s.pop()
    s.push(4)
    print(s.size())
    s.see()
​

xxxxxxxxxx
# 《队列的操作》
# Queue()创建一个空的队列
# enqueue(item)往队列中添加一个item元素
# dequeue()从队列头部删除一个元素
# is_empty()判断一个队列是否为空
# size()返回队列的大小
​
​
class Queue(object):
    """队列"""
    def __init__(self):
        self.__list = []
​
    def enququ(self, item):
        """往队列中添加一个item元素"""
        self.__list.append(item)
​
    def dequeue(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)
​
    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []
​
    def size(self):
        """返回队列的大小"""
        return len(self.__list)
​
​
if __name__ == "__main__":
    s = Queue()
    s.enququ(1)
    s.enququ(2)
    s.enququ(3)
    s.enququ(4)
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())

xxxxxxxxxx
# 《双端队列的操作》
# 头部尾部均可存取
​
​
class Queue(object):
    """双端队列"""
    def __init__(self):
        self.__list = []
​
    def add_front(self, item):
        """往队列尾添加一个item元素"""
        self.__list.append(item)
​
    def add_rear(self, item):
        """往队列头添加一个item元素"""
        self.__list.insert(0, item)
​
    def pop_front(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)
​
    def pop_rear(self):
        """从队列尾部删除一个元素"""
        return self.__list.pop()
​
    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []
​
    def size(self):
        """返回队列的大小"""
        return len(self.__list)
​