Computer Science Chapter 4 – Queue – Complete Notes, Q&A & Exam Preparation

A queue is an ordered linear list of elements in which the ends used for adding and removing elements are different. A queue follows First-In-First-Out (FIFO), unlike the stack’s LIFO approach.

Examples shown in the chapter include students waiting in a line, customers at a bank cash counter and vehicles waiting at a fuel pump.

In FIFO, the element that enters the queue first is the first one to leave. The element that has stayed in the queue the longest is removed first. FIFO is also known as the First Come First Served (FCFS) approach.

• REAR = end where new items are added.
• FRONT = end from which items are removed.
• REAR is also called TAIL.
• FRONT is also called HEAD.

The chapter implements a queue using Python’s list data type. A list does not have a fixed size in the manner described for a fixed-capacity queue, so the chapter does not implement IS FULL for this list-based version.

Create queue

myQueue = list()

enqueue()

def enqueue(myQueue, element):
    myQueue.append(element)

append() adds the element at the end of the list, which is the Rear.

isEmpty()

def isEmpty(myQueue):
    if len(myQueue)==0:
        return True
    else:
        return False

dequeue()

def dequeue(myQueue):
    if not (isEmpty(myQueue)):
        return myQueue.pop(0)
    else :
        print("Queue is empty")

pop(0) removes the first item, so it represents deletion at the Front.

size()

def size(myQueue):
    return len(myQueue)

peek()

def peek(myQueue):
    if isEmpty(myQueue):
        print('Queue is empty')
        return None
    else:
        return myQueue[0]

Bank cash-counter scenario – Program 4-1

myQueue = list()
# each person to be assigned a code as P1, P2, P3,...
element = input("enter person’s code to enter in queue :")
enqueue(myQueue,element)
element = input("enter person’s code for insertion in queue :")
enqueue(myQueue,element)
print("person removed from queue is:", dequeue(myQueue))
print("Number of people in the queue is :",size(myQueue))
element = input("enter person’s code to enter in queue :")
enqueue(myQueue,element)
element = input("enter person’s code to enter in queue :")
enqueue(myQueue,element)
element = input("enter person’s code to enter in queue :")
enqueue(myQueue,element)
print("Now we are going to remove remaining people from the queue")
while not isEmpty(myQueue):
    print("person removed from queue is ",
    dequeue(myQueue))

Output

enter person’s code to enter in queue :P1
enter person’s code to enter in queue :P2
person removed from the queue is :p1
number of people in the queue is :1
enter person’s code to enter in queue :P3
enter person’s code to enter in queue :P4
enter person’s code to enter in queue :P5
Now we are going to remove remaining people from the queue
person removed from the queue is :p2
person removed from the queue is :p3
person removed from the queue is :p4
person removed from the queue is :p5
Queue is empty

Deque (pronounced “deck”) permits insertion and removal from either end: head/front or tail/rear. Because both ends can be used, it can implement stack or queue behaviour. It is also called a Double ended queue.

Like the queue, the deque is implemented with the Python list data type in this chapter.

myDeque = list()

Deletion from Front: its implementation is the same as the queue’s dequeue() because the first element is removed with pop(0).

return myDeque.pop(0)

Program 4-2 – Implementation of Deque in Python

def insertFront(myDeque,element):
    myDeque.insert(0,element)
def getFront(myDeque):
    if not (isEmpty(myDeque)):
        return myDeque[0]
    else:
        print("Queue underflow")
def getRear(myDeque):
    if not (isEmpty(myDeque)):
        return myDeque[len(myDeque)-1]
    else:
        print ("Queue underflow")
def insertRear(myDeque,element):
    myDeque.append(element)
def isEmpty(myDeque):
    if len(myDeque) == 0:
        return True
    else:
        return False
def deletionRear(myDeque):
    if not isEmpty(myDeque):
        return myDeque.pop()
    else:
        print("Queue underflow")
def deletionFront(myDeque):
    if isEmpty(myDeque):
        print("Queue underflow")
    else:
        return myDeque.pop(0)
def main():
    dQu = list()
    choice = int(input('enter 1 to use as normal queue 2 otherwise : '))
    if choice == 1:
        element = input("data for insertion at rear ")
        insertRear(dQu,element)
        element = getFront(dQu)
        print("data at the beginning of queue is ", element)
        element = input("data for insertion at front ")
        insertRear(dQu,element)
        print('data removed from front of queue is ', deletionFront(dQu))
        print('data removed from front of queue is ', deletionFront(dQu))

Output

enter 1 to use as normal queue 2 otherwise : 1
data for insertion at rear 23
data at the beginning of queue is 23
data for insertion at rear 45
data removed from front of queue is 23
data removed from front of queue is 45
Queue underflow
data removed from front of queue is None
enter 1 to use as normal queue 2 otherwise : 2
data for insertion at front 34
data at the end of queue is 34
data for insertion at front 56
data removed from rear of queue is 34
data removed from rear of queue is 56
Queue underflow
data removed from rear of queue is None

Exercise topics from the chapter

1. Complete the chapter fill-in-the-blank concepts: queue definition, FIFO order, enqueue/dequeue, deletion end, the order of received elements, deque definition and the deletion sequence in a deque.
2. Compare and contrast a queue with a stack.
3. Explain how FIFO describes a queue.
4. Write a menu-driven Python program using a queue to implement movement of a shuttlecock in its box.
5. Explain how a queue data type differs from a deque data type.
6. Show the status of a queue after the given sequence of enqueue, dequeue and peek operations.
7. Show the status of a deque after the given sequence of peek, insertFront, insertRear, deletionFront and deletionRear operations.
8. Write a Python program to check whether a given string is a palindrome using a deque, referring to Algorithm 4.1.

1 Mark

1. Define queue.
2. Expand FIFO and FCFS.
3. Which end is used for insertion in a queue?
4. Which end is used for deletion?
5. What is Overflow?
6. What is Underflow?
7. Define deque.

2 Marks

1. Differentiate enqueue and dequeue.
2. Explain isEmpty and peek.
3. State the roles of Front and Rear.
4. Write the basic list methods used in the chapter for queue and deque.

3 Marks

1. Explain FIFO.
2. Explain queue applications given in the chapter.
3. Explain the four basic deque operations.
4. Explain palindrome checking using deque.

4/5 Marks

1. Write the Python functions for implementing a queue using a list.
2. Write the bank queue program and explain its output.
3. Explain Algorithm 4.1 with the figures.
4. Write the Python deque program and explain its output.
5. Compare queue and deque with respect to insertion and deletion.