To ace your coding interview for a software engineering job, you’ll need to understand stacks and queues. They come up frequently in coding interviews and are fundamental to many other data structures too.
Let’s take a look at some typical stacks and queues questions.
5 typical stacks and queues interview questions
- Given a string of round, curly, and square opening and closing brackets, return whether the brackets are balanced (well-formed).
- Given an integer array "nums" and an integer "k," return the length of the shortest non-empty subarray of "nums" with a sum of at least "k."
- Evaluate the value of an arithmetic expression in Reverse Polish Notation.
- Implement a max stack.
- Design your implementation of the circular queue.
Below, we take a look at some more questions and provide you with links to high quality solutions to them. We explain how stacks and queues work, their variations, and the most important things you need to know about them, including a useful "cheat sheet" to remind you of the key points at a glance.
This is an overview of what we’ll cover:
Easy stacks and queues interview questions
- Medium stacks and queues interview questions
- Hard stacks and queues interview questions
- Stacks and queues basics
- Stacks and queues cheat sheet
- Mock interviews for software engineers
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of stacks and queues.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solutions, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the "phone screen" stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
1.1 Valid parenthesis
1.2 Min stack
1.3 Implement stack using queues
1.4 Implement queue using stacks
1.5 Next greater element I
1.6 Backspace string compare
1.7 Remove all adjacent duplicates in string
1.8 Build an array with stack operations
1.9 Final prices with a special discount in a shop
1.10 Number of recent calls
Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
2.1 Simplify path
2.2 Evaluate reverse polish notation
2.3 Basic calculator II
2.4 Remove duplicate letters
2.5 Flatten nested list iterator
2.6 Decode string
2.7 Remove K digits
2.8 Add two numbers II
2.9 Generate parentheses
2.10 132 pattern
2.11 Next greater element II
2.12 Score of parentheses
- Text guide (Dev.to/Seanpgallivan)
- Text guide (LeetCode)
- Video guide (Nick White)
- Code example (LeetCode)
2.13 Exclusive time of functions
2.14 Asteroid collision
- Text guide (Petamind)
- Text guide (LeetCode)
- Video guide (Kevin Naughton Jr.)
- Code example (LeetCode)
2.15 Daily temperatures
- Text guide (Medium/Greynut)
- Video guide (Alexander Le)
- Video guide (NeetCode)
- Code example (LeetCode)
2.16 Online stock span
- Text guide (Medium/Tanu)
- Video guide (Timothy H Chang)
- Video guide (TECH DOSE)
- Code example (LeetCode)
2.17 Sum of subarray minimums
2.18 Validate stack sequences
2.19 Maximum width ramp
2.20 Next greater node in linked list
2.21 Smallest subsequence of distinct characters
2.22 Minimum cost tree from leaf values
2.23 Reverse substrings between each pair of parentheses
2.24 Remove all adjacent duplicates in string II
2.25 Design circular queue
2.26 Reveal cards in increasing order
2.27 Design front middle back queue
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
3.1 Longest valid parentheses
3.2 Trapping rain water
3.3 Largest rectangle in histogram
3.4 Maximal rectangle
3.5 Basic calculator
3.6 Maximum frequency stack
3.7 Odd even jump
3.8 Constrained subsequence sum
3.9 Sliding window maximum
3.10 Find the most competitive subsequence
3.11 Number of visible people in a queue
3.12 Shortest subarray with sum at least K
3.13 Stamping the sequence
In order to crack the questions above and others like them, you’ll need to have a strong understanding of stacks and queues and how they work. Let’s get into it.
4.1 What are stacks and queues?
Stacks and queues are similar and complementary in many ways. Both are a sequenced collection of elements that are generally accessed one element at time, and are implemented using similar data structures.
Stacks are Last in First Out (LIFO) constructs. Queues are the opposite, being First In First Out (FIFO) constructs. These characteristics are what give these structures their name. A stack is analogous to a stack of physical objects, for example a stack of plates or chairs. The last plate or chair added to the stack is usually the first one removed when an item is needed. Similarly for a queue, the first person to enter a queue is usually the first person served.
There are two main operations on stacks and queues. These are adding a new element, and accessing the next logical element.
For a stack, these two operations are known as “push” and “pop.” “Push” adds a new element to the top of the stack. “Pop” returns the last element added to the stack, and removes it from the stack.
A queue’s two operations are known as “enqueue” and “dequeue”. “Enqueue” adds a new element to the end of the queue. “Dequeue” returns the oldest element in the queue, and removes it from the queue.
Stacks and queues often have a third operation defined called “peek”. This operation returns the next logical element, but does not remove it from the stack or queue.
Although stacks and queues have no fixed capacity in theory, in practice, resource bounds make it so that that they do. Adding an element to a stack when it has no more space is known as a “stack overflow” error. Trying to pop an element from an empty stack is called a “stack underflow” error. Similarly for queues, these errors are known as “queue overflow” and “queue underflow”.
4.1.1 Types of stacks and queues (Java, Python, C++)
In Java, a Stack class is available, which extends the Vector class. C++ has many containers in the STL that expose push and pop operations. It also has Stack and Queue templates which wrap underlying vectors or lists to provide stricter stack and queue interfaces. Python has a deque class, or double ended queue, which allows pushing and popping from the front or the back, allowing it to be used as a stack or a queue.
4.1.2 How stacks and queues store data
Stacks and queues are defined by their interface and functionality, not by their implementations. Stacks and queues are often implemented using arrays or, more commonly, linked lists.
A straightforward implementation of a stack can be done with an array. Elements are pushed by adding them to the first unoccupied position of the array. The pop operation is accomplished by returning and removing the element at the last occupied position of the array. A variable is maintained indicating the last occupied position in the array, so that elements can be pushed and popped at the correct position.
Linked list implementations for stacks and queues can also be straightforward. For a stack, elements are pushed and popped from the tail of the linked list. For a queue, elements are enqueued at the tail, and dequeued from the head. For both implementations, maintaining a variable pointing to the head and the tail of the linked list makes the standard stack and queue operations possible in constant time.
4.1.3 How stacks and queues compare to other data structures
Stacks and queues are often mentioned with arrays and linked lists, as these are commonly used to implement them. Deques, or double ended queues, are also a variant that can be used as both a stack and a queue.
You can download the cheat sheet here.
5.1 Related algorithms and techniques
5.2 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity (the processing time for various stack and queue operations) and algorithm complexity (the amount of time and space used for common algorithms).
For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.
5.2.1 Time complexity
Queues and stacks are simple in terms of time complexity. All defined operations are possible in constant time. This is because push/enqueue and pop/dequeue operations are adding or removing elements from the ends of a linked list. These are operations that linked lists are very efficient at.
Finding a particular element in a stack or queue is dependent on the underlying implementation, with most cases requiring linear time. Often searching within a queue or stack is not a function provided on implementations.
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only stacks and queues, but also the rest of the relevant data structures. Check out our guides for questions, explanations and helpful cheat sheets.
Once you’re confident on all the topics, you’ll want to start practicing answering coding questions in an interview situation. One way of doing this is by practicing out loud, which is a very underrated way of preparing. However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.