Week 8: Lab Document, 10/18

In class we studied the implementation of the Queue ADT and saw how the Queue ADT plays a critical role in breadth-first search. The Stack ADT is similar to the Queue ADT, except that elements leave the stack according to the "last in first out" (LIFO) rule.

More specifically, Stack ADT supports the following operations:

  1. void push(item): this inserts item into the stack,
  2. item pop(): this deletes and returns the most recent item in the stack,
  3. item peek(): this returns, but does not delete the most recent item in the stack,
  4. boolean isEmpty(): this returns true if the stack is empty; false otherwise.

Problem: Implement a Stack ADT so that all of the operations mentioned above run in constant time. You are free to use an array for the implementation and you may also assume that the maximum number of items that will be present in the stack at any one time is known to the user ahead of time.