Back to DSA Course

Stack is a linear data strucure and follows LIFO. Stack has one end where as Queue has two ends. It contains only one pointer top pointer pointing to the top most element of the Stack.

A Stack can be defined as a container in which the insertion and deletion can be done from the one end known as top of the stack.

Properties of Stack

Follows LIFO(Last In First Out) method.

The LIFO order says that the element which is inserted at the last in the Stack will be the first one to be removed. In LIFO order, the insertion takes place at the rear end of the stack and deletion occurs at the rear of the stack.

Why do we use stacks?

Stacks follows LIFO method and addition and retrieval of a data item takes only Οn time. Stacks are used where we need to access data in the reverse order or their arrival. Stacks are used commonly in recursive function calls, expression parsing, depth first traversal of graphs etc.

Common Operations in Stack

• Push: Add an element to the top of a stack; O(1)
• Pop: Remove an element from the top of a stack; O(1)
• IsEmpty: Check if the stack is empty
• IsFull: Check if the stack is full
• Peek: Get the value of the top element without removing it; O(1)
• Searching for an element in the Stack: O(n)

A Stack is typically implemented with a dynamic array (or) with a singly linked list.

How to understand a stack practically?

There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate that is at the top is the first one to be removed, i.e. the plate that has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.

Time Complexities of operations on stack

The operations push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.

Implementation

There are two ways to implement a stack.

• Using Arrays

package com.praveen.stack.array;

public class StackByArray {

	int[] arr;
	int topOfStack;// keeps track of the cell which is last occupied in Array, this will help in
					// insertion/deletion

	public StackByArray(int size) {
		this.arr = new int[size];
		this.topOfStack = -1;
		System.out.println("Successfully created an empty Stack of Size: " + size);
	}

	public void push(int value) {
		// if array is full, show stack overflow error
		if (isFullStack()) {
			System.out.println("Stack overflow error!!");
		} else {
			arr[topOfStack + 1] = value;
			topOfStack++;
			System.out.println("Successfully inserted " + value + " in the stack");
		}
	}

	public void pop() {
		// if array is empty, show stack underflow error
		if (isEmptyStack()) {
			System.out.println("Stack underflow error!!");
		} else {
			System.out.println("Poping value from Stack: " + arr[topOfStack] + "...");
			topOfStack--;
		}
	}

	public boolean isEmptyStack() {
		// if top pointer is zero, the stack is empty
		if (topOfStack == -1)
			return true;
		else
			return false;
	}

	public boolean isFullStack() {
		if (topOfStack == arr.length - 1) {
			System.out.println("Stack is full !");
			return true;
		} else {
			return false;
		}
	}

	public void peekOperation() {
		if (!isEmptyStack())
			System.out.println("Top of Stack: " + arr[topOfStack]);
		else {
			System.out.println("The stack is empty!!");
		}
		System.out.println();
		System.out.println();
	}

	public void deleteStack() {
		arr = null;
		System.out.println("Stack is successfully deleted");
	}

}

Pros: Easy to implement. Memory is saved as pointers are not involved.

Cons: Fixed Size. It is not dynamic. It doesn't grow or shrink depending on needs at runtime.

• Using Linked List

package com.praveen.stack.linkedlist;

import com.praveen.linkedlist.SingleLinkedList;

public class StackByLinkedList {

	SingleLinkedList list;

	// constructor
	public StackByLinkedList() {
		list = new SingleLinkedList();
	}

	public void push(int value) {
		if (list.getHead() == null) {
			list.createSingleLinkedList(value);
		} else {
			list.insertInLinkedList(value, 0);
		}
		System.out.println("Inserted " + value + " in Stack !");
	}

	public int pop() {
		int value = -1;
		if (isEmpty()) {
			System.out.println("Stack underflow error!!");
		} else {
			value = list.getHead().getValue();
			list.deletionOfNode(0);
		}
		return value;
	}

	public boolean isEmpty() {
		if (list.getHead() == null)
			return true;
		else
			return false;
	}

	public int peek() {
		if (!isEmpty())
			return list.getHead().getValue();
		else {
			System.out.println("The stack is empty!!");
			return -1;
		}
	}

	public void deleteStack() {
		list.setHead(null);
	}

}

Pros: The linked list implementation of stack can either grow or shrink according to the needs at runtime.

Cons: Requires extra memory due to involvement of pointers.

When to Use/Avoid Stack?

When to Use

• Helps manage data in particular way(LIFO)
• Cannot be easily corrupted(No one can insert data in middle)

When to Avoid

• Random Access not possible(If we have done some mistake it is costly to rectify)

Applications of Stack

• Stacks can be used to check for the balancing of paranthesis in an expression.
• Infix to Postfix/Prefix conversion.
• Redo-undo features at many places such as editors, photoshop, etc.
• Forward and backward feature in web browsers. And Many More...