Queue — NCERT Solutions

A queue and a stack are both linear data structures, but they differ in the order of operation.

• Queue follows FIFO (First In First Out): insertion happens at the rear and deletion happens at the front.
• Stack follows LIFO (Last In First Out): both insertion and deletion happen at the same end called the top.

So, in a queue the oldest element is removed first, while in a stack the newest element is removed first.

FIFO means First In First Out. In a queue, the element that enters first is the first one to leave. So the element that has been waiting the longest is removed first. That is why queue is also called First Come First Served (FCFS).

A menu-driven Python program for shuttlecock movement in a box can be written using a queue by following the same idea as the book’s queue program. Each movement can be treated as an insertion at the rear, and each removal as a deletion from the front.

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

def isEmpty(q):
    return len(q) == 0

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


def main():
    box = list()
    while True:
        print("1. Insert shuttlecock")
        print("2. Remove shuttlecock")
        print("3. View front")
        print("4. Show size")
        print("5. Exit")
        ch = int(input("Enter choice: "))

        if ch == 1:
            s = input("Enter shuttlecock code: ")
            enqueue(box, s)
        elif ch == 2:
            print("Removed:", dequeue(box))
        elif ch == 3:
            if not isEmpty(box):
                print("Front:", box[0])
            else:
                print("Queue is empty")
        elif ch == 4:
            print("Size:", len(box))
        elif ch == 5:
            break
        else:
            print("Invalid choice")

main()

This uses the queue operations from the chapter: enqueue, dequeue, isEmpty, and peek/front access.

A queue and a deque are different in their allowed operations:

• In a queue, insertion happens only at the rear and deletion only at the front.
• In a deque (double ended queue), insertion and deletion can happen from both ends — front as well as rear.

So, a deque is more flexible and can also behave like a queue or a stack.

Work step by step using FIFO:

1. enqueue(34) → [34]
2. enqueue(54) → [34, 54]
3. dequeue() removes front 34 → [54]
4. enqueue(12) → [54, 12]
5. dequeue() removes front 54 → [12]
6. enqueue(61) → [12, 61]
7. peek() shows front element, so queue remains [12, 61]
8. dequeue() removes 12 → [61]
9. dequeue() removes 61 → []
10. dequeue() on empty queue → Queue is empty
11. dequeue() again on empty queue → Queue is empty
12. enqueue(1) → [1]

So the status after each operation is as shown in the final answer.

Start with an empty deque [].

1. peek() → deque is empty, so output Queue underflow and deque stays []
2. insertFront(12) → [12]
3. insertRear(67) → [12, 67]
4. deletionFront() removes 12 → [67]
5. insertRear(43) → [67, 43]
6. deletionRear() removes 43 → [67]
7. deletionFront() removes 67 → []
8. deletionRear() on empty deque → Queue underflow

Thus the status after each operation is as given in the final answer.

def insertRear(myDeque, element):
    myDeque.append(element)

def deletionFront(myDeque):
    if len(myDeque) != 0:
        return myDeque.pop(0)
    else:
        print("Queue underflow")


def deletionRear(myDeque):
    if len(myDeque) != 0:
        return myDeque.pop()
    else:
        print("Queue underflow")

def isPalindrome(s):
    d = list()

    # insert each character in deque
    for ch in s:
        insertRear(d, ch)

    # compare front and rear characters
    while len(d) > 1:
        front = deletionFront(d)
        rear = deletionRear(d)
        if front != rear:
            return False

    return True

# main program
string = input("Enter a string: ")
if isPalindrome(string):
    print("Palindrome")
else:
    print("Not Palindrome")