Introduction to Stack in Java A stack is a collection of objects that are inserted and removed in a LIFO(Last In First Out) fashion. The name “stack” is derived from a stack of plates. So, when we need a plate, we take (pop) from the top of the stack, and when we want to add a plate, we put (push) it at the top as well. We cannot add or remove a plate at the middle of the stack.
Likely, elements can be added to the stack at the top, and they can be seen or removed from the top. No element can be retrieved, removed, or added from the middle of the stack.
Stack is a fundamental data structure. They are used in many applications. One such application is the undo mechanism in text editors. All the changes are stored in a stack. When you undo something, it pops the most recent action. When you make changes, it pushes changes onto the stack.
You must have also observed the Back and Forward buttons on browsers . These operations are also performed using stacks.
We can perform various operations on stack other than push() and pop() . We can see the topmost element in the stack using peek() ; we can know the size of the stack using the size() method. Also we can check if the stack is empty using the empty() method.
How to Implement Stacks in Java? The Java collections framework has a Stack Class that provides the functionality of the Stack Data structure. The Stack class extends the Vector class.
Firstly we need to import java.util.Stack package. This package contains stack Data Structure, which will allow us to create a stack, insert data into it and use all the other functionalities of the stack.
Let us see how we create a stack. Mentioned below is the general syntax to declare the stack. Stack is the DataType like we use int for the Integer variable. **stacks** is the variable name.
The object can be Integer, String, Character, Float, etc. The stack can store only one type of data. It is not possible to store text, numbers, etc., in the same stack. If we want to store numbers, we use Integer datatype; similarly, if we want to store text we use String datatype.
To Initialize the stack we use <variable_name> = new Stack<>(); Now the stack is ready to use.
Example:
Methods in Stack Class
push(e): Adds element e to the top of the stack.
Example:
pop(): Removes and returns the top element from the stack. If the stack is empty, it throws an exception(EmptyStackException ).
Example:
peek(): Returns the top element of the stack without removing it. If the stack is empty, it throws an exception.
Example:
size(): Returns the number of elements in the stack.
Example:
empty(): Returns a Boolean indicating whether the stack is empty
Example:
Implementation of Stack Using Array in Java
We are implementing our own stack using class and methods. It will have the same functionality as we saw in the above examples. We name our class as ArrayStack as we are using Array to store our data.
E in Angular brackets (<>) makes our class Generic. It enables the user to use any data type. We can make a stack of String datatype, of Integer datatype, or Character datatype. It is not limited to only Integer.
We declare an array named data to store the values and topIndex to keep track of the top element.
There are two constructor methods , one with capacity customed by the user and the other default. Default Array capacity is 1000 for the stack where capacity is not mentioned. The topIndex is set to -1. We initialize the data array and topIndex in the constructor method.
The size() method returns the size of the stack i.e. topIndex+1.
The empty() method checks if the topIndex is at -1 which implies, the stack is empty.
The push() method first checks if the stack is full. If it is full it throws an Exception else it simply adds an element to the stack and increment the topIndex by 1.
The peek() method returns the topmost element in the stack i.e data[topIndex]. If the stack is empty, it throws EmptyStackException.
Identically, the pop() method also throws EmptyStackException if the stack is empty or removes the top element, returns its value, and decreases topIndex by 1.
So the Output would be
Likewise, Stack can also be implemented using LinkedList.
Implementation of Stack Using LinkedList in Java
In LinkedList-based implementation, we create a LinkedList class and declare the head node.
In the constructor method, we initialize headNode to null and stackSize to 0.
If headNode is null and pop() or peek() operations are performed then it throws an Exception , as the stack is empty. There is no restriction on the size of Stack as we are using LinkedList.
When an element is pushed into a stack, oldHead stores the value of headNode. The new element is added at headNode, and its next is set to oldHead. Thus, we add elements at the front of LinkedList.
While removing element , the value of headNode is stored in a temporary variable. headNode is set as headNode.next, and the stored value is returned by the function.
peek() method returns value of headNode. size() method retrun stackSize and empty() method checks if stackSize is zero respectively.
Time Complexity for Array and LinkedList based implementations of Stack.
Output:
STACK METHOD TIME COMPLEXITY push() O(1) pop() O(1) peek() O(1) size() O(1) empty() O(1)
Time complexity for the addition of elements in array at a particular index is O(1) as well as for creating a node and attaching it to a LinkedList is also O(1). Incrementing topIndex variable is also O(1).
Removing the node of LinkedList and decrementing the topIndex is done in O(1) time complexity. Whereas, in the case of ArrayStack we set the element at topIndex to be null and decrement the topIndex value, which is also performed in O(1) time.
peek() is nothing but the headNode.value in LinkedList and data[topIndex] in the array which can also be performed in O(1) time complexity.
In size() method there is only one arithmetic operation, so it is also performed in O(1) time and in the empty() method there's evaluation of a boolean expression. All of these take O(1) time only.
All the methods execute the constant number of statements. All the operations are performed on topIndex only thus, time complexity is O(1) for all methods.
Applications of Stack in Java
Reversing Array or String using Stack
All the Elements are first pushed onto the stack and then popped. The resulting sequence is reversed.
Matching Parentheses and HTML Tags
Opening parentheses are pushed in the stack. When we come across a closing parenthesis, we pop the opening one from the stack.
Stack is used in recursion
Recursion is the process in which a function calls itself. Stack is a very useful data structure. It is used widely in computer science for recursive function calls.
In Preorder, Postorder, Inorder conversions
Preorder, Postorder, and Inorder are used in Binary Tree Transversals.
Introduction of Java Queue You must have stood in a queue while submitting your assignments to your teacher or in a voting line. How does it work? The person standing first submits the assignment first and comes out of the queue.
Our Queue data structure in java also works in the same way. The element first entered in the queue is removed first as well. No element can be removed from the rear end or from the middle of the queue. Also, no element can be added at the front end or any other position, it has to be added only from the rear end. This is also known as the first-in, first-out (FIFO) principle.
A queue is a collection of objects that are inserted at the rear end of the list and are deleted from the front end of the list. We can also perform various other operations on Queue in Java. We can see the element at the front end, know the size of the queue and check if the queue is empty.
How to Implement Queue in Java? In Java, the Queue interface is present in **java.util** package and extends Collection Framework. Since Queue is an Interface, queue needs a concrete class for the declaration, such as LinkedList, PriorityQueue, etc.
Firstly, we will import the queue from Java Collections Framework. This will let us declare Queue.
Queue is a datatype. queue is the variable name of our queue. This declares the queue. The object is the datatype. All the elements in the Queue have to be of the same datatype. It can be Integer, Float, String, Character, etc.
<variable_name> = new LinkedListQueue(); initializes queue. Now we can use the queue to store, retrieve and manipulate the data.
For example:
Here Character DataType is used. String, Integer, Double, etc., can also be used.
Methods of Queue in Java
Our Queue ADT Interface java.util.Queue Interface java.util.Queue throws exceptions returns special value enqueue() add(e) offer(e) dequeue() remove() poll() first() element() peek() size() size() size() isEmpty() isEmpty() isEmpty()
Note:
ADT stands for Abstract Data Type
Queue Interface in java.util.Queue has additional methods for enqueue() , dequeue() and first() . The methods in the second column throws Exceptions. add(e) throws exception if the Queue size if full and remove() and element() throws Exception if Queue is empty.
These additional methods also include methods that don't throw any exception in any case and just return null. These are offer(e) , poll() , peek() .
size() and empty() methods are same for all.
These methods are explained below:
enqueue(e): Adds element e to the back of the queue.
Example:
dequeue(): Removes and returns the first element from the queue. An Exception is thrown if Queue is empty.
Example:
first(): Returns the first element of the queue without removing it. An Exception is thrown if Queue is empty.
Example:
size(): Returns the number of elements in the queue.
Example:
isEmpty(): Returns a Boolean indicating whether the queue is empty.
Example:
Implementation of Queue Using Array in Java
Now, we will implement our own queue using an array by creating our own class and methods. In the code given below, we have implemented ArrayQueue as a generic class as well. Thus, our queue can support multiple data types.
We declared two variables frontNode and queueSize . We create two constructor methods the same as the stack, one with fixed capacity and another with user-defined capacity. We initialize frontNode and queueSize here.
frontIndex+queueSize gives us the index of the rear end.
enqueue() method first checks if the queue is full. If it is full then it throws an exception. If it has space, it adds the element at the rear end and increments the queueSize.
dequeue() method removes an element from the front end and decrements the queueSize. If the queue is empty it throws an Exception.
first() method returns the element at the frontIndex and if the queue is empty it also throws an exception.
As seen in the example though there's only one element in the queue it is not at index 0. Thus, taking (fronIndex+1)%data.length() in dequeue() and (frontIndex+queueSize) in enqueue() utilizes all the space of the array and then only it declares it to be full.
Output:
The queue can also be implemented using LinkedList.
Implementation of Queue using LinkedList in Java
In LinkedList-based implementation we create the LinkedListQueue class. We Declare frontNode, rearNode, and queueSize.
In the constructor method frontNode and rearNode are initialized to null and queueSize is initialized to 0.
If queueSize is 0 and dequeue() or first() operations are performed then it throws an Exception, as the queue is empty. There is no restriction on the size of the Queue as we are using LinkedList.
When an element is pushed into a Queue, oldRear stores the rearNode, and the new element is added to rearNode. Lastly, oldRear.next is set as rearNode. Thus, we add an element at the rear end in Queue.
While removing an element, the value of frontNode is stored in a temporary variable. frontNode is set as frontNode.next, and its value is returned by the function.
first() method returns value of frontNode. size() method returns queueSize and isEmpty() method checks if queueSize is zero respectively.
Output:
Time Complexities for Array and LinkedList Based Impelementations
Queue Method Time Complexity enqueue() O(1) dequeue() O(1) first() O(1) size() O(1) isEmpty() O(1)
Time complexity for the addition of elements in array at a particular index is O(1) and well as for creating a node, attaching a node in a LinkedList at the rear end is also O(1). Incrementing queueSize variable is also O(1).
Removing the node of LinkedList, setting it to null, and decrementing the queueSize is done in O(1) time complexity. Whereas, in the case of ArrayQueue we set the element at frontIndex to be null and decrement the queueSize which is also performed in O(1) time.
peek() is nothing but the front value in LinkedList and data[frontIndex] in the array which can also be performed in O(1) time complexity.
In size() there is only one arithmetic operation so it is also O(1) and in the empty() method, there's an evaluation of a boolean expression. All of these take O(1) time only.
All the methods run in O(1) time complexity as we are doing all the operations on front and rear only. And all the methods contain a fixed number of statements.
Types of Queues in Java
Circular Queue: In Circular Queue, the last position is connected back to the first position.
Input Restricted Queue: The input can be taken from the rear end only, and elements can be deleted from both ends.
Output Restricted Queue: The output can be taken from the front end only but elements can be inserted from both ends.
Doubly ended Queue: Elements can be inserted and removed from both ends i.e. front and rear.
Priority Queue: In a Priority Queue, a collection of elements are associated in a specific order.
Applications of Queue in Java
Operating Systems maintains a queue of processes, one that is ready to proceed and others that are waiting to be executed.
Priority Queues are used in scheduling the jobs in the operating system.
Difference Between Stack and Queue in Java
STACK QUEUE The stack is a linear data structure in which the insertion and deletion of elements are done by only one end. The Queue is a linear data structure in which insertion and deletion are done from two different ends i.e., rear and front ends, respectively. Stack has only one end name as TOP The queue has two ends name as REAR and FRONT . Stack follows LIFO principal Queue follows FIFO principal Stack is used for expression conversion and evaluation, handling recursive function calls, and checking the well-formedness of parenthesis. The queue is used for prioritizing jobs in operating systems, categorizing data, and for simulations.
Important Points to Remember About Stack and Queue in Java NOTE:
Stack is a Class whereas Queue is an Interface, thus queue requires a concrete class for declaration and initialization.
Queue data structure supports add() and remove operations inherited from Collection, but these throw exceptions, which is less user-friendly. Thus, Queue methods are used; they return special values, such as null, in exceptional cases.
Conclusion
Stack DataStructure follows the LIFO principle, whereas Queue DataStructure follows the FIFO principle.
All the operations of Stack and Queue are carried out in O(1) time complexity.
Stacks are used in recursive problems, binary tree transversals , etc.
Queues are used in operating Systems and sequential data transfer.
Free
