Stack Basics

Ever wondered you see the most recent messages that you see at the top? Or how the Undo/Redo function in Excel or Word know what your previous function was? Or how the Back/Forward on your browser knows in which order you visited various websites?

Well all of the above examples ( and a Ton of other applications) make use of what is known as a STACK (Take in the literal sense like a stack of plates or books.)

In technical language- A Stack is a non-primitive linear data structure in which elements can be inserted and deleted only from one side of the list, called the top. A stack follows the LIFO (Last In First Out) principle, i.e., the element inserted at the last is the first element to come out.

The main Stack operations include:

  1. push (inserting data onto stack)
  2. pop (removes the data from the top)

Implementation

  1. Simple Array based implementation
  2. Linked List implementation

Note: The following coding exercises have been uploaded in JAVA.

Coding Exercise 1: Array Implementation

package stack;
//Representation of Stack as a Simple Array
public class Program001array_implementation {
	
	static class Stack{
		
		final int MAX= 5;
		int [] data= new int[MAX];
		int top=-1;
		
		public void push(int element){
			if(top<MAX-1){
				top++;
				data[top]=element; 
			}
			
			else 
				System.out.println("Stack is Full");
		}
		
		public Integer pop(){          
			if(top==-1){
				System.out.println("Stack is Empty");
				return null;
			}
			
			return data[top--];
			
		}
		
		public void stackdisplay ()
		{
			for(int i=top; i>=0; i--){
				System.out.print(data[i] + " ");
			}
			
			System.out.println();
		}
		
		public static void main (String [] args)
		{
			Stack s= new Stack();
			
			s.push(2);
			s.stackdisplay();
			s.push(3);
			s.push(4);
			s.stackdisplay();
			s.push(5);
			s.push(6);
			s.push(7);
			s.stackdisplay();
			System.out.println(s.pop() + " removed");
			s.stackdisplay();
			System.out.println(s.pop() + " removed");
			System.out.println(s.pop() + " removed");
			System.out.println(s.pop() + " removed");
			System.out.println(s.pop() + " removed");
			System.out.println(s.pop() + " removed");
			
		}
		
	}
}

Download Code

Coding Exercise 2: Linked List Implementation

package stack;
import stack.Program001array_implementation.Stack;
public class Program002linked_list_implmentation {
	static class Linked_List {
		Node head;
		class Node {
			int data;
			Node next;
			Node(int d) {
				data = d;
				next = null;
			}
		}
		public void insert_in_beginning(int element) {
			Node new_node = new Node(element);
			new_node.next = head;
			head = new_node;
		}
		public Integer delete_from_beginning() {
			if (head == null)
				return null;
			int r = head.data;
			head = head.next;
			return r;
		}
		public void display() {
			Node n = head;
			while (n != null) {
				System.out.print(n.data + " ");
				n = n.next;
			}
			System.out.println();
		}
	}
	static class Stack {
		final int MAX = 5;
		int top = -1;
		Linked_List data = new Linked_List();
		public void push(int element) {
			if (top < MAX - 1) {
				top++;
				data.insert_in_beginning(element);
			}
			else
				System.out.println("Stack is Full");
		}
		public Integer pop() {
			if (top == -1) {
				System.out.println("Stack is empty");
				return null;
			}
			int r = data.delete_from_beginning();
			top--;
			return r;
		}
		public void stackdisplay() {
			data.display();
		}
	}
	public static void main(String[] args) {
		Stack s = new Stack();
		s.push(2);
		s.stackdisplay();
		s.push(3);
		s.push(4);
		s.stackdisplay();
		s.push(5);
		s.push(6);
		s.push(7);
		s.stackdisplay();
		System.out.println(s.pop() + " removed");
		s.stackdisplay();
		System.out.println(s.pop() + " removed");
		System.out.println(s.pop() + " removed");
		System.out.println(s.pop() + " removed");
		System.out.println(s.pop() + " removed");
		System.out.println(s.pop() + " removed");
	}
}

Download Code

My Github Link: https://github.com/aarushi-nema/data-structure

References:
1. https://www.geeksforgeeks.org/

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close