Prerequisites:
What is Stack?
Stack is a linear Data Structure that follows LIFO(Last In First Out) order while performing its operations. The main operations that are performed on the stack are mentioned below:
- push() : inserts an element at beginning of the stack(In singly linked list)
- pop() : deletes first element from of the stack(Topmost element)
- peek() : returns the element which is at the beginning of the stack
Other than this operation there is another one called display(), which displays the contents of the stack. Now we are going to implement the Stack using a singly linked list and generics. If you are aware of the concept of generics, which allows us to use any data type as a type parameter, and the type of data is determined at the time of object creation. The advantages of using generics in classes, methods, and interfaces are, type-checking is done during object creation, code can be reused and the performance is better.
Let’s see the implementation in the following example :
Java
// Java Program to Implement Stack Using LinkedList// and Generics// importing the required packagesimport java.util.Scanner; class LinkedStack<T> { // create a Node class private class Node { // A Node contains two parts inside it one is 'data' // part and the other is 'next' which has a // reference to the next Node T data; Node next; // define a parameterized constructor which // initializes the local variables of Node class public Node(T data, Node next) { this.data = data; this.next = next; } public String toString() { // returns the data in // string format return data.toString(); } } // Here top acts as a reference to the Node private Node top; public boolean isEmpty() { return top == null; } public void push(T ele) { // Every time when a new element is pushed onto the // stack a new Node is created and top is pointed to // it top = new Node(ele, top); } public T pop() { // check if elements present on Stack or not if (top == null) return null; else { // if present do the following // Assign the topmost element of // stack into a variable T element = top.data; // make top to point it's next // node top = top.next; // Popped element is returned to // the main return element; } } public T peek() { // return the element which is // at beginning of the stack return top.data; } public int size() { // This method returns the no.of elements present on // the stack int count = 0; Node temp = top; while (temp != null) { // increment count count += 1; // make temp to point it's // next Node temp = temp.next; } return count; } public void display() { // This method displays every element of the Stack // LinkedList System.out.println( "The elements of the stack are: "); Node temp = top; while (temp != null) { // print the data in 'temp' System.out.print(temp.data + "->"); // make temp to point it's // next Node temp = temp.next; } // indicates that last Node is not // pointing to any Node System.out.println("null"); System.out.println(); }} // main methodpublic class GFG { // main driver method public static void main(String[] args) { // create an object of LinkedStack LinkedStack<Double> ls = new LinkedStack<>(); // push an element onto the stack // push 10 ls.push(10.0); // push 20 ls.push(20.0); // display the contents of the stack // try to push some more elements ls.display(); ls.push(30.0); ls.push(40.0); System.out.println( "After pushing 10.0,20.0,30.0,40.0"); ls.display(); // pop element from stack(40.0 is popped // out) ls.pop(); // 30.0 is popped out // printing the stack after poping the elements ls.pop(); System.out.println("after pop() operation"); ls.display(); // display the topmost element of the stack System.out.println( "current Topmost element of stack: " + ls.peek()); // display the no.of elements of the stack System.out.println("current size of the stack: " + ls.size()); System.out.println(); // Now create another Object with String Type // parameter LinkedStack<String> lss = new LinkedStack<>(); // push a String message // onto the stack lss.push("How's your day?"); lss.push("geek"); lss.push("Hello!!"); // Display the contents of the stack lss.display(); lss.pop(); System.out.println("after pop() operation"); lss.display(); // display the topmost string on // the stack System.out.println( "current Topmost element of stack: " + lss.peek()); System.out.println("current size of the stack: " + lss.size()); // Although the implementation is using generics try // yourself and perform the above operations using // different datatypes as type parameters.. }} |
The elements of the stack are: 20.0->10.0->null After pushing 10.0,20.0,30.0,40.0 The elements of the stack are: 40.0->30.0->20.0->10.0->null after pop() operation The elements of the stack are: 20.0->10.0->null current Topmost element of stack: 20.0 current size of the stack: 2 The elements of the stack are: Hello!!->geek->How's your day?->null after pop() operation The elements of the stack are: geek->How's your day?->null current Topmost element of stack: geek current size of the stack: 2
Time and Space Complexity
Time Complexity : O(1)
For push(), pop(), and peek() operations because we are just retrieving the contents of the stack which takes constant time, while the operations size() and display() take O(N) time complexity because these methods iterate over all elements of the stack, where ‘N’ is the number of nodes of the stack
Auxiliary space : O(N)
The space required for the code to store each node(data and reference to the next Node) of the stack is O(1), so if there are ‘N’ nodes the space complexity becomes O(N).
we can also write the above main method in menu-driven format, here is the code for you (which has Double data type as a type parameter you can change that if you want)
Java
// main methodpublic class GFG { // main driver method public static void main(String[] args) { // create an object of LinkedStack LinkedStack<Double> ls = new LinkedStack<>(); Scanner sc = new Scanner(System.in); do { // As we are writing a menu driven program so // user can choose the operation he wants System.out.println("-----MENU-----"); System.out.print( "1.push\n2.pop\n3.peek\n4.display\n5.size\n6.exit\n"); System.out.println("Enter your choice:"); int choice = sc.nextInt(); switch (choice) { case 1: System.out.println("Enter the element to push :"); Double ele = sc.nextDouble(); ls.push(ele); break; case 2: System.out.print("Poped element: "); System.out.println(ls.pop()); break; case 3: System.out.println("topmost element :"); System.out.println(ls.peek()); break; case 4: ls.display(); break; case 5: System.out.println("Total elements on stack: "+ ls.size()); break; case 6: System.exit(1); default: System.out.println("Invalid choice!!"); } } while (true); }} |
We can also include an interface in our code that has the abstract methods and it should be placed in its own file and the class should include the keyword ‘implements’ in order to implement the methods of it.
Here is an example interface for the above example:
Java
public interface IStack<T> { // This Interface has the abstract methods // to be implemented by the LinkedStack // checks whether Stack is empty or not boolean isEmpty(); // inserts an element onto the stack void push(T ele); // deletes and returns the beginning element on // the stack T pop(); // returns the beginning element of the stack T peek(); // returns the no.of elements present on stack int size();} |
