Stack Data Structure – Basicsbehind.com

What is Stack?

Think Stack as naturally model piles of objects, for example the dinner plates. After a new plate is washed, it is pushed on the top of the stack. When serving food, a clean plate is popped off the stack. Here the plates don’t care which one to be used next that is one of most important reason to use Stack data structure.

Important points:

Stack is a container where items are retrieved by last-in, first-out (LIFO) order.
Stack is the right container to use when retrieval order doesn’t matter
Stack order is important in processing any properly nested structure. This includes recursive calls, parenthesized formula such as postfix evaluation, and depth first search traversal in Graph etc.
Stacks are very simple to implement.

Operations on a Stack:

push(x): Insert item x at the top of stack.
pop(): Return and remove the top element of stack.
peek(): Return the top element of stack.
full(): Test whether the more items can be pushed to the stack.
empty(): Test whether the more items can be popped from the stack.

Implementation of Stack Data Structure:

Implement using simple array. (bounded)
Implement using linked list. (unbounded)

Stack using array: This is very easy to implement. Create an array to hold the Stack values. Maintain a top which will point to the currently pushed element. Initially the top will be -1.
When you push a value to the Stack, you increment the top by 1. When you pop a value from the stack, you return the top element and then decrement the top.
For example – consider below stack. Initially top were -1. Before pushing 5, increment top = top+1 –top= -1+1 =0, 5 is pushed to the Stack at 0th position. Similarly before pushing 10, top is incremented by 1 and became 0+1 =1 and 10 is pushed at 1^st position.

Stack implementation in Java using Array

public class Stack {

	private int maxSize;
	private int[] stackArray;
	private int top;
        
        //initialize stack
	public Stack(int size) {
		stackArray = new int[size];
		maxSize = size;
		top = -1;
	}

	public void push(int value) {
		if (isFull()) {
			System.err.println("Stack is full..");
			return;
		}
		stackArray[++top] = value;
	}
        //Return and remove top element
	public int pop() {
		if (!isEmpty()) {
			return stackArray[top--];
		} else {
			System.err.println("Stack is empty...");
			return -1;
		}
	}
	//Return top element
	public int peek() {
		if (!isEmpty()) {
			return stackArray[top];
		} else {
			System.err.println("Stack is empty...");
			return -1;
		}
	}

	public boolean isEmpty() {
		return top == -1;
	}

	public boolean isFull() {
		return top == maxSize;
	}

	public static void main(String[] args) {
		Stack stack = new Stack(10);
		for (int i = 0; i < 10; i++) {
			stack.push(i);
		}
		for (int i = 0; i < 10; i++) {
			System.out.print(stack.pop()+" ");
		}
	}
}

Output
---------
9 8 7 6 5 4 3 2 1 0

Stack implementation in Java using Linked List

Create a Node class which will hold value and link to the next element.

public class Node {

	private int value;
	private Node next;
	
	public Node(int value) {
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

Create the Stack with all the methods.

package com.test.stack;

public class Stack {

	private Node top;
	private int size;

	public Stack() {
		top = null;
		size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return top == null;
	}

	public void push(int value) {
		Node node = new Node(value);
		node.setNext(top);
		top = node;
		size++;
	}

	public int pop() {
		if (isEmpty()) {
			System.err.println("Stack is empty");
		}
		Integer temp = top.getValue();
		top = top.getNext();
		size--;
		return temp;
	}

	public int peek() {
		if (isEmpty()) {
			System.err.println("Stack is empty");
		}
		return top.getValue();
	}

	public static void main(String[] args) {
		Stack stack = new Stack();
		for (int i = 0; i < 10; i++) {
			stack.push(i);
		}
		for (int i = 0; i < 10; i++) {
			System.out.print(stack.pop() + " ");
		}

	}
}

Output
---------
9 8 7 6 5 4 3 2 1 0

Next ↠Queue data structure ↠↠

References: