A Stack is a linear data structure (i.e. its elements form a sequence) where operations are performed at the ‘top’ of the stack. The order may be FIFO (First In, First Out) or more commonly LIFO (Last In, First Out).

An analogue in real life is a stack of plates — with a FIFO approach, you take a plate from the bottom of the pile whereas with a LIFO approach you take a plate from the top.

The stack data structure has a multitude of uses, an obvious one is your browser history (a LIFO stack). Typically, a stack implementation will provide at least three operations — push, pop, and peek.

Pushing onto the stack can be visualised at follows:

Popping from the stack can be visualised at follows:

Complexity

🔔 Complexity is considered in terms of worst case.

Time

Space

A LIFO implementation

Here we’re using an array as a backing store for simplicity (although you can of course use a different approach such as a linked list).

Define a Stack<T> class with the following methods:

• isEmpty - determines whether the stack has elements
• length - returns the number of elements on the stack
• peek - returns the top element from the stack without popping it
• pop - pops from the stack
• push - pushes onto the stack

// TypeScript
export class Stack<T> {
	private elements: T[];

	public constructor() {
		this.elements = new Array<T>();
	}

	public isEmpty(): boolean {
		return this.elements.length < 1;
	}

	public length(): number {
		return this.elements.length;
	}

	public peek(): T {
		return this.elements[this.elements.length - 1];
	}

	public pop(): T {
		if (this.elements.length > 0) {
			return this.elements.pop();
		}
	}

	public push(item: T): void {
		this.elements.push(item);
	}
}

Code on Github