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:
- push (inserting data onto stack)
- pop (removes the data from the top)
Implementation
- Simple Array based implementation
- 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");
}
}
}
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");
}
}
My Github Link: https://github.com/aarushi-nema/data-structure
References:
1. https://www.geeksforgeeks.org/