Topic 06 of 15
Stacks & Queues
A pile of plates and a lunch line.
A stack is a pile of plates: you put plates on top and take them from the top. A queue is a lunch line: you join at the back and leave from the front. Matching brackets, undo buttons, and "the next bigger number" all come from these two.
What you will be able to do
Bracket matchingMonotonic stackQueue and deque windowsStack from queues and backExpression evaluation
0/38
Meet the stack and the queue
01 / 04
Push 1, 2, 3 onto the stack. 3 is on top.
- looking now
- just added
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Implement Stack from ScratchBuild a pile of plates where you can only add or take the plate on top, using a plain array or a chain of boxes.Stack design
- 02Implement Queue from ScratchBuild a fair waiting line where people join at the back and leave from the front, without anyone having to shuffle forward.Queue design
- 03Implement 2 stack in an arrayTwo kids share one long shelf for their toy piles, one starting from each end, so no space is wasted until the piles meet.Two pointers from both ends
- 04Find the middle element of a stackKeep a pile of books where you can always point at the middle book right away, even while books are added and taken off the top.Doubly linked list with a middle pointer
- 05Implement N stacks in an ArrayLet many piles share one row of lockers, where any pile can take any empty locker and every locker remembers which one is under it.Free list inside an array
- 06Check the expression has valid or Balanced parenthesis or notCheck that every opened box in a row of brackets gets closed by the right lid, and in the right order.Stack matching
- 07Reverse a String using StackWrite a word backwards by stacking its letters like blocks and then taking them off from the top.Stack reversal
- 08Design a Stack that supports getMin() in O(1) time and O(1) extra spaceKeep a pile of numbers that can tell you its smallest number instantly, by hiding the old smallest number inside a special note on the pile.Stack with an encoded minimum
- 09Find the next Greater elementFor every kid in a line, find the first taller kid standing to their right.Monotonic stack
- 10The celebrity ProblemAt a party, find the one guest everybody knows who knows nobody, by asking as few questions as possible.Elimination with a stack
- 11Arithmetic Expression evaluationWork out a math sentence like 3+2*(4-1)-5 the way a calculator does, doing brackets first and times before plus.Two stacks for operators and numbers
- 12Evaluation of Postfix expressionWork out a math sentence where each sign comes after its two numbers, by keeping the numbers in a pile and combining the top two whenever a sign shows up.Stack evaluation
- 13Implement a method to insert an element at its bottom without using any other data structureSlide a new block under a tower of blocks, using only your hands and your memory, with no second table to put blocks on.Recursion as a hidden stack
- 14Reverse a stack using recursionFlip a pile of plates upside down using only the pile itself, by taking plates off and sliding each one back in at the bottom.Recursion as a hidden stack
- 15Sort a Stack using recursionSort a pile of numbered blocks so the biggest is on top, using only the pile and helpers who can each hold one block.Recursion as a hidden stack
- 16Merge Overlapping IntervalsSquash a messy list of meeting times into the fewest blocks, joining any meetings that touch or overlap.Greedy by sorting
- 17Largest rectangular Area in HistogramFind the biggest rectangle of floor tiles you can lay flat across a row of towers of different heights.Monotonic stack
- 18Length of the Longest Valid SubstringFind the longest unbroken stretch of brackets where every open bracket gets a matching close bracket.Stack of indices
- 19Expression contains redundant bracket or notFind out if a math sentence has a pair of brackets that wraps nothing useful, like (c) or a second pair around ((a+b)).Stack matching
- 20Implement Stack using QueueMake a fair waiting line behave like a pile of plates, by sending older people to the back every time someone new arrives.Stack and queue design
- 21Implement Stack using DequeBuild a pile of plates out of a tube that opens at both ends, by only ever using one of the ends.Stack and queue design
- 22Stack Permutations (Check if an array is stack permutation of other)Train cars enter a side track one by one; check if they can leave in a given order.Stack simulation
- 23Implement Queue using StackMake a fair first come, first served line using only two piles, by pouring one pile into the other only when you need to.Two stacks, lazy transfer
- 24Implement n queue in an arrayLet several waiting lines share one row of seats, where any line can take any empty seat and each seat remembers who sits behind it.Free list inside an array
- 25Implement a Circular queueMake a waiting line in a fixed row of seats that bends around like a merry-go-round, so seats freed at the front get used again at the back.Circular array with modulo
- 26LRU Cache ImplementationBuild a small toy shelf that remembers which toy you played with least recently and throws that one out when the shelf is full.Hash map plus doubly linked list
- 27Reverse a Queue using recursionTurn a waiting line around using only "leave from the front" and "join at the back", with each helper holding one person until the rest are turned around.Recursion as a hidden stack
- 28Reverse the first K elements of a queueTurn around only the first few kids in a waiting line and keep everyone else where they were.Stack plus queue rotation
- 29Interleave the first half of the queue with second halfShuffle a line of kids like a deck of cards: one from the first half, one from the second half, again and again.Queue rotation
- 30Find the first circular tour that visits all Petrol PumpsFind the first gas station on a round road where a car can start with an empty tank and drive all the way around without running dry.Greedy with a running sum
- 31Minimum time required to rot all orangesFind how many minutes it takes for rot to spread from the bad oranges to every good orange in a crate, or say it never will.Breadth first search with a queue
- 32Distance of nearest cell having 1 in a binary matrixFor every square on a grid, find how many steps it is to the nearest square marked 1, by letting all the 1s spread out at the same time like ripples.Multi-source breadth first search
- 33First negative integer in every window of size kSlide a frame of size k along a row of numbers and, for every position, name the first negative number inside the frame.Sliding window with a queue
- 34Check if all levels of two trees are anagrams or notWalk two family trees row by row at the same time and check that each pair of rows has the same names, in any order.Breadth first search with a queue
- 35Sum of minimum and maximum elements of all subarrays of size kSlide a window of k boxes along a row of numbers and add up the biggest plus the smallest number seen in every window.Monotonic deque
- 36Minimum sum of squares of character counts in a given string after removing k charactersRemove k letters from a word so that no letter is left with a big pile, by always shaving the tallest pile.Heap of counts
- 37Queue based approach or first non-repeating character in a streamAs letters arrive one by one, say which letter so far has shown up only once and arrived the earliest.Queue plus counting
- 38Next Smaller ElementFor every kid in a line, find the first shorter kid standing to their right.Monotonic stack