Newest first or oldest first
Type a, b and c in a text editor and press Undo three times. The editor takes back c, then b, then a: the newest change is undone first. Now send three documents a, b and c to a printer. They come out as a, b, c: the oldest job is printed first.
Both programs hold items that are waiting to be handled, and both received a, b and c in the same order. They differ in which waiting item they hand back next. The editor keeps its changes in a stack, and the printer keeps its jobs in a queue.
Definition
A stack removes the item that was added most recently. A queue removes the item that was added earliest.
A stack uses one end, called the top, like a stack of plates: a plate is put on the top and taken from the top, so the plate taken is the one put there last. Adding an item on top is a push and removing the top item is a pop. This order is called last in, first out, or LIFO.
A queue uses two ends, like the line at a shop's checkout. Items join at the back and leave from the front, so they leave in the order they arrived: first in, first out, or FIFO. Adding to a queue is also called enqueue, and removing from it dequeue.
Give a stack and a queue the same items
In the widget, push 1, 2 and 3 onto the stack, enqueue 1, 2 and 3 into the queue, and then remove everything from both. The stack's Removed row reads 3, 2, 1 and the queue's reads 1, 2, 3.
Which of the two a program needs depends on which waiting item has to be handled next. A stack fits when the item that arrived last must be finished first. Undo is one case. Function calls are another: when f calls g, g has to return before f can continue, which is why the record of running calls is named the call stack. A queue fits when items must be handled in the order they arrived, like the print jobs, or customers waiting in a line.
A stack and a queue in code
Python has no separate stack type, because a list already works as one. append adds an item at the end, pop() removes the last item and returns it, and stack[-1] reads the last item without removing it. The end of the list is the top of the stack.
A queue adds at one end and removes at the other, so one of the two operations has to work at the front of a list, where a list is slow. Calling pop(0) on a list does remove the oldest item, but a list stores its items side by side, so every item that remains then moves one place to the left.
For a queue, use collections.deque. A deque (short for double-ended queue, pronounced "deck", and a different word from dequeue) adds and removes items at both ends without moving the others. append adds at the back, popleft() removes from the front, and queue[0] reads the front item. A deque also has pop(), which removes from the back, and appendleft(), which adds at the front.
stack = []
stack.append(1) # [1]
stack.append(2) # [1, 2]
stack.append(3) # [1, 2, 3]
print(stack[-1]) # 3, the top; the stack is unchanged
print(stack.pop()) # 3 again, and now the stack is [1, 2]
queue = deque()
queue.append(1) # deque([1])
queue.append(2) # deque([1, 2])
queue.append(3) # deque([1, 2, 3])
print(queue[0]) # 1, the front; the queue is unchanged
print(queue.popleft()) # 1 again, and now the queue is deque([2, 3])
print(len(stack), len(queue))Each comment shows the stack or queue after its line has run.
An empty stack or queue has nothing to hand back, so removing from one stops the program with an IndexError. Code that may meet an empty stack tests it first: if stack: is true when the list holds at least one item, and the same test works on a deque.
Cost of stack and queue operations
- Push, pop and reading the top of a stack
- Only the top item is touched, however many items lie below it. A push costs more on the rare occasions when the stack's storage is full and its items are copied into a larger block, and over many pushes that cost averages out to per push.
- Adding at the back of a queue, removing at its front
- A deque records where its first item is and keeps free room at both ends. Removing at the front only advances that record to the next item, adding uses the free room, and no other item moves.
- Removing the first item of a Python list or a C++ `vector`
- Every remaining item moves one place to the left. Emptying items from the front moves items, then , and so on, which adds up to moves: 4,999,950,000 for 100,000 items.
Match brackets with a stack
The first job we give a stack is one a code editor does all the time: deciding whether the brackets in a piece of text pair up.
You get a string s made only of the characters (, ), [, ], { and }. Return true if every opening bracket is closed by a bracket of the same kind, the brackets close in the right order, and every closing bracket has an opening one before it. Otherwise return false.
Constraints
-
len(s)
Sample 1 · Input
s = "()"
Output
true
Sample 2 · Input
s = "()[]{}"Output
true
Sample 3 · Input
s = "(]"
Output
false
Sample 4 · Input
s = "([])"
Output
true
Sample 5 · Input
s = "([)]"
Output
false
The last two samples show what "the right order" means. ([]) is valid: the square pair opens and closes inside the round pair. ([)] is not, because the round pair closes while the square bracket inside it is still open.
Counting the brackets cannot tell these two apart, since each has one opener and one closer of both kinds. The check has to follow which opener each closer meets.
Read ([)] from left to right. After ( and [, two brackets are open, and the [ is inside the (. Then ) arrives. It cannot close the (, because that would leave the [ open across the end of the round pair. In general, a closer has to close the bracket that was opened most recently and is still open. The most recently added item is the one a stack hands back, so we keep the open brackets on a stack. We push every opener, and for every closer we look at the top, check that it is the same kind, and pop it.
Here is the check on ([]):
(is an opener, so it is pushed. The stack holds(.[is pushed on top of it. The stack holds(and[.]is a closer. The top is[, the same kind, so it is popped. The stack holds(.)is a closer. The top is(, the same kind, so it is popped. The stack is empty.
The string ends with nothing left open, so it is valid.
Step through the bracket check
The widget runs the same check one character at a time, on any string you type. Its first example is valid. The other three are the three ways a string can fail:
([)]: a closer finds an opener of the wrong kind on top of the stack.((): the string ends while an opener is still on the stack.)(: a closer arrives while the stack is empty.
The function has a test for each of the three:
def is_valid(s):
opener = {")": "(", "]": "[", "}": "{"}
waiting = []
for ch in s:
if ch in opener:
if not waiting or waiting[-1] != opener[ch]:
return False
waiting.pop()
else:
waiting.append(ch)
return not waiting
for s in ["()", "()[]{}", "(]", "([])", "([)]"]:
print(s, is_valid(s))Prints each of the five samples with its answer.
The dictionary opener gives, for each closer, the opener it needs, so ch in opener is true for the three closers and false for the three openers. The test not waiting comes first in the or, and Python skips the right side of an or once the left side is true, so waiting[-1] is never read on an empty stack. The last line handles a string that ends too early: it is valid only if no opener is still waiting.
Each character is either pushed or matched with one pop, so a string of characters takes at most stack operations, 10,000 for the longest input. The stack holds items at most, when every character is an opener.
Save unfinished work on the stack
In the bracket check, a stack entry only had to say which kind of bracket was open. In the next problem a [ also interrupts work in progress, the way a function call interrupts the function that makes it: whatever was being built before the [ is set aside, and picked up again when the matching ] arrives. The stack entry then holds whatever is needed to pick it up.
An encoded string uses k[text] to mean text repeated k times, and these can nest. Letters outside any brackets stay as they are. Given a valid encoded string s, return the decoded string.
Constraints
-
len(s) sholds lowercase letters, digits and square brackets- Every repeat count is between 1 and 300
Sample 1 · Input
s = "3[a]2[bc]"
Output
"aaabcbc"
Sample 2 · Input
s = "3[a2[c]]"
Output
"accaccacc"
Sample 3 · Input
s = "2[abc]3[cd]ef"
Output
"abcabccdcdcdef"
In the second sample, the inner piece 2[c] decodes to cc. The outer bracket therefore holds acc, and three copies of that give accaccacc.
We read the string from left to right with two variables: current, the text decoded so far at the nesting level we are in, and count, the number being read. A letter is added to the end of current. A digit extends the number: count becomes count * 10 plus the digit, so that reading 1 and then 0 in 10[a] gives . The two brackets do the rest:
- At
[, an inner piece begins. Before starting on it, we push a pair onto the stack: the text built so far, and the repeat count that was just read. Thencurrentstarts again from the empty string, to collect the inner piece, andcountgoes back to 0 for the next number. - At
], the inner piece is complete and sits incurrent. We pop the pair that was saved at its[, andcurrentbecomes the saved text followed by the inner piece repeated that many times.
The saved pairs belong on a stack for the same reason as the open brackets did. A ] always closes the most recent [ that is still open, and that [ pushed the pair now on top.
def decode_string(s):
saved = [] # (text before the bracket, repeat count)
current = ""
count = 0
for ch in s:
if ch.isdigit():
count = count * 10 + int(ch)
elif ch == "[":
saved.append((current, count))
current = ""
count = 0
elif ch == "]":
before, times = saved.pop()
current = before + current * times
else:
current += ch
return current
for s in ["3[a]2[bc]", "3[a2[c]]", "2[abc]3[cd]ef"]:
print(decode_string(s))Prints the three samples' answers.
Here is the second sample, 3[a2[c]], one character at a time. The stack is written with its bottom entry first.
| Character | What happens | saved after | current after |
|---|---|---|---|
3 | count becomes 3 | empty | "" |
[ | push ("", 3) and start again | ("", 3) | "" |
a | add the letter | ("", 3) | "a" |
2 | count becomes 2 | ("", 3) | "a" |
[ | push ("a", 2) and start again | ("", 3), ("a", 2) | "" |
c | add the letter | ("", 3), ("a", 2) | "c" |
] | pop ("a", 2): "a" then "c" twice | ("", 3) | "acc" |
] | pop ("", 3): "" then "acc" three times | empty | "accaccacc" |
Keep the minimum of a stack
Decode String stored a pair in every stack entry. The same idea answers a question that a plain stack cannot answer quickly: what is the smallest value on it right now?
Design a class MinStack with four methods: push(val) puts a value on top, pop() removes the top, top() returns the top value, and getMin() returns the smallest value currently on the stack. Each method must run in time. LeetCode creates the object and calls the methods in the order given, and the output lists what each call returns (null when it returns nothing).
Constraints
-
val pop,topandgetMinare only called on a non-empty stack- At most calls
Sample · Input
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
In the sample, the three pushes leave , 0 and on the stack, so getMin returns . The pop removes . After it the top is 0 and the minimum is .
The direct way is to look through the whole stack on every getMin. The problem allows 30,000 calls, and they can be 15,000 pushes followed by 15,000 calls of getMin, each of which reads 15,000 values:
That is about two seconds of work at operations a second, and the statement does not allow it in any case: it asks for time per call.
The next idea is a single variable that holds the smallest value pushed so far. It works until something is popped. Push 5 and then 2, and the variable holds 2. Now pop the 2. The stack holds only 5, but the variable still says 2, and nothing records what the minimum was before the 2 arrived.
So we record it. Next to every value we store the minimum of the stack as it was just after that value was pushed, which is the smallest of that value and everything below it. This stored minimum stays correct for as long as its entry is on the stack, because the entries below it cannot change while it is there: every push goes above it, and a pop can reach them only after removing it.
A push computes its minimum from the new value and the minimum stored in the entry just below; on an empty stack, the minimum is the new value itself. A pop removes a value together with its minimum, and the entry that becomes the top already holds the minimum of what is left.
class MinStack:
def __init__(self):
self.items = [] # (value, minimum of it and everything below)
def push(self, val):
low = val
if self.items:
low = min(val, self.items[-1][1])
self.items.append((val, low))
def pop(self):
self.items.pop()
def top(self):
return self.items[-1][0]
def getMin(self):
return self.items[-1][1]
s = MinStack()
s.push(-2)
s.push(0)
s.push(-3)
print(s.getMin())
s.pop()
print(s.top())
print(s.getMin())The lines after the class replay the sample.
On the sample, the three pushes store the pairs , and , and getMin reads from the top pair. After the pop the top pair is , which answers top with 0 and getMin with . Every method does a fixed amount of work, whatever the size of the stack.
Build a queue out of two stacks
A stack and a queue hand their items back in opposite orders, and yet a queue can be built from nothing but stacks, because reversing a list twice restores its order. Push 1, 2 and 3 onto a stack and pop them all, and they come out as 3, 2, 1. Push them onto a second stack in that order and pop again, and they come out as 1, 2, 3, the order a queue gives.
Design a class MyQueue that behaves like a queue, with push(x) to add at the back, pop() to remove and return the front, peek() to return the front, and empty() to say whether it holds nothing. Store items only in stacks, using only push to top, peek or pop from top, size and is-empty. The follow-up asks for amortized per operation.
Constraints
- At most 100 calls
popandpeekare only called on a non-empty queue
Sample · Input
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
In the sample, 1 and 2 are pushed. peek and pop both return 1, the oldest item, and the queue then still holds 2, so empty returns false.
The queue keeps two stacks. New items are pushed onto the first, inbox, and items are removed from the second, outbox. When an item is needed and outbox is empty, we first pour: we pop every item off inbox and push it onto outbox. The pour reverses the items, so the oldest one ends up on top of outbox.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pour(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self.pour()
return self.outbox.pop()
def peek(self):
self.pour()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1)
q.push(2)
print(q.peek(), q.pop(), q.empty())The last four lines replay the sample.
Pouring only when outbox is empty is what keeps the items in order. Everything in outbox arrived before everything in inbox, so while outbox holds anything, its top is the oldest item of the whole queue. Suppose we push 1 and 2 and pop once. The pour puts 1 on top of outbox, the pop returns it, and 2 stays in outbox. Now we push 3. A pour at this moment would put 3 on top of 2, and the next pop would return 3, although 2 has waited longer.
One call can be slow: after pushes, the first pop moves all items. So instead of finding the cost of each call separately, we add up the cost of a whole sequence of calls. Over its whole life an item is pushed onto inbox once, moved to outbox once (a pop and a push) and popped from outbox once, so items cost at most stack operations in total, in whatever order the calls come. A pour that moves many items can only follow that many cheap pushes.
This way of counting is called amortized analysis. Every item needs its own push call, so is at most the number of calls , and apart from pouring each call does a constant amount of work. So calls, starting from an empty queue, take time in total. Some calls are expensive, but the cost per call, averaged over the sequence, is , and we say that each call takes amortized time. The same kind of argument shows that appending to a list takes amortized time when the list doubles its storage each time it fills: the copies move items, and over appends they add up to fewer than moves.
Common mistakes with stacks and queues
Returning true as soon as the bracket loop ends.
- Where it breaks
- In
(()the one closer finds a matching opener, so the loop finishes without returning false. One(is still on the stack, and the function returns true for an invalid string. - The fix
- After the loop, return true only if the stack is empty.
Reading the top of the stack for a closer without checking that the stack holds anything.
- Where it breaks
- In
)(the first character is a closer and the stack is empty. Python stops withIndexError: list index out of range, and in C++ callingtop()on the empty stack is undefined behavior. - The fix
- Test for an empty stack first and return false, as the listing does.
Leaving
countunchanged after a[in Decode String.- Where it breaks
- In
2[a]3[b]the count is still 2 when the3is read, so it becomes , and the function returnsaafollowed by 23 copies ofbwhere the answer isaabbb. - The fix
- Set
countback to 0 as soon as it has been pushed.
Recall You push 4, 7, 1 and 8 onto a Min Stack and then pop twice. Which pairs does it store, and what does `getMin` return before and after the two pops?
The four pushes store , , and . The second number of each pair is the smallest value from that entry down, so getMin reads the top pair and returns 1. The two pops remove and and leave on top, so getMin now returns 4. No scan was needed to find that the minimum had gone back up to 4, because the entry for 7 recorded it when 7 was pushed.