Stack, Queue and the Lost Pen-Drive Token
During the school’s practical examination week, the computer lab uses a Python list as a stack to keep track of the 5 borrowed pen drives issued to examiners. The stack is initially empty, and the lab follows a strict last-in-first-out rule. At 9:00 a.m., pen drives with token numbers 11, 12, 13, 14 and 15 are pushed in that order. At 9:10, an examiner asks for a pen drive, but the stack is full; the lab assistant says the only way to make room is to pop one item. At 9:15, two pops are performed, and then token 16 is pushed. Separately, a queue in the lab corridor holds students waiting for a viva: 21, 22, 23. One student is served from the front, and then student 24 joins the queue. The lab assistant wants to use the same Python list for both the pen-drive stack and the student queue to save memory.
1. Trace the final contents of the stack after the operations at 9:15 and state which token is on top. Show each step.
Read the worked answer
Start: [11, 12, 13, 14, 15] with 15 on top. First pop removes 15: [11, 12, 13, 14]. Second pop removes 14: [11, 12, 13]. Push 16 adds to the rear/top: [11, 12, 13, 16]. The top is 16.
The key is LIFO: the most recently pushed item is removed first, so 14 and 15 are removed while 11, 12 and 13 remain. The stack does not remove 11 just because it was pushed first.
2. Trace the queue after serving one student and adding student 24. Then explain why using the same list object for the stack and queue would cause incorrect behaviour in this scenario.
Read the worked answer
Queue start: [21, 22, 23]. Serving from the front removes 21: [22, 23]. Adding 24 at the rear gives [22, 23, 24]. The front is 22.
If the same list object is used, stack operations act at the end, while queue service acts at the front. After the stack pops, the list becomes [11, 12, 13]; a queue dequeue would remove 11, which is not the same as popping 13. The structures would corrupt each other's order, and stack overflow checks would be confused by queue insertions. Use separate lists, or collections.deque for the queue.
3. The assistant suggests implementing the stack with a fixed-size list of length 5 and checking `len(stack) == 5` before push. Write the condition and explain what happens if the check is omitted when pushing token 16 after only one pop.
Read the worked answer
Use if len(stack) < 5: stack.append(token) else reject with an overflow message. If the check is omitted and one pop has reduced the length to 4, pushing 16 makes 5 items, which is still within capacity. But if a second push is attempted without a check, the list grows to 6, breaking the fixed-capacity rule.
A fixed-size list does not enforce the size by itself; the program must check before every push. Checking len(stack) == 5 before push is the correct guard.