Python数据结构与算法3——栈和队列

栈

概念

栈是一种线性的数据结构，FILO（先进后出）的操作，可以用顺序表实现，也可以用链表来实现。想象成一个杯子，只能往上面倒水进去，把水倒出去的时候，上面的先出来。

操作

栈的基本操作包含：

• stack()：创建空的栈
• push()：入栈
• pop()：出栈
• peek()：返回栈顶元素
• is_empty()：判断是否为空栈
• size()：返回栈的元素个数

代码实现

通过列表list的操作来实现栈的先进后出方式

class Stack(object):
    """Stack"""
    def __init__(self):
        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)
    
    def is_empty(self):
        # 判断是否为空
        # 空列表返回真
        return self.__list == []
        # 如果是空列表，布尔值为F，取反变成T
        # return not self.__list
    
if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

观察结果：进入的顺序是12345，出来的顺序是54321

image.png

队列

概念

队列queue也是一种线性结构，方式是先进先出FIFO， 想象成一支队伍。

• 允许插入数据的一端：队尾
• 允许删除的一端：队头
  假设队列，则是队头元素，是队尾元素。删除从开始，添加从开始

操作

几个重要的操作

• enqueue()：插入元素
• dequeue()：删除元素
• is_empty()：判断是否为空
• size()：返回元素个数

代码实现

class Queue(object):
    # Queue
    def __init__(self):
        self.__list = []
    
    def enqueue(self, item):
        # 添加元素：append默认是添加到末尾
        self.__list.append(item)
        # self.__list.append(0, item)
    
    def dequeue(self):
        # 从队列头部删除元素：pop默认是末尾
        return  self.__list.pop(0)
        # return  self.__list.pop()
    
    def is_empty(self):
        # 判断是否为空
        return self._list == []
    
    def size(self):
        # 返回个数
        return len(self.__list)
    
if __name__ == "__main__":
    q = Queue()
    
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)
    
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

image.png

双端队列

概念

能够在队头和队尾同时进行插入和删除操作的队列。操作的规则类似栈的先进后出。

代码实现

# coding: utf-8
# 双端队列

class Dueue(object):
    # Doublequeue
    # 构造函数，用来定义私有化属性
    def __init__(self):
        self.__list = []
    
    def add_front(self, item):
        # 添加元素：append默认是添加到末尾；也可以指定位置
        # 双端队列中哪里添加就在哪里删除
        self.__list.insert(0, item)
        # self.__list.append(0, item)
    
    def add_rear(self, item):
        # 从队列头部删除元素：pop默认是末尾
        self.__list.append(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)
    
if __name__ == "__main__":
    q = Dueue()
    
    # 头部插入 
    q.add_front(1)
    q.add_front(2)
    q.add_front(3)
    # 尾部删除
    q.add_rear(4)
    q.add_rear(5)
    q.add_rear(6)
    
    # 同步删除
    print(q.pop_front())
    print(q.pop_front())
    print(q.pop_front())
    # 尾部删除
    print(q.pop_rear())
    print(q.pop_rear())
    print(q.pop_rear())

image.png