Queues With list and deque
00:12 The difference is that queues are FIFO: First-In/First-Out. This is like a bank line-up. First person to arrive in the morning is the first person served. Operations on a queue are commonly called enqueue and dequeue.
00:29 Like stacks, queues don’t typically support random access, or if they do, it tends to be an expensive operation, whereas the insert and delete operations on a queue are typically aimed at being O(1). Common uses for queues are scheduling and breadth-first search of a tree-like data structure.
list type in Python can be used as a queue by popping items off the front of the list. You can do this by adding an extra parameter to the call to
.pop(). The underlying structure of a
list is a dynamic array. Lists were implemented this way to optimize for random access, but the cost of this is the first spot in the list must be the first spot in memory.
01:25 This is an O(n) operation, n for everything to the right of the hole, which could be the entire list. This doesn’t mean not to use a list as a queue. The cost of O(n) isn’t too bad if n is small. Lists are good enough for small amounts of data.
If you aren’t playing with small amounts of data, a better alternative is to use the
deque object in the
collections library. The
.popleft() methods act as enqueue and dequeue respectively.
Become a Member to join the conversation.