Queue

Answer: Queue

Explanation: A Queue is a linear data structure in which insertion takes place at one end (called the Rear) and deletion takes place at the other end (called the Front). Because insertion and deletion happen at different ends, it follows the FIFO (First In First Out) principle.

Answer: FIFO (First In First Out)

Explanation: In a queue, the element that is inserted first is the one that gets deleted first. This ordering is called FIFO — First In, First Out. For example, if A, B, C are inserted in that order, A will be the first one to be deleted.

Answer: Insertion operation → enqueue; Deletion operation → dequeue

Explanation:
- enqueue: adds a new element at the Rear end of the queue.
- dequeue: removes an element from the Front end of the queue.

Answer: Front

Explanation: In a queue, following the FIFO strategy, deletion (dequeue operation) always happens from the Front end, while insertion (enqueue) happens at the Rear end.

Answer: A, S, D, F

Explanation: A queue follows FIFO order. The elements are present as:
$$\text{Front} \rightarrow A, S, D, F \leftarrow \text{Rear}$$
When deleted one at a time from the Front, the sequence received is: A → S → D → F.

Answer: Deque (Double-Ended Queue)

Explanation: A Deque (Double-Ended Queue) allows insertion and deletion at both the Front and the Rear ends. However, no insertion or deletion is allowed in the middle. It is a generalised version of both stack and queue.

Answer: deletionFront, deletionRear, deletionRear, deletionRear, deletionFront

Explanation:

Initial deque (Front → Rear): $z, x, c, v, b$

| Step | Operation | Element Removed | Deque Status |
|------|-----------|----------------|--------------|
| 1 | deletionFront() | z | x, c, v, b |
| 2 | deletionRear() | b | x, c, v |
| 3 | deletionRear() | v | x, c |
| 4 | deletionRear() | x | c |
| 5 | deletionFront() | c | (empty) |

Sequence of operations: deletionFront, deletionRear, deletionRear, deletionRear, deletionFront

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):

| Feature | Stack | Queue |
|---------|-------|-------|
| Principle | LIFO (Last In First Out) | FIFO (First In First Out) |
| Insertion end | Top | Rear |
| Deletion end | Top (same as insertion) | Front (opposite to insertion) |
| Insertion operation | push() | enqueue() |
| Deletion operation | pop() | dequeue() |
| Pointers used | One pointer: Top | Two pointers: Front and Rear |
| Example | Undo operation in editor | Printer job scheduling |
| Python implementation | `append()` to insert, `pop()` to delete | `append()` to insert, `pop(0)` to delete |

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:

```python
# 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:

| Feature | Queue | Deque (Double-Ended Queue) |
|---------|-------|----------------------------|
| Full form | Queue | Double-Ended Queue |
| Insertion | Only at Rear end | At both Front and Rear ends |
| Deletion | Only at Front end | At both Front and Rear ends |
| Principle | Strictly FIFO | Can behave as FIFO or LIFO |
| Flexibility | Less flexible | More flexible |
| Operations | enqueue, dequeue, peek, isEmpty | insertFront, insertRear, deletionFront, deletionRear, getFront, getRear, isEmpty |
| Stack simulation | Cannot simulate a stack | Can simulate both stack and queue |
| Example use | Printer job queue, CPU scheduling | Browser history (back and forward), Undo-Redo operations |

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()`.

| Step | Operation | Action | Queue Status (Front → Rear) |
|------|-----------|--------|-----------------------------|
| 0 | — | Initial state | $[\;]$ (Empty) |
| 1 | enqueue(34) | Insert 34 at Rear | $[34]$ |
| 2 | enqueue(54) | Insert 54 at Rear | $[34, 54]$ |
| 3 | dequeue() | Remove 34 from Front | $[54]$ |
| 4 | enqueue(12) | Insert 12 at Rear | $[54, 12]$ |
| 5 | dequeue() | Remove 54 from Front | $[12]$ |
| 6 | enqueue() | Invalid — no element given; Queue unchanged | $[12]$ |
| 7 | dequeue() | Remove 12 from Front | $[\;]$ (Empty) |
| 8 | dequeue() | Queue is empty — Underflow / Queue Empty message | $[\;]$ (Empty) |
| 9 | enqueue(1) | Insert 1 at Rear | $[1]$ |

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.

| Step | Operation | Action | Deque Status (Front → Rear) |
|------|-----------|--------|-----------------------------|
| 0 | — | Initial state | $[\;]$ (Empty) |
| 1 | peek() | Deque is empty — returns None / prints "Deque is empty" | $[\;]$ (Empty) |
| 2 | insertFront(12) | Insert 12 at Front | $[12]$ |
| 3 | insertRear(67) | Insert 67 at Rear | $[12, 67]$ |
| 4 | deletionFront() | Remove 12 from Front → returns 12 | $[67]$ |
| 5 | insertRear(43) | Insert 43 at Rear | $[67, 43]$ |
| 6 | deletionRear() | Remove 43 from Rear → returns 43 | $[67]$ |
| 7 | deletionFront() | Remove 67 from Front → returns 67 | $[\;]$ (Empty) |
| 8 | deletionRear() | Deque is empty — Underflow / prints "Queue underflow" | $[\;]$ (Empty) |

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:

```python
# 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':

| Step | Deque | Front Char | Rear Char | Equal? |
|------|-------|-----------|----------|--------|
| Initial | [m, a, d, a, m] | — | — | — |
| 1 | [a, d, a] | m | m | Yes |
| 2 | [d] | a | a | Yes |
| 3 | [d] | size=1, loop ends | — | — |

Result: Palindrome ✓