Queue — NCERT Solutions

Given: Two linear data structures — Stack and Queue.

Comparison (Similarities):

• Both are linear data structures.
• Both are ordered collections of elements.
• Both support insertion and deletion operations.
• Both can be implemented using Python lists.

Contrast (Differences):

Conclusion: Both are useful data structures but differ in the order in which elements are accessed. Stack works on LIFO while Queue works on FIFO principle.

FIFO stands for First In, First Out.

FIFO describes the fundamental behaviour of a queue:

• The element that is inserted first (at the Rear) is the element that is deleted first (from the Front).
• In other words, elements leave the queue in the same order in which they entered.

Real-life analogy: Consider a queue of people waiting at a ticket counter. The person who joins the queue first gets the ticket first and leaves first. No one can jump the queue from the middle.

Example:

Suppose we perform the following operations:
$$\text{enqueue}(10) \rightarrow \text{enqueue}(20) \rightarrow \text{enqueue}(30)$$

Queue status: $\text{Front} \rightarrow 10, 20, 30 \leftarrow \text{Rear}$

Now performing dequeue operations:

• dequeue() → returns 10 (first inserted, first removed)
• dequeue() → returns 20
• dequeue() → returns 30

This confirms the FIFO property: the order of deletion is the same as the order of insertion.

Concept: A box of shuttlecocks behaves like a queue — the first shuttlecock placed in the box (at the bottom) is the first one taken out (from the top/front). This is a FIFO structure.

Python Program:

# Queue implementation for shuttlecock box

def enqueue(myQueue, element):
    """Insert shuttlecock into the box (at Rear)"""
    myQueue.append(element)
    print(f"Shuttlecock '{element}' added to the box.")

def dequeue(myQueue):
    """Remove shuttlecock from the box (from Front)"""
    if not isEmpty(myQueue):
        removed = myQueue.pop(0)
        print(f"Shuttlecock '{removed}' taken out from the box.")
        return removed
    else:
        print("Box is empty! No shuttlecock to remove.")
        return None

def isEmpty(myQueue):
    """Check if box is empty"""
    return len(myQueue) == 0

def peek(myQueue):
    """View the shuttlecock at the front without removing"""
    if isEmpty(myQueue):
        print("Box is empty!")
        return None
    else:
        print(f"Shuttlecock at the front of box: '{myQueue[0]}'")
        return myQueue[0]

def size(myQueue):
    """Display number of shuttlecocks in box"""
    print(f"Number of shuttlecocks in box: {len(myQueue)}")
    return len(myQueue)

def displayBox(myQueue):
    """Display all shuttlecocks in the box"""
    if isEmpty(myQueue):
        print("Box is empty!")
    else:
        print("Shuttlecocks in box (Front to Rear):", myQueue)

# Main menu-driven program
def main():
    shuttlecockBox = list()
    while True:
        print("\n===== SHUTTLECOCK BOX MENU =====")
        print("1. Add shuttlecock to box (enqueue)")
        print("2. Take shuttlecock from box (dequeue)")
        print("3. View front shuttlecock (peek)")
        print("4. Check if box is empty")
        print("5. Count shuttlecocks in box")
        print("6. Display all shuttlecocks")
        print("7. Exit")

        choice = int(input("Enter your choice (1-7): "))

        if choice == 1:
            name = input("Enter shuttlecock name/number to add: ")
            enqueue(shuttlecockBox, name)
        elif choice == 2:
            dequeue(shuttlecockBox)
        elif choice == 3:
            peek(shuttlecockBox)
        elif choice == 4:
            if isEmpty(shuttlecockBox):
                print("Box is EMPTY.")
            else:
                print("Box is NOT empty.")
        elif choice == 5:
            size(shuttlecockBox)
        elif choice == 6:
            displayBox(shuttlecockBox)
        elif choice == 7:
            print("Exiting program.")
            break
        else:
            print("Invalid choice! Please enter between 1 and 7.")

main()

Sample Output:

===== SHUTTLECOCK BOX MENU =====
1. Add shuttlecock to box (enqueue)
...
Enter your choice: 1
Enter shuttlecock name/number to add: SC1
Shuttlecock 'SC1' added to the box.

Enter your choice: 1
Enter shuttlecock name/number to add: SC2
Shuttlecock 'SC2' added to the box.

Enter your choice: 2
Shuttlecock 'SC1' taken out from the box.

Explanation: The shuttlecock added first (SC1) is taken out first, demonstrating FIFO behaviour of a queue.

Queue vs Deque — Differences:

Key Point: A queue is a restricted version of deque. In a queue, insertion is only at Rear and deletion only at Front. A deque generalises this by allowing both operations at both ends, making it more versatile.

Note: The operation enqueue() without an argument (6th operation) is assumed to be invalid/ignored, or it may be a misprint. We will mark it as an error and continue.

Initial Queue: Empty $[]$

Concept: Queue follows FIFO. Insertion at Rear using enqueue(), deletion from Front using dequeue().

Final Queue Status: $[1]$ with Front → 1 ← Rear

Initial Deque: Empty $[]$

Concept: A Deque (Double-Ended Queue) allows insertion and deletion at both Front and Rear ends.

Final Deque Status: Empty $[]$

Concept: A string is a palindrome if it reads the same forwards and backwards (e.g., 'madam', 'racecar', 'level').

Algorithm using Deque:

1. Insert all characters of the string into a deque.
2. Repeatedly remove one character from the Front and one from the Rear.
3. Compare the two characters.
4. If they are equal for all pairs, the string is a palindrome.
5. If any pair is unequal, it is not a palindrome.

Python Program:

# Palindrome check using Deque

def insertRear(myDeque, element):
    """Insert element at Rear of deque"""
    myDeque.append(element)

def deletionFront(myDeque):
    """Delete element from Front of deque"""
    if not isEmpty(myDeque):
        return myDeque.pop(0)
    else:
        print("Deque underflow")
        return None

def deletionRear(myDeque):
    """Delete element from Rear of deque"""
    if not isEmpty(myDeque):
        return myDeque.pop()
    else:
        print("Deque underflow")
        return None

def isEmpty(myDeque):
    """Check if deque is empty"""
    return len(myDeque) == 0

def size(myDeque):
    """Return size of deque"""
    return len(myDeque)

def isPalindrome(inputString):
    """Check if inputString is palindrome using deque"""
    myDeque = list()

    # Step 1: Insert all characters into deque
    for char in inputString:
        insertRear(myDeque, char)

    # Step 2: Compare front and rear characters
    isPalin = True
    while size(myDeque) > 1:
        frontChar = deletionFront(myDeque)   # remove from front
        rearChar  = deletionRear(myDeque)    # remove from rear
        if frontChar != rearChar:
            isPalin = False
            break

    return isPalin

# Main program
def main():
    inputStr = input("Enter a string to check for palindrome: ")
    # Convert to lowercase for case-insensitive comparison
    inputStr = inputStr.lower()

    if isPalindrome(inputStr):
        print(f"'{inputStr}' is a PALINDROME.")
    else:
        print(f"'{inputStr}' is NOT a palindrome.")

main()

Sample Output 1:

Enter a string to check for palindrome: madam
'madam' is a PALINDROME.

Sample Output 2:

Enter a string to check for palindrome: hello
'hello' is NOT a palindrome.

Sample Output 3:

Enter a string to check for palindrome: racecar
'racecar' is a PALINDROME.

Dry Run for 'madam':

Result: Palindrome ✓