Week 4. Stacks and Queues

Abstract Data Type

Abstract data type (ADT): model of a data structure that specifies the type of data stored, the operations supported on them, and the type of parameters of the operations. An ADT specifies what each operation does, but not how it does it.

Link to original

Stack ADT

Stack (ADT)

An instance of the stack data structure is a sequence of elements (objects) with one end designated as the top of the stack:

$$E_1,E_2,E_3,\dots ,E_n$$

Main stack operations (LIFO):

• push(e): insert element $e$ at the top of the stack
• pop(): remove and return the element at the top of the stack Throws an error if stack is empty.

Additional stack operations:

• top(): return the top element in the stack without removing it Throws an error if stack is empty.
• size(): return the number of elements stored
• isEmpty(): check if the stack is empty

Java Stack Interface

Below is a Java interface according to our stack ADT:

public interface Stack<E> {
	public void push(E element);
	public E pop() throws EmptyStackException;
	public E top() throws EmptyStackException;
	public int size();
	public boolean isEmpty();
}

Link to original

Array-based implementation

Array-based stack implementation

A simple way of implementing the stack ADT is using an array where we add elements left to right and a variable keeps track of the index of the top element. The array storing the stack elements may become full, a push operation will then throw a FullStackException.

In terms of performance:

• Let $n$ be the number of elements in the stack.
• The space used is $O(n)$
• Each operation runs in time $O(1)$

Limitations:

• The maximum size of the stack must be defined ahead of time and cannot be changed.
• Trying to push a new element into a full stack causes an implementation specific exception.

Link to original

Queue ADT

Queue (ADT)

The queue ADT stores a collection of arbitrary elements. Insertions and deletions follow FIFO. The elements are arranged in a sequence. Insertions are at the rear of the queue and removals are at the front.

Main queue operations:

• enqueue(e): inserts element $e$ at the end of the queue
• dequeue(): removes and returns the element at the front of the queue

Auxiliary queue operations:

• front(): returns the element at the front without removing it
• size(): returns the number of elements stored
• isEmpty(): returns a boolean value indicating whether no elements are stored

Exceptions:

• Attempting dequeue or front on an empty queue throws EmptyQueueException.

Queue Interface in Java

Below is a Java interface according to our queue ADT:

public interface Queue<E> {
	public int size();
	public boolean isEmpty();
	public E front() throws EmptyQueueException;
	public void enqueue(E element);
	public E dequeue() throws EmptyQueueException;
}

Link to original

Array-based implementation

Use an array of size $N$ in a circular fashion. Two variables keep track of the front and rear:

• $f$: index of the front element
• $r$: index immediately past the rear element The array location $r$ is kept empty.

Various implementations of methods:

def size():
	return (r - f + N) mod N
 
def isEmpty():
	return f == r
 
def enqueue(e):
	if size() == N - 1:
		raise FullQueueException
	else:
		Q[r] = e
		r = (r + 1) mod N
 
def dequeue():
	if isEmpty():
		raise EmptyQueueException
	else:
		e = Q[f]
		f = (f + 1) mod N
		return e