Python队列

FIFO

一、单向队列

• 使用list实现队列基本的方式:
  1. 队首head:list最后一个list[-1]元素，出队(pop)的位置，使用list.pop实现
  2. 队尾tail：list第一个list[0]元素，入队(push)的位置，使用list.insert实现

• 入列(push)

  使用list.insert()方法，在list第一个元素[0]位置插入数据项

• 出列(pop)

  使用list.pop()方法，将list最后一个元素[-1]位置弹出数据项

class Queue:
    def __init__(self):
        self.items=[]

    def push(self,item):
        self.items.insert(0,item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return self.items==[]

    def size(self):
        return len(self.items)

if __name__=="__main__":
    queue=Queue()
    queue.push('first')
    queue.push('second')
    queue.push('third')
    queue.push('forth')
    print(queue.size())
    print(queue.items)
    print(queue.pop())
    print(queue.items)
    print(queue.pop())
    print(queue.items)
    print(queue.size())

二、双向队列

双向队列，队首、队尾均可入队、出队

• 使用list实现队列基本的方式:

  1. 队首head:list的最后一个list[-1]元素
  2. 队尾tail：list的第一个list[0]元素

• 队首操作

  1. push_head:使用list.append()方法实现，在list的最后一个位置[-1]添加元素
  2. pop_head:使用list.pop()方法实现，将list最后一个位置[-1]元素弹出
• 队尾操作
  1. push_tail:使用list.insert(0)方法实现，在list[0]位置插入一个元素
  2. pop_tail:使用list.pop(0)，将list[0]元素弹出

class DoubleQueue:
    def __init__(self):
        self.items=[]

    def push_tail(self, item):
        self.items.insert(0,item)

    def pop_tail(self):
        return self.items.pop(0)

    def push_head(self,item):
        self.items.append(item)
    def pop_head(self):
        return self.items.pop()

    def is_empty(self):
        return self.items==[]

    def size(self):
        return len(self.items)

if __name__=="__main__":
    queue=DoubleQueue()
    queue.push_tail('first')
    queue.push_tail('second')
    queue.push_tail('third')
    queue.push_tail('forth')
    print(queue.size())
    print(queue.items)
    print(queue.pop_head())
    print(queue.items)
    queue.push_tail("five")
    print(queue.items)
    print(queue.pop_tail())
    print(queue.items)
    queue.push_head("zero")
    print(queue.items)
    print(queue.size())
    print(queue.is_empty())