Stack is one of the most used data structures in computer science. It is a linear data structure which supports ordering of elements in Last In First Out order(LIFO).

The very typical real world example is a stack of plates, where new plates are put on the top of the existing ones and the top ones are the first one to be removed.

There are numerous applications which involve stack in computer science, some of them are,

  • Compilers/Run time environments, which use it to store recursive calls.
  • Tree Traversals
  • Software Applications which provide Undo/Redo operations like text editors.
  • Evaluation of mathametical notations like Infix/Postfix etc.

Stack provides the following basic operations,

  • Push
    Pushes the element to the top of the stack.
  • Pop
    Pops or removes the top element of the stak.
  • Top
    Returns the top element of the stack.
  • isEmpty
    Returns true if the stack is empty or returns a false otherwise.
  • Size
    Returns a integer value which is the number of elements currently in the stack.
Implementation

Typically stack is implemented using,

The major operations in a stack involve adding and removing elements at the top, if we use an array to implement it, we will end up moving the array elements one step to the right every time there's a push or pop operation which is very expensive.

On the other hand, a linked list allows addition and removal of an element at the start in constant time. Hence we will use a single linkedlist to implement a stack.

We can start with an empty linkedlist where 'head' is null, use it to append elements or remove for push and pop operations.

Psuedo Code
  • Push
if head is null
    create node with input value
    assign head to the new node
else
    create node with input value
    point's new node's next to head
    make the new node as head
  • Pop
if head is null
    return null
else
    store head value to temp
    point head to the head's next
    return the temp
  • Top
if head is null
    return null
else
   return head's value
  • isEmpty
return head==null

Below is the full java implementation for stack using linkedlist,


/*
 * Author : Venkatesh Thallam
 */

/*
 * Node Definition for the underlying linked list we use to implement stack
 * */
class Node {
	int val;
	Node next;

	Node(int val) {
		this.val = val;
	}
}

public class StackImplementation {

	Node head;

	StackImplementation() {
		head = null;
	}

	public static void main(String[] args) {
		StackImplementation stack = new StackImplementation();
		stack.push(8);
		stack.push(28);
		stack.push(38);
		stack.push(48);
		stack.push(68);
		stack.pop();
		stack.push(98);
		System.out.println(stack.size());
		System.out.println(stack.isEmpty());
		System.out.println(stack.top());
	}

	/*
	 * Pushes an element to the top of the stack
	 */
	public void push(int val) {
		if (head == null) {
			head = new Node(val);
		} else {
			Node newhead = new Node(val);
			newhead.next = head;
			head = newhead;
		}
	}

	/*
	 * Pops the top element and returns it
	 */
	public Integer pop() {
		if (head == null)
			return null;
		else {
			Integer poppedval = head.val;
			head = head.next;
			return poppedval;
		}
	}

	/*
	 * Returns a boolean that tells if a stack is empty
	 */
	public boolean isEmpty() {
		return head == null;
	}

	/*
	 * Returns the total elements currently in the stack
	 */
	public int size() {
		int count = 0;
		Node temp = head;
		while (temp != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}

	/*
	 * Returns the top element of the stack.
	 */
	public Integer top() {
		if (head != null)
			return head.val;
		else
			return null;
	}

}

Time Complexity

The time complexity for each of the stack operations is below,

  • Push - O(1)
  • Pop - O(1)
  • Top - O(1)
  • isEmpty - O(1)
  • Size - O(n), since this requires checking all values of stack.