Data Structures and Algorithms
with ObjectOriented Design Patterns in C++

The arraybased stack implementation
shown in Programs , , and
uses a fixed length array.
As a result, it is possible for the stack to become full.
However, the Array<T> class defined in Chapter
provides a SetLength member function which can be used
to change the length of the array.

Rewrite the Push routine so that it doubles
the length of the array when the array is full.

Rewrite the Pop routine so that it halves
the length of the array when the array is less than half full.

Show that the average time for both push and pop
operations is O(1).
Hint: Consider the running time required to
push items onto an empty stack, where .

Consider a sequence S of push and pop operations
performed on a stack that is initially empty.
The sequence S is a valid sequence of operations if
at no point is a pop operation attempted on an empty stack
and if the stack is empty at the end of the sequence.
Design a set of rules for generating a valid sequence.

Devise an implementation of the Queue
abstract data type using two stacks.
Give algorithms for the Enqueue and Dequeue operations,
and derive tight bigoh expressions for the running times
of your implementation.

Write each of the following infix expressions
in postfix notation:
 ,
 ,
 ,
 ,
 , and
 .

Write each of the following postfix expressions
in infix notation:
 ,
 ,
 ,
 ,
 , and
 .

Devise an algorithm which translates a postfix expression
to a prefix expression.
Hint: Use a stack of strings.

The arraybased queue implementation
shown in Programs , and
uses a fixed length array.
As a result, it is possible for the queue to become full.

Rewrite the Enqueue routine so that it doubles
the length of the array when the array is full.

Rewrite the Dequeue routine so that it halves
the length of the array when the array is less than half full.

Show that the average time for both enqueue and dequeue
operations is O(1).

Stacks and queues can be viewed as special cases of deques.
Show how all the operations on stacks and queues
can be mapped to operations on a deque.
Discuss the merits of using a deque to implement a stack or a queue.

Suppose we add a new operation to the stack ADT
called FindMinimum
that returns a reference to the smallest element in the stack.
Show that is its possible to provide an implementation
for FindMinimum that has a worst case running time of O(1).

The breadthfirst traversal routine shown in Program
visits the nodes of a tree in the order of their levels in the tree.
Modify the algorithm so that the nodes are visited in reverse.
Hint: Use a stack.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.