一 什么是队列(queue)?
只允许在头部删除、尾部插入的线性结构。先进先出(First in first out),类似生活中排队一样,先进入队列的人先走,后进入队列的人后走,且只能从队列尾部加入队列。
队列可以用数组和链表实现,分别叫顺序队列、链队列。
在顺序队列中,队头即为数组头部元素,队尾即为数组尾部元素。
二 队列的常用操作
1.入队:queue.enqueue()
2.出队:queue.dequeue()
3.判断队列是否为空:queue.is_empty()
4.查看队头元素:queue.get_head()
1 | class Queue: |
双端队列可在队列的头部和尾部都进行插入和删除。
小结:栈和队列都有数组和链表两种实现形式。
两个栈可以实现一个队列,两个队列也可以实现一个栈。