Stacks and queues

The diagram shows the initial contents of a stack, with 5 at the top.

The following operations are performed in order: push(6), pop(), pop(), push(1), peek().

(a) State the values returned by the two pop() operations. [1]

(b) State the value returned by peek(). [1]

(c) Write down the final contents of the stack from bottom to top and state the number of items. [2]

A stack is used to evaluate the postfix (reverse Polish) expression 5 3 + 2 * 4 -. Operands are pushed; when an operator is read, two values are popped, the operation is applied and the result is pushed.

(a) Show the contents of the stack after the token + and after the token * has been processed. [2]

(b) State the final result. [1]

(c) When the operator - is processed, state the two values popped, in the order they are popped, and identify which of them is the left-hand operand of the subtraction. [2]

Write a Python class Stack that implements a stack of fixed maximum size using a list and an integer top. It must include:

• a constructor taking the maximum size;
• methods is_empty() and is_full();
• a method push(item) that raises an error if the stack is full;
• a method pop() that returns the top item and raises an error if the stack is empty.

[6]

A café app stores customer orders in a queue. The diagram shows the initial queue, with Ana at the front.

The following operations are performed in order:

enqueue("Dev"), dequeue(), dequeue(), enqueue("Eli"), front(), isEmpty()

(a) State the values returned by the two dequeue() operations, in order. [1]

(b) State the value returned by front(). [1]

(c) State the value returned by isEmpty(). [1]

(d) State the final contents of the queue, from front to rear. [1]

(a) Outline what is meant by the term FIFO when describing a queue. [1]

(b) For each of the following situations, identify whether a stack or a queue is the more suitable data structure and justify your choice.

(i) A web browser's Back button, which returns the user to the pages they visited, most recent first. [2]

(ii) A school's shared printer, which receives print jobs from many computers and prints them in the order they were sent. [2]

A queue of integers is implemented as a circular queue using a fixed-size list data of size 6, with variables front, rear and count. The diagram shows the empty queue.

SIZE = 6
data = [None] * SIZE
front = 0
rear = -1
count = 0

def enqueue(item):
    global rear, count
    if count == SIZE:
        print("Queue full")
    else:
        rear = (rear + 1) % SIZE
        data[rear] = item
        count = count + 1

def dequeue():
    global front, count
    item = data[front]
    data[front] = None
    front = (front + 1) % SIZE
    count = count - 1
    return item

The following calls are made: enqueue(12), enqueue(7), enqueue(30), enqueue(4), enqueue(19), then dequeue() three times, then enqueue(25), enqueue(8), enqueue(16).

(a) State the values returned by the three dequeue() calls. [1]

(b) State the contents of data (index 0 to 5) and the values of front, rear and count after all the calls. [3]

(c) Explain why a circular queue is used rather than a linear queue in which rear only ever increases. [2]

The function below uses a stack to check whether the brackets in a string are correctly matched.

def balanced(text):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in text:
        if ch in "([{":
            stack.append(ch)          # push
        elif ch in ")]}":
            if len(stack) == 0 or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

(a) Trace balanced("(()[]"), stating the contents of stack (bottom to top) after each character is processed, and the value returned. [3]

(b) The call balanced("([)]") returns False. Identify the character being processed when False is returned and explain why. [2]

A student implements a queue in Python in two ways: (A) a list, using append() to enqueue and pop(0) to dequeue; (B) a deque, using append() to enqueue and popleft() to dequeue. For each implementation, the student fills a queue with n items and then times how long it takes to dequeue all of them.

(a) Describe how the total time changes when n doubles, for each implementation. [2]

(b) Hence deduce the time complexity, in Big O notation, of a single dequeue operation for each implementation. [2]

(c) Explain why dequeuing with pop(0) on a list behaves in this way. [1]

(d) Predict the total time for implementation (A) when n = 400 000. [1]

A program uses a Queue class with methods enqueue(item), dequeue() and isEmpty(), and a Stack class with methods push(item), pop() and isEmpty(). Stack() creates an empty stack.

For example, if queue q holds 3, 9, 1, 6 (front to rear), then after reverseQueue(q) it holds 6, 1, 9, 3.

(a) Construct the function reverseQueue(q) in Python or Java that reverses the order of the items in queue q. Use only the methods listed; do not access the underlying list or array. [4]

(b) For a queue of n items, state the time complexity and the additional memory used by your function, in Big O notation, with a reason. [2]

A queue is built from two stacks, inStack and outStack. Python lists are used as stacks (append = push, pop() = pop).

class TwoStackQueue:
    def __init__(self):
        self.inStack = []
        self.outStack = []

    def enqueue(self, item):
        self.inStack.append(item)

    def dequeue(self):
        if len(self.outStack) == 0:
            while len(self.inStack) > 0:
                self.outStack.append(self.inStack.pop())
        return self.outStack.pop()

The following calls are made on a new TwoStackQueue: enqueue(4), enqueue(8), enqueue(2), dequeue(), enqueue(5), dequeue(), dequeue(), dequeue().

(a) State the values returned by the four dequeue() calls, in order. [1]

(b) State the contents of inStack and outStack (bottom to top) immediately after enqueue(5). [2]

(c) State the total number of items moved from inStack to outStack during the whole sequence. [1]

(d) A single dequeue() can be O(n). Explain why the average cost per operation over a long sequence of operations is still O(1). [2]