Friday, 21 July 2017

Difference between Stack and Queue Data Structure in Java

Stack and Queue are two of important data structures in the programming world and have a variety of usage. As opposed to the array and linked list, which are considered as a primary data structure, they are a secondary data structure which can build using an array or linked list. You can use Stack to solve recursive problems and Queue can be used for ordered processing. The difference between Stack and Queue Data structure is also one of the common questions not only in Java interviews but also on C, C++, and other programming job interviews. Well, main difference comes the way these data structures are used, Stack is LIFO (last In First Out) data structure, which means the item which is inserted last is retrieved first, similar to a stack of plates in a dinner party, where every guest pick up the plate from the top of stack.

On the other hand Queue data structure literally represent a queue, which is a FIFO (First In First Out) data structure, i.e. object which is first inserted, is first consumed, because insertion and consumption happen at opposite end of the queue.

When the difference between Stack and Queue is asked in Java Interviews, the interviewer also expects you to be familiar with the Stack and Queue classes from Java Collection Framework. Java supports both these data structure and provides a sample implementation of them, by the way, you should also be familiar with implementing Stack and Queue in Java using an array and linked list, which is another good code related questions in programming job interview.

Stack vs Queue in Java

In this article, we will compare Stack vs Queue based upon their differences in behavior and how they are implemented and used in Java programming language. In one word, the difference between Stack and Queue comes in how they consume elements, In Stack, we remove the most recently added element, while in Queue we remove least recently added element.

Before seeing some more differences between Stack and Queue data structure, let's see some similarity between them, this will help to understand their differences better.

1) Both Stack and Queue are built on top of basic data structure like an array or linked list. Since both Stack and Queue can be bounded and unbounded, it makes sense to use an array for bounded stack and queue and may be linked list (it suits problem domain) for an unbounded queue.

2) The Java Collection API contains an implementation of both stack and queue data structure. It has a class called java.util.Stack which represents Stack and then it has a Queue interface, with a couple of implementation e.g. BlockingQueue, LinkedList, and PriorityQueue.
Now let's see differences between Stack and Queue data structure in Java:

1) The first and major difference between Stack and Queue data structure is that Stack is LIFO(Last In First Out) data structure while Queue is FIFO (First In First out) data structure. So if you have a requirement where elements are processed in the order they are generated or put into Queue, you should use a Queue implementation, which supports FIFO ordering, but if you need to work with the most recently added entry, Stack would be the right data structure.

Stack, Data Structure in Java, Oracle Java Tutorials and Certifications

2) Key operation supported by any Stack implementation are push() and pop() which is used to add and retrieve an element from Stack, worth noting is that pop() not only retrieves element but also removes it from Stack. The key operation for Queue data structure in Java is offer() and poll(), which is used to add an object into Queue and retrieve an object from the head of Queue.

Though Queue also supports add(Object o)and remove(Object o) operation, inherited from Collection, there is the difference between them. Collection method throws Exception, while Queue methods return special values e.g. null, in exceptional cases.

For example offer() return false, if it's not able to insert an element into Queue, while add() throws a RuntimeException when it fails to add an element into Queue. Similarly poll() returns null if the queue is empty, while remove method throws an unchecked exception. Since null is used as a special value, it's worth noting that Queue implementation generally doesn't allow null, but LinkedList is an exception, which does allow nulls.

3) Elements or Objects are added at the top of the Stack, but they are enquired at the different end, head and tail, in the case of a queue. Adding an element into Queue is also referred as enqueue operation and removing an element are referred as dequeue operation. Head and tail of Queue are also referred as front and rear of the queue. insertion take place at the rear end, while deletion takes place at opposite end e.g. front end. You can also read a good book on data structure and algorithms e.g. Introduction to Algorithms to learn more about different data structures and algorithms.

4) The Stack data structure is a natural recursive data structure and suits well for recursive problems e.g. implementing pre-order, post-order, and in-order traversal of the binary tree, while Queue is a sequential data structure and can be used to provide ordering in processing. One example of this is a producer-consumer pattern, where a shared queue is used for data exchange between producer and consumer threads.

5) An example of using Stack data structure is reversing a String in Java, you can reverse a String by simply putting each character from String into Stack and once you finished, start popping them up. Since Stack is LIFO data structure, you will retrieve letters in reverse order.

A good example of Queue is a producer-consumer problem, in which producer produces and consumer consumes the item. This problem also helps to understand BlockingQueue, which is a relatively new concurrent utility, which can simplify producer-consumer designs in concurrent programs. 

As someone has rightly said that a picture is worth of 1000 words, here are two diagram which helps you understand difference between Stack and Queue more clearly

Stack, Data Structure in Java, Oracle Java Tutorials and Certifications

That's all on the difference between Stack and Queue data structure in Java. By the way, don't confuse between Stack and Heap memory with Stack and Queue, in that post, we have compared different memories in Java platform, and here our focus on different data structure and collection class. Though Stack is commonly used to store method invocation and local variable data, in terms of memory it just a different area.