Ctrl+K

Queue

Queue#

A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear”, and the removal of existing items occurs at the other end, commonly called the “front”. As an element enters the queue it starts at the rear and makes its way toward the front, waiting it is the next element to be removed.

The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called FIFO(first-in, first-out). It is also known as “first-come first-served.”

flowchart BT; subgraph id3 [ ] direction LR c1(Remove from front) end subgraph id2 [Queue] direction LR b1(3.14) b2(True) b3(dog) b4(20) end subgraph id1 [ ] direction LR a1(Add to rear) end a1-->b1 c1-->b4 style id1 fill:#FFFFFF, stroke-width:0px style id3 fill:#FFFFFF, stroke-width:0px

Examples

  • Cine for getting a movie ticket.

  • Check-out line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack).

  • Operating systems use a number of different queues to control processes within a computer. The scheduling of what gets done next is typically based on a queuing algorithm that tries to execute programs as quickly as possible and serve as many users as it can.

Queue Abstract Data Type#

The queue abstract data type is defined by the following structure and operations. A queue is structured, as described above, as an ordered collection of items which are added at one end, called the “rear”, and removed from the other end, called the “front”. Queues maintain a FIFO ordering property.

Queue Operations#

  • Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.

  • enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.

  • dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.

  • is_empty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.

  • size() returns the number of items in the queue. It needs no parameters and returns an integer.

q = Queue() creates a queue that starts out empty, table below shows the results of a sequence of queue operations.

Queue Operation

Queue Contents

Return Value

q.is_empty()

[]

True

q.enqueue(4)

[4]

q.enqueue('dog')

['dog',4]

q.enqueue('True')

[True,'dog',4]

q.size()

[True,'dog',4]

3

q.is_empty()

[True,'dog',4]

False

q.enqueue(8.4)

[8.4,True,'dog',4]

q.dequeue()

[8.4,True],'dog']

4

q.dequeue()

[8.4,True]

'dog'

q.size()

[8.4,True]

2

Implementing a Queue in Python#

An abstract data type (ADT) when given a physical implementation then we refer to the implementation as a data structure.

In any object-oriented programming language, the implementation of choice for an abstract data type such as a Queue is the creation of a new class. The queue operations are implemented as methods. Further, to implement a queue, which is a collection of elements, it makes sense to utilize the primitive collections provided.

Python provides List an ordered collection mechanism and a set of methods, rear is at position 0 in the list. This allows us to use the insert function on lists to add new elements to the rear of the queue. The pop operation can be used to remove the front element (the last element of the list). Recall that this also means that enqueue will be O(n) and dequeue will be O(1).

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

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

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

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

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

# Create a new queue
q = Queue()

# Check if the queue is empty
print(q.is_empty())

# Enqueue 4 at rear of queue
q.enqueue(4)

# Enqueue "dog" at rear of queue
q.enqueue('dog')

# Enqueue "True" at rear of queue
q.enqueue(True)

# Give the size of the queue
print(q.size())

# Check if the queue is empty
print(q.is_empty())

# Enqueue 8.4 at rear of queue
q.enqueue(8.4)

# Dequeue the rear element from the queue and return it
print(q.dequeue())

# Dequeue the rear element from the queue and return it
print(q.dequeue())

# Give the size of the queue
print(q.size())

True
3
False
4
dog
2

Practical usage in python#

collections.deque module provide an implementation of the queue data structure, you can find more information about the interface and api from list docs.

Practice Problem#

Write a function hot_potato(names, num) that simulates the game of Hot Potato.#

def hot_potato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())

        simqueue.dequeue()

    return simqueue.dequeue()

print(hot_potato(["Bill","David","Susan","Jane","Kent","Brad"], 10))

Jane

Simulation: Printing Tasks#

On any average day about 10 students are working in the lab at any given hour. These students typically print up to twice during that time, and the length of these tasks ranges from 1 to 20 pages. The printer in the lab is older, capable of processing 10 pages per minute of draft quality. The printer could be switched to give better quality, but then it would produce only five pages per minute. The slower printing speed could make students wait too long. What page rate should be used?

Contents