CS 305 Test 4

CS 305, Computer Algorithms I

Fall 2003 - Test 4

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 exchange two elements in a linked list. Your function must exchange the elements themselves, not just the values stored in the elements, and should work for any two valid list elements (you may not assume the two elements are different).
See Test 3 question 4.
Describe how you'd implement a queue using two stacks. You don't have to go into great detail, just indicate how you'd implement enque() and deque(). You also don't have to be worried about efficiency.
The problem with stacks is that they're FIFO, while queues are LIFO. However, stacks are also reversing, so if we load a stack in FIFO order and then reverse it, we get LIFO order. Also note that if we reverse LIFO order we get back FIFO order.
The implementation follows the observations in the previous paragraph. There are two stacks, called enqueuing and dequeuing; the invariant is
```
enqueuing.empty() or dequeuing.empty()
```
enque() is implemented as
```
enque(v)
  if not dequeuing.empty()
    pop dequeuing into enqueuing, switching from FIFO to LIFO order.
  enqueuing.push(v)  
```
deque() is implemented as
```
deque()
  if not enqueuing.empty()
    pop enqueuing into dequeuing, switching from LIFO to FIFO order.
  dequeuing.pop(v)  
```
Most of the answers for this were more or less correct.
Consider an 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.
Given a stack ADT in which the pop() operation returns the top element, is the implementation
```
int pop() {

  if stack_size < 1
    stack_underflow

  return elements[stack_size--]  
```
correct? Explain, making your assumptions clear.
With the not unreasonable assumptions that stack_size is equal to the number of elements in the stack, and that the top of the stack has the largest index, the given code is incorrect: it has an off by one error.
If an array has n elements, the indices of the elements are 0 to n - 1. stack_size is the index of the next array element to receive a value; it has to be decreased by one to point to the actual top of the stack (assuming there are elements in the stack). Unfortunately stack_size-- returns the old value of stack_size. The correct code is
```
  return elements[--stack_size];
```
Given that we went over this question in class, there were some truly strange answers. Most of the correct answer, however, went right to the point.

This page last modified on 22 November 2003.