|
Answer» We can easily implement a stack using the LINKED list. A stack will have a top pointer which is the “head” of the stack where the item will be pushed and popped at the head of the list. The link field of the first node will be null and the link field of the second field will have the address of the first node and so on and the address of the last node will be stored in the “top” pointer. The major advantage of linked list usage over an array is we can implement a stack that can grow or shrink according to the need. As the array is of fixed size, it will lead to stack overflow by putting restrictions on the maximum capacity of an array. In the linked list, each new node will be allocated dynamically, so overflow will not occur. Stack Operations are: - PUSH() : This function will INSERT an element into the linked list which in turn will be added to the top node of Stack.
- pop() : This function will return the top element from the Stack and the top pointer will be moved to the second node of Stack.
- peek(): This function will return the topmost element in the stack.
- display(): This function will print all the elements of Stack.
- isEmpty(): It will return true if the Stack is empty otherwise it returns false.
// Java program// Importing packageimport static java.lang.System.exit; // Creating Stack using Linked listclass StackLinkedlist { // A node of linked list private class Node { // INTEGER DATA int info; // Reference variable of Node type Node link; } // Creating a global top reference variable Node top; // Constructor StackLinkedlist() { this.top = null; } // Function for adding an element i in the stack public void push(int i) // Insert at the beginning { // Creating a new node t and allocate memory Node t = new Node(); /* Checking if the stack is full, then inserting an element would lead to stack overflow*/ if (t == null) { System.out.print("\nStack Overflow"); return; } // Initializing data into info field of t node t.info = i; // Add top reference into link field of t node t.link = top; // Update top reference top = t; } // Function for checking if the stack is empty or not public boolean isEmpty() { return top == null; } // Function for returning topmost element of a stack public int peek() { // Checking for empty stack if (!isEmpty()) { return top.info; } else { System.out.println("Stack is empty"); return -1; } } // Function to pop the topmost element from the stack public void pop() { // Checking for stack underflow if (top == null) { System.out.print("\nStack Underflow"); return; } // Updating the top pointer to point to the next node top = (top).link; } public void show() { // Checking for stack underflow if (top == null) { System.out.printf("\nStack Underflow"); exit(1); } else { Node tmp = top; while (tmp != null) { // Printing node data System.out.printf("%d->", tmp.info); // Assigning tmp link to tmp node tmp = tmp.link; } } }}//Class with main() functionpublic class ImplementStack { public static void main(String[] args) { // Creating object for the StackLinkedList class StackLinkedlist ob = new StackLinkedlist(); // Inserting values for stack ob.push(15); ob.push(20); ob.push(25); ob.push(30); // Printing elements of Stack ob.display(); // Printing Top element of Stack System.out.printf("\nTop element of Stack is %d\n", ob.peek()); // Deleting top element of the Stack ob.pop(); ob.pop(); // Printing Stack elements ob.show(); // Printing Top element of Stack System.out.printf("\nTop element of Stack is %d\n", ob.peek()); }}Output: 30->25->20->15->Top element of Stack is 3020->15->Top element of Stack is 20
|
