What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. It contains only one pointer top pointer pointing to the topmost element of the stack. A stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.

Initialization of Stack

we can initialize stack by using

Stack stack1 = new Stack(); or

Stack<String> stack2 = new Stack<String>();

Standard Stack Operations

1. Adding Elements: In order to add an element to the stack, we can use the push() method. This push() operation places the element at the top of the stack.

example. stack1.push("4");

1. Removing Elements: To pop an element from the stack, we can use the pop() method. The element is popped from the top of the stack and is removed from the same.

   example. stack1.pop()

   It returns the popped element.

2. Accessing the Element: To retrieve or fetch the first element of the Stack or the element present at the top of the Stack, we can use peek() method. The element retrieved does not get deleted or removed from the Stack.

   example. stack1.peek()

   It returns the element at the top of the stack.

3. isEmpty(): It determines whether the stack is empty or not.

4. isFull(): It determines whether the stack is full or not.

5. count(): It returns the total number of elements available in a stack.

6. display(): It prints all the elements available in the stack.

Applications of Stack

1. Balancing of symbols: Stack is used for balancing a symbol.

2. String reversal: Stack is also used for reversing a string.

3. UNDO/REDO: It can also be used for performing UNDO/REDO operations.

4. DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.

2. Add element at the position of incremented top. This is referred to as adding new element at the top of the stack.

Stack is overflown when we try to insert an element into a completely filled stack therefore, our main function must always avoid stack overflow condition.

Deletion of an element from a stack (Pop operation)

Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack.

The underflow condition occurs when we try to delete an element from an already empty stack.

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without deleting it. Underflow condition can occur if we try to return the top element in an already empty stack.

Java codes for push(), pop() and peek()

// Array implementation of stack

class Stack { private String[] arr; private int top;

Stack(int size) { this.arr = new String[size]; this.top = -1; }

public void push(String element) { if(top == arr.length-1) { // Stack overflow System.out.println("Stack is full"); } else { top++; arr[top] = element; } }

public int peek() { if(top == -1) { System.out.println("Stack is empty"); return -1; } else { return arr[top]; } }

public String pop() { if(top == -1) { // Stack underflow System.out.println("Stack is empty"); return null; } else { String element = arr[top]; top--; return element; } } }

public class Main {

public static void main(String[] args) { Stack stack = new Stack(5);

stack.push("Item 1"); stack.push("Item 2"); stack.push("Item 3");

System.out.println("Pushed 3 items to stack"); }

}

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field.

Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list implementation is different from that of an array implementation. In order to push an element onto the stack, the following steps are involved.

1. Create a node first and allocate memory to it.

2. If the list is empty then the item is to be pushed as the start node of the list. This includes assigning value to the data part of the node and assign null to the address part of the node.

3. 1. If there are some nodes in the list already, then we have to add the new element in the beginning of the list (to not violate the property of the stack). For this purpose, assign the address of the starting element to the address field of the new node and make the new node, the starting node of the list.

The elements are accessed in order, node 0, node 1, node 2, node 3, node 4 and so on ...

Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :

1. Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.

2. Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.

Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. For this purpose, we need to follow the following steps.

1. Copy the head pointer into a temporary pointer.

2. Move the temporary pointer through all the nodes of the list and print the value field attached to every node.

Java codes for push(), pop() and peek()

class Node { int data; Node next;

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

class Stack { Node top;

// Push element onto stack public void push(int data) { Node newNode = new Node(data); if(top == null) { top = newNode; return; } newNode.next = top; top = newNode; }

// Pop top element public int pop() { if(top == null) { System.out.println("Stack is empty"); return -1; } int topData = top.data; top = top.next; return topData; }

// Peek top element public int peek() { if(top == null) { System.out.println("Stack is empty"); return -1; } return top.data; }

}

public class Main { public static void main(String[] args) { Stack stack = new Stack(); stack.push(1); stack.push(2); stack.push(3);

System.out.println(stack.peek()); // Prints 3 System.out.println(stack.pop()); // Prints 3 System.out.println(stack.peek()); // Prints 2

} }

That's all for Today ...

Keep reading .....