CS 305 Test 4

CS 305, Computer Algorithms I

Fall 2003 - Test 4

Describe how you would implement a stack using a queue. You don't have to go into great detail, just indicate how you'd implement push() and pop(). You also don't have to worry about efficiency.
The problem with queues is that they preserve FIFO order, and stacks preserve LIFO order. However, FIFO is just LIFO reversed, and that's our clue.
Given a single queue q, we can implement the rotate() operation as follows:
```
rotate()
  q.enque(q.deque())
```
Assuming deque() returns the dequeued element. push() is implemented directly with enque():
```
push(v)
  q.enque(v)
```
pop() is simple but expensive:
```
pop()
  if queue_size < 1
    stack_underflow
  for i = 1; i < queue_size; i++
    rotate()
  q.deque()
```
In other words, rotate the most recently queued element to the head of the queue and dequeue it.
Most of the answers were on the right track, but didn't go far enough in explaining how the queue would be manipulated. Several wrong answers engaged in non-queue-like behavior, such as adding and removing from the same end, and traversing the queue.
Nyhoff models a stack as both plates on a spring and as books on a table. Which is the more appropriate model when stacks are implemented as arrays? Explain.
The important property of the plates on a spring is that the top plate is always at the same place in the stack: at the top. Maintaining this property with an array is expensive because every push and pop requires shifting all elements down and up the array.
On the other hand the important property of books on a table is that the top moves up and down the stack while the bottom remains stationary. This is a much less expensive model to implement in an array.
Given that this was from the book, many of the answers were amusingly beside the point, including one answer that voted for books on the table because you could read the titles on the spines.
Recall the array-list hybrid implementation of stacks that uses doubling for each successive array allocation. As the stack shrinks, we can recover the array space by deleting the arrays, or by hanging them on a free list. If we use the free-list approach, should the free list be implemented as a stack or a queue?
The arrays are allocated in increasing order, doubling on each allocation. The arrays are deallocated in reverse order, essentially halving each successive array size.
If the arrays are deallocated in one order and are allocated in the other order, we need a free list that can reverse the order of deallocation, which means we need a stack.
Most of the answers didn't establish the importance of treating the freed arrays in a particular order, which made this question harder to answer. Other answers explicitly assumed that order was unimportant, and then chose stacks because they were simpler than queues.
The swap(a, b) operator swaps the values of its two operands. For example
```
int i = 3
int j = 4

swap(i, j)

// j = 3
// i = 4
```
Write a function that uses swap() to remove an element from a linked list. Your function must work for any element in the list.
See Test 3 question 2.

This page last modified on 22 November 2003.