Consider a table with a stack of plates. After the first one is placed on the table, the next one is placed on top of it; the third one is placed on top of the second, and so on, until the desired number is reached. To take the dishes off the table one by one, start with the last one placed on top; then move on to the last-but-one; then the one next to the top; and so on. As a result, the last dish to be added to the pile is the first to be removed. This way, all the plates are removed in the order of last-in-first-out. LIFO stands for Last-In-First-Out order.
Elements are added to the top of the stack similarly, and they can be seen or removed from the top similarly. From the middle of the stack, no element can be retrieved, removed, or added.
A stack is a fundamental data structure. They are employed in a variety of situations. The undo feature in text editors is one example. A stack is used to keep track of all the modifications. When you undo something, the most recent action is displayed. It pushes modifications onto the stack when you make changes.
You’ve probably noticed the browser’s Back and Forward buttons as well. Stacks are used in these as well.In Java, a stack is a LIFO data structure. A structure like this keeps things of the same type together.
The element at the top is the one with the first index. At least three of the following techniques should be present in a stack:
- push: This method pushes a new element to the top of the stack.
- pop: This method removes the element at the top of the stack.
- peek: This reads out the element at the top without deleting it.
The stack class in Java is found in the java.util.* package, which you must import. Further, the stack in Java has one constructor and five methods, which are all described below:
Creation of a Java Stack
The Stack Class in the Java collections framework implements the Stack Data structure’s features. The Stack class is an extension of the Vector class.
We must first import the java.util.Stack package. This package includes stack DataStructure, which allows us to build a stack, enter data into it, and use all of the stack’s other features.
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>import java.util.Stack;</pre> </div>
Let’s have a look at how we make a stack. The general syntax for declaring the stack is listed below. Stack is the DataType, much as int is the DataType for an Integer variable. The variable’s name is Stack. The object can be an integer, a string, a character, a float, or anything else. Only one type of data can be stored in the stack. Text, numbers, and other data are not stored on the same stack. When storing integers, we use the Integer data type, and when storing text, we use the String data type. The constructor of an empty stack has the following syntax:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>public Stack()</pre> </div>
The statement below creates an empty stack named newStack:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>Stack<String> newStack = new Stack<String>();</pre> </div>
Java Stack Methods
The following are common methods in Java’s Stack.
public E push(E item)
It adds a new item to the stack’s top. The illustration is as follows:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>Stack<String> compStack = new Stack<String>();
compStack.push('Apple'); compStack.push('IBM'); compStack.push('DELL'); compStack.push('Lenovo'); compStack.push('Chrome Book');
</pre>
</div>
public E pop()
It returns the item at the top of the stack after removing it. The subsequent section shows the illustration:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>Stack<String> compStack = new Stack<String>();
compStack.push('Apple'); compStack.push('IBM'); compStack.push('DELL'); compStack.push('Lenovo'); compStack.push('Chrome Book');
String strOne = compStack.pop();
String strTwo = compStack.pop();
String strThree = compStack.pop();
String strFour = compStack.pop();
String strFive = compStack.pop();
System.out.println(strOne);
System.out.println (strTwo);
System.out.println (strThree);
System.out.println (strFour);
System.out.println (strFive);
System.out.println();</pre>
</div>
Items are taken out in the reverse order that they were pushed in.
public E peek()
It replicates the item at the top of the stack without deleting it and returns it. Below is the illustration:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>Stack<String> compStack = new Stack<String>();
compStack.push('Apple'); compStack.push('IBM'); compStack.push('DELL'); compStack.push('Lenovo'); compStack.push('Chrome Book');
String strOne = compStack.peek();
String strTwo = compStack.peek ();
String strThree = compStack.peek ();
String strFour = compStack.peek ();
String strFive = compStack.peek ();
System.out.println(strOne);
System.out.println (strTwo);
System.out.println (strThree);
System.out.println(strFour);
System.out.println(strFive);
System.out.println();</pre>
</div>
It also means that peek copies the top element rather than removing it ().
public boolean empty()
If the stack is empty, this returns true; otherwise, it returns false. Here is the illustration:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>Stack<String> compStack = new Stack<String>();
compStack.push('Apple'); compStack.push('IBM'); compStack.push('DELL'); compStack.push('Lenovo'); compStack.push('Chrome Book');
boolean boolVal = compStack.empty();
System.out.println(boolVal);</pre>
</div>
The output is false because the stack, compStack, is not empty.
public int search(Object o)
It gives you the index of the object you’re looking for. If the object cannot be discovered, the result is -1. Here’s the illustration:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>Stack<String> compStack = new Stack<String>();
compStack.push('Apple'); compStack.push('IBM'); compStack.push('DELL'); compStack.push('Lenovo'); compStack.push('Chrome Book');
String strOne = compStack.search('Apple');
String strTwo = compStack.search('IBM');
String strThree = compStack.search('DELL');
String strFour = compStack.search('Lenovo');
String strFive = compStack.search('Chrome Book');
System.out.println(strOne);
System.out.println (strTwo);
System.out.println (strThree);
System.out.println(strFour);
System.out.println(strFive);
System.out.println();</pre>
</div>
Stack implementation using a LinkedList in Java
- We design a LinkedList class and specify the head node in a LinkedList-based implementation. In addition, we set the head node to null and stack size to 0 in the constructor procedure.
- If the head node is null and pop() or peek() are used, an Exception is thrown since the stack is empty.
- Because we’re using LinkedList, there’s no limit to the size of Stack.
- oldHead saves the value of the head node when an element is pushed into a stack. A new element is added at the head node, and its next is set to oldHead. As a result, we append elements to LinkedList’s front.
- The value of the head node is stored in a temporary variable while removing an element.
- The head node property is set to true. The function then returns a value that is previously stored.
- The headNode value is returned by the peek() method. The size() and empty() methods retrun stackSize and verify if stackSize is 0, respectively.
- The time complexity of Stack implementations based on Array and LinkedList.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.*;
public class CodeStackLinkedList {
private Node head; // the node at the beginning
private int lengthOfStack;
// this is a nested class responsible for defining a node in a linkedlist
private class CodeNode {
int value;
Node next;
}
public CodeStackLinkedList() {
headNode = null;
lengthOfStack = 0;
}
// To demonstrate stack behavior, remove the value from the beginning of the list.
public int pop() throws Exception {
if (head == null) {
throw new EmptyStackException();
}
int value = head.value;
head = head.next;
lengthOfStack--;
return value;
}
// To demonstrate stack behavior, add a value to the beginning of the list.
public void push(int value) {
Node oldHead = head;
head = new CodeNode();
head.value = value;
head.next = oldHead;
lengthOfStack++;
}
public int peek() throws Exception {
if ( head == null) throw new EmptyStackException();
else return head.value;
}
public int size() {
return lengthOfStack;
}
public boolean empty() {
return lengthOfStack == 0;
}
public static void main(String args[]) throws Exception {
LinkedListStack numStackList = new LinkedListStack();
numStackList.push(33);
numStackList.push(17);
numStackList.push(3); /
System.out.println("The value at the top is :" + numStackList.peek());
System.out.println("The removed Element is : " + numStackList.pop());
System.out.println("Stack's size is : " + numStackList.size());
System.out.println("The removed Element is: " + numStackList.pop());
System.out.println("The value at the top is : " + numStackList.peek());
numStackList.push(37);
System.out.println("Stack is empty : " + numStackList.empty());
}
}</pre>
</div>
How to use Stack in a variety of ways In Java
Using Stack to Reverse an Array or a String
First, all of the Elements are pushed onto the stack, then popped. The result is a reversal of the sequence.
Finding HTML Tags and Parentheses that Match
The parenthesis that open are pushed to the top of the stack. When we come across a closing parenthesis, we remove the starting parenthesis from the stack.
Use of stacks in recursion
The process through which a function calls itself is known as recursion. The stack data structure is quite handy. For recursive function calls, it is commonly used in computer science.
Conversions in Binary Tree Traversals
Binary Tree Transversals use Preorder, Postorder, and Inorder.
Introduction to the Queue
Consider a long line of people waiting for a product or service. The first person to arrive first is served. Further, the next person to be served is the second. Finally, the third will be served, and so on, until the line is cleared. It is known as a FIFO (first-in-first-out) strategy.
In Java, a queue is a FIFO data structure. A structure like this keeps things of the same type together. The topmost element is the one with the first index. At the very least, a queue should include the following three methods:
- enqueue: This adds a new element to the queue’s back.
- dequeue: Removes the element from the top of the queue.
- peek: This reads aloud the initial element without deleting it.
The queue has no constructor in Java, but it does have six methods, three of which are explained below:
Implementation/Instantiation of a Java Queue
In Java, the Queue is an interface. The Java Stack class creates a stack object, but the Java Queue Interface class creates a class. The class still needs to be instantiated into an object. Many classes from the Queue Interface have already been implemented in Java. Among the options, the programmer should select the one that is most appropriate for him. LinkedList has been chosen for this article. There are two constructors for LinkedList, but only one is discussed here. There are numerous LinkedList class methods, but only three are discussed here.
The LinkedList class in Java is found in the java.util.* package, which you must import. The following is a syntax for creating a queue using the LinkedList class:
public LinkedList()
The sentence that follows creates an empty queue called ldList:
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>LinkedList<String> ldList = new LinkedList<String>(); // Some Methods of LinkedList Queue</pre> </div>
public boolean add(E e)
It adds a new item to the queue’s back end. The illustration is as follows:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>LinkedList<String> compList = new LinkedList<String>();
compList.add('Apple');
compList.add('Amazon');
compList.add('Microsoft');
compList.add('Toshiba');
compList.add('Uber');</pre>
</div>
public E remove()
It returns the item that was previously in front of the queue. The code snippet below demonstrates how to use the remove() method.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>LinkedList<String> compList = new LinkedList<String>();
compList.add('Apple');
compList.add('Amazon');
compList.add('Microsoft');
compList.add('Toshiba');
compList.add('Uber');
String strOne = compList.remove();
String strTwo = compList.remove();
String strThree = compList.remove();
String strFour = compList.remove();
String strFive = compList.remove();
System.out.println(strOne);
System.out.println (strTwo);
System.out.println (strThree);
System.out.println(strFour);
System.out.println(strFive);
System.out.println();</pre>
</div>
Validating that the data structure is FIFO.
public E peek()
It replicates the item at the front of the queue without removing it and returns it. Here’s the demo:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>LinkedList<String> compList = new LinkedList<String>();
compList.add('Apple');
compList.add('Amazon');
compList.add('Microsoft');
compList.add('Toshiba');
compList.add('Uber');
String strOne = compList.peek();
String strTwo = compList.peek();
String strThree = compList.peek();
String strFour = compList.peek();
String strFive = compList.peek();
System.out.println(strOne);
System.out.println (strTwo);
System.out.println (strThree);
System.out.println(strFour);
System.out.println(strFive);
System.out.println();</pre>
</div>
It also means that peek copies the front element rather than removing it ().
Conclusion
Data structures such as the stack and queue exist. The fundamental data structures in the Java Collections Framework are Stack and Queue. They are used to store and retrieve the same type of data in a specified order. Both the Stack and the Queue are Linear Data Structures.
In Java, the stack is a data structure that works on the last-in, first-out principle. push(), pop(), and peek() are the most common among the five techniques available. Additionally, a queue is a data structure that works on the first-in, first-out principle. It also has several methods, including add(), remove(), and peek().
