Stacks and Queues

Prev: Linked Lists Next: Binary Trees

Problems

9.1

Design a stack that includes a max operation, in addition to push and pop. The max method should return the maximum value stored in the stack.

Hint: Use additional storage to track the maximum value.

---

9.2

A string is said to be an arithmetical expression in Reverse Polish notation (RPN) if:

1. It is a single digit or a sequence of digits, prefixed with an optional -, e.g., "6", "123", "-42".
2. It is of the form "A,B,o" where $A$ and $B$ are RPN expressions and $o$ is one of $+,-,\times ,/$.

For example, the following strings satisfy these rules: "1729", "3,4,+,2,\times,1,+", "1,1,+,-2,\times", "-641,6,/,28,/".

An RPN expression can be evaluated uniquely to an integer, which is determined recursively. The base case corresponds to Rule (1), which is an integer expressed in the base-10 positional system. Rule (2) corresponds to the recursive case, and the RPNs are evaluated in the natural way, e.g., if $A$ evaluates to 2 and $B$ evaluates to 3, then "A,B,\times" evaluates to 6.

Write a program that takes an arithmetical expression in RPN and returns the number that the expression evaluates to.

Hint: Process subexpressions, keeping values in a stack. How should operators be handled?

Variant: Solve the same problem for expressions in Polish notation, i.e., when $A,B,o$ is replaced by $o,A,B$ in Rule (2).

---

9.3

A string over the characters {, }, (, ), [, ] is said to be well-formed if the different types of brackets match in the correct order. For example, "([]){()}" is well-formed, as is "[()[]{()()}]". However, "{)" and "[()[]{()()" are not well-formed.

Write a program that tests if a string made up of the characters (, ), [, ], {, and } is well-formed.

Hint: Which left parenthesis does a right parenthesis match with?

---

9.4

A file or directory can be specified via a string called the pathname. This string may specify an absolute path, starting from the root, e.g., /usr/bin/gcc, or a path relative to the current working directory, e.g., scripts/awkscripts.

The same directory may be specified by multiple directory paths. For example, /usr/lib/../bin/gcc and scripts/../../scripts/awkscripts/././ specify equivalent absolute and relative pathnames.

Write a program which takes a pathname, and returns the shortest equivalent pathname. Assume individual directories and files have names that use only alphanumeric characters. Subdirectory names may be combined using forward slashes (/), the current directory (.), and parent directory (..).

Hint: Trace the cases. How should . and .. be handled? Watch for invalid paths.

---

9.5

A postings list is a singly linked list with an additional jump field at each node. The jump field points to any other node. One way to enumerate the nodes in a postings list is to iteratively follow the next field. Another is to always first follow the jump field if it leads to a node that has not been explored previously, and then search from the next node. Call the order in which these nodes are traversed the jump-first order.

Write recursive and iterative routines that take a postings list, and compute the jump-first order. Assume each node has an integer-valued field that holds the order, and is initialized to -1.

Hint: Recursion makes the problem trivial. Mimic the recursion with a stack.

---

9.6

You are given a series of buildings that have windows facing west. The buildings are in a straight line, and any building which is to the east of a building of equal or greater height cannot view the sunset.

Design an algorithm that processes buildings in east-to-west order and returns the set of buildings which view the sunset. Each building is specified by its height.

Hint: When does a building not have a sunset view?

Variant: Solve the problem subject to the same constraints when buildings are presented in west-to-east order.

---

9.7

Binary trees are formally defined in Chapter 10. In particular, each node in a binary tree has a depth, which is its distance from the root.

Given a binary tree, return an array consisting of the keys at the same level. Keys should appear in the order of the corresponding nodes’ depths, breaking ties from left to right. For example, for the binary tree in Figure 10.1 on Page 148, the result should be $⟨⟨314⟩,⟨6,6⟩,⟨271,561,2,271⟩,⟨28,0,3,1,28⟩,⟨17,401,257⟩,⟨641⟩⟩$.

Hint: First think about solving this problem with a pair of queues.

Variant: Write a program which takes as input a binary tree and returns the keys in top down, alternating left-to-right and right-to-left order, starting from left-to-right. For example, if the input is the tree in Figure 10.1 on Page 148, your program should return $⟨⟨314⟩,⟨6,6⟩,⟨271,561,2,271⟩,⟨28,1,3,0,28⟩,⟨17,401,257⟩,⟨641⟩⟩$.

Variant: Write a program which takes as input a binary tree and returns the keys in a bottom up, left-to-right order. For example, if the input is the tree in Figure 10.1 on Page 148, your program should return $⟨⟨641⟩,⟨17,401,257⟩,⟨28,0,3,1,28⟩,⟨271,561,2,271⟩,⟨6,6⟩,⟨314⟩⟩$.

Variant: Write a program which takes as input a binary tree with integer keys, and returns the average of the keys at each level. For example, if the input is the tree in Figure 10.1 on Page 148, your program should return $⟨314,6,276.25,12,225,641⟩$.

---

9.8

A queue can be implemented using an array and two additional fields, the beginning and the end indices. This structure is sometimes referred to as a circular queue. Both enqueue and dequeue have $O(1)$ time complexity. If the array is fixed, there is a maximum number of entries that can be stored. If the array is dynamically resized, the total time for $m$ combined enqueue and dequeue operations is $O(m)$.

Implement a queue API using an array for storing elements. Your API should include a constructor function, which takes as argument the initial capacity of the queue, enqueue and dequeue functions, and a function which returns the number of elements stored. Implement dynamic resizing to support storing an arbitrarily large number of elements.

Hint: Track the head and tail. How can you differentiate a full queue from an empty one?

---

9.9

Queue insertion and deletion follows first-in, first-out semantics; stack insertion and deletion is last-in, first-out.

How would you implement a queue given a library implementing stacks?

Hint: It is impossible to solve this problem with a single stack.

---

9.10

Implement a queue with enqueue, dequeue, and max operations. The max operation returns the maximum element currently stored in the queue.

Hint: When can an element never be returned by max, regardless of future updates?

Answers

9.1

Store, alongside the primary stack, enough information to answer max() in constant time. A simple implementation caches the maximum seen so far with every pushed element. A tighter version keeps an auxiliary stack of pairs (max_value, count), pushing a new pair only when the maximum increases and incrementing the count on ties; on pop, decrement the count and remove the pair when it reaches zero. All operations run in $O(1)$ time.

---

9.2

Split the expression into comma-separated tokens and scan from left to right. Push numeric tokens onto a stack. When an operator appears, pop the top two values, apply the operator in the correct order, and push the result. The final stack entry is the answer. This is $O(n)$ time and $O(n)$ space in the worst case.

---

9.3

Scan the string left to right. Push every opening delimiter onto a stack. For each closing delimiter, the stack must be nonempty and its top must be the matching opener; otherwise the string is not well-formed. At the end, the stack must be empty. The algorithm runs in $O(n)$ time and $O(n)$ space in the worst case.

---

9.4

Tokenize on / and process components with a stack of path names. Ignore empty components and .. On .., pop one directory when possible; for relative paths, preserve leading unresolved .. entries, while for absolute paths going above the root is invalid. Reassemble the stack into the normalized path. This is a linear-time, linear-space stack simulation.

---

9.5

The recursive solution is depth-first search with the traversal order node, then jump, then next, skipping already visited nodes by checking whether their order field is still -1. The iterative version simulates that recursion with an explicit stack: when visiting a node, push next first and jump second so the jump edge is processed first. Both versions run in $O(n)$ time; recursion uses call-stack space, while the iterative version uses an explicit stack of size up to $O(n)$.

---

9.6

If buildings arrive east to west, maintain a stack of candidate buildings that still have a sunset view. When a new building arrives, pop every shorter or equal candidate, since the new building blocks all of them, then push the new building. Each building is pushed and popped at most once, so the total running time is $O(n)$.

---

9.7

Use breadth-first traversal. Keep a queue of nodes for the current depth; while processing one level, collect its keys and enqueue the children into a second queue, or equivalently count the current queue size and process exactly that many nodes. Append each per-level list to the result. Every node is enqueued and dequeued once, so the running time is $O(n)$ and the extra space is $O(m)$, where $m$ is the maximum width of the tree.

---

9.8

Represent the queue with a backing array, a head index, a tail index, and the current element count. Enqueue writes at tail, advances it modulo the array size, and increments the count; dequeue reads at head, advances it modulo the array size, and decrements the count. When the queue is full, rotate the live interval so it becomes contiguous, resize the array, and reset head and tail accordingly. Dequeue is $O(1)$ worst-case, and enqueue is $O(1)$ amortized.

---

9.9

Use two stacks. One stack handles enqueues. The other handles dequeues. To dequeue, if the dequeue stack is empty, move every element from the enqueue stack into it, reversing order; then pop from the dequeue stack. Each element moves from one stack to the other at most once, so a sequence of $m$ queue operations takes $O(m)$ total time, i.e., $O(1)$ amortized per operation.

---

9.10

Maintain the queue entries normally, plus a deque of candidates for the maximum. On enqueue, remove elements from the deque’s tail while they are smaller than the new value, then append the new value. On dequeue, if the removed queue element equals the deque’s head, remove that head as well. The current maximum is always the deque head, so max() is $O(1)$. Enqueue and dequeue are $O(1)$ amortized because each element enters and leaves the deque at most once.