Stack

A stack is an abstract data type that is a ‘linear’ (one-dimensional) data structure, in which items are accessed in a Last In First Out (LIFO) order.

Definition §

• Items are accessed in Last In First Out (LIFO) order
• Only the top (head) can be viewed (via peek) or returned (via pop)
• Adding new items is referred to as pushing
• Removing items is referred to as popping
• The last item to enter a stack is the first to come out of it

ADT Signature §

name stack;
import elem, boolean;
ops:
	newStack : → stack; 
	push : stack × elem → stack;
	pop : stack → stack; 
	top : stack → elem; 
	isEmpty : stack → boolean; 
	etc.

Time Complexity Analysis §

Implemented with unsorted array §

We treat pushing as putting elements at the end of the array, and popping as removing from the end.

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Push	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Equivalent to insertion of an element after index $n-1$. Array insertion after end takes constant time
Pop	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Equivalent to deleting the last element. Takes constant time.
Peek	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Assuming we keep track of $n$, this is equivalent to array access, which is constant time.

Implemented with linked list §

Uses §

• Call Stack