Sunday, May 7, 2023

Top 20 Stack and Queue Data Structure Interview Questions for 1 to 3 years Experienced

Both Stack and Queue are two of the crucial data structure which is very useful in solving a lot of problems. They are not as fundamental data structures as an array or linked lists but they offer some unique advantages in terms of how you store and access elements. Stack is commonly known as LIFO data structure because the last element you put is the first one to come out while Queue is known as FIFO data structure. The elements are retrieved from the queue in the order they were inserted. Both of these data structure has several usages and are used to solve many common problems and to implement algorithms. 

One of the main use of Stack is to convert a recursive algorithm into an iterative one because Stack logically represents the call stack that is used in recursion. This means you can also most of the recursive problems involving String, binary tree, etc using Stacks like preOrder, InOrder, and PostOrder traversal. 

Similarly, Queue is also used in many popular algorithms like level order search in a binary tree is implemented using Queue. There is also a Priority Queue data structure that allows you to retrieve elements based upon priority and you can use this to process jobs and elements on time or price priority. 

While JDK provides an implementation for both Stack and Queue data structure, there is a Stack class in java.util package and there is a Queue interface in the Java collection framework, its useful to know how to implement these data structures on your own as you may not be allowed to use Java implementation of Stack and Queue data structure during coding interviews.  

Implementing Data Structure in Java or your favorite programming language like C, C++, or JavaScript is also quite useful to improve your coding skill and I highly recommend all developers to code data structure on their own. 

I have shared a lot of coding problems in the past on my post about 100 data structure problems and 30 programming interview questions covering all kin of data structures and algorithms but in this article, I will cover only stack and queue data structure. You can solve these coding problems not only improve your understanding of stack and queue but also improve your coding and programming skills. 




1. Basic operations of Stack  Data Structure

You can implement a Stack data structure using an array or linked list but what matters most is that you should implement the basic operations like push, pop, peek, size, isEmpty, etc.

1. Push
This operation adds an element at the top of the stack. A top is a place where all stack operations take place.

2. Pop
This operation retrieves the top element after removing it from the stack.

3. isEmpty
This operation returns true if the stack is empty.

4. peek()
This operation returns the top element without removing it from the stack, also known as the top

5. size()
This operation returns the total number of elements in the stack.

One of the gotcha while implementing stack using array in Java is not removing the object reference from the array, which can cause memory leak, as explained in Effective Java. So, don't repeat that mistake, particularly in interviews. 




2. Basic operations of Queue

Similar to stack, Queue also has some basic options for adding, removing, and querying elements. These are known as enqueue, dequeue, and peek. Though there is no top, instead you have the front and rear end of the queue. elements are inserted at the end of the queue and removed from the front of the queue. 

1. Enqueue()
This operation adds an element at the end of the queue. It also increases the size by 1.

2. Dequeue()
This operation removes an element from the start of the queue and decreases the size by 1.

3. isEmpty()
This function returns true if the queue is empty like size==0

4. peek()
This function returns the first element of the queue without removing it, also known as the top()

5. size()
This operation returns the total number of elements in the stack.

You can implement Queue using both array and linked list in Java just try both of them. If you are stuck then I also suggest you go through one of these the best data structure and algorithms courses to revise key data structure concepts before interviews. 




20+ Stack and Queue Programming Interview Questions

Now that you know about Stack and Queue data structure, here are some of the frequently asked Coding interview questions based upon Stack and Queue data structure. You can practice these questions to check your understanding of these two data structures and further strengthen your knowledge. 

1. Difference between Stack and Queue Data Structure in Java? (answer)
hint - stack is a LIFO data structure which means items are removed in the reverse order of their insertion, while a Queue is a FIFO data structure which means items are removed in the same order of their insertion. 

2. How to implement Stack in Java using array? (solution)
I can't tell you much about this because it's pretty simple. All you need to write essential functions like push()pop()size() which operate on array. 

3. How to evaluate a postfix expression using a stack? (solution)
You need to write a program that will accept a string in postfix format and then return the result of that expression for the example given "24*" your program should return 8.

4. How to sort values in a stack? (solution)
Here, you need to write a program where you will be given a stack with unsorted order, you need to return a stack with elements in sorted order.

5. How to reverse the first k elements of a queue? (solution)

6. How to generate binary numbers from 1 to n using a queue? (solution)

7. How do you find the sum of two linked lists using Stack? (solution)
For example, if the given linked list are 1-2-3-4-5 and 6-7-8-9-10 then your program should return a linked list with nodes 7-9-11-13-15

8. How to check balanced parentheses in an expression? (solution)

9. How to implement a stack using a queue? (solution)

10. How to reverse a String using Stack? (solution)
For example, if a given String is "code" then your program should return "edoc".



11. How to check for balanced parentheses in an expression? (solution)

12. How to convert Infix to Postfix using Stack? (solution)
For example, if the given expression is ((A-(B/C))*((A/K)-L)) then your program should return *-A/BC-/AKL.

13. How to implement a queue using a stack? (solution)

14. Postfix to Prefix Conversion? (solution)
For example, if the given expression is "AB+CD-*" then your program should return it on prefix format like "*+AB-CD".

15. Prefix to Postfix Conversion? (solution)
For example, if the given expression is "*+AB-CD" then your program should print "AB+CD-*".

16. Prefix to Infix Conversion? (solution)
For example, if the given expression is *-A/BC-/AKL then your program should print ((A-(B/C))*((A/K)-L)).


17. Iterative PreOrder traversal using Stack? (solution)
hint - in pre-order traversal of a tree, the root is visited first, then left node, and finally the right node. That's why this is also called NLR (Root-Left-Right) traversal algorithm. Given a binary tree, you need to print all nodes in the pre-order. 

18. Iterative InOrder traversal using Stack? (solution)
hint - during in-order traversal, the left node is traversed first, then root, and finally the right node, hence this algorithm is also known as LNR (Left-Node-Right) order algorithm. Another interesting fact of in-order traversal is that in the case of the binary search tree, it prints all nodes in sorted order. 

19. Iterative PostOrder traversal using Stack? (solution)
Just in case you forgot what is post-order traversal, let me remind you that in a post-order traversal of a binary tree, the left node is traversed first, then the right node, and finally the root. It's also known as LRN (Left-Right-Node) order traversal. Again, you cannot use recursion. 

20. Reverse a number using a stack? (solution)
For example: if the given number is 12345 then your program should return 54321. You cannot use recursion

Top 10 Stack and Queue Data Structure Interview Questions



That's all about some of the frequently asked Stack and Queue Data Structure interview questions. Whether you are preparing for your next Programming interview or want to do well on your current job, learning Stack and Queue or say any other data structure will help you to write better programs. 

Always remember Data Structure + algorithms = Programs which means both data structure and algorithms are important for writing programs that are fast, robust, and can withstand tests of time. 


Other Resources for Coding Interviews:

Thanks for reading this article. If you like Stack and Queue Data Structure questions from Interviews then please share with your friends and colleagues. If you have any doubt or any other questions to add to this list feel free to drop a note. 

P. S. - If you need more practice, including dozens more problems and solutions for each pattern, check out these coding interview resources which not only help you to revise key concepts but also guide you on how to solve coding problems in real interviews.  

No comments :

Post a Comment