CSE 143/AC : 20 July 2000

Basic ADTs: stacks, queues

Working with raw linked lists and vectors is prone to error. Often, we want to restrict the set of operations that are possible on a data structure. The stack and queue ADTs specialize the idea of a sequence so that insertion and deletion must always occur at the same point each.

• A stack can only insert and delete at one end of the list, called the "top" of the stack. The stack is therefore a LIFO ("last in, first out") data structure. The operations usually have the following names:

  class Stack { public: void push(Item item); // "insert at top" Item pop(); // "remove top element" Item peek() const; // "examine top element" bool isEmpty() const; int size() const; // ... };

• A queue can only insert at one end (sometimes called the back of the queue), remove at the opposite end (sometimes called the front of the queue). A queue is therefore a FIFO ("first in, first out") data structure. As with stacks, queue operations have their own names:

  class Queue { public: void enqueue(Item item); // "insert at back" Item dequeue(); // "remove front element" Item peekFront() const; // "examine front element" bool isEmpty() const; int size() const; // ... };

Notice that neither ADT defines a representation. This is what makes it abstract.