Last-in, first-out stack

When to use it

Use it when the newest item still waiting is the only one that matters now, and older items must wait until it is finished or removed.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A drawing app records each action you take. The word "undo" removes the newest action that is still there. Return the actions that are left, oldest first.

Input
actions = ["line", "circle", "undo", "square", "fill", "undo", "undo", "text"]

Output
["line", "text"]

The method

1. Start with an empty stack of the actions still kept
2. An undo takes the top action off, if the stack has one
3. Any other action goes on top of the stack
4. What is left, read from the bottom up, is the answer

The run, one moment at a time

1. Step 1. No action has been read yet, so the stack is empty.

   actions: line circle undo square fill undo undo text
   stack: empty
   

2. Step 3. "line" is an action, so it goes on top of the stack. Putting an item on top is called a push.

   actions: line circle undo square fill undo undo text
   stack: line  (top at 0)
   

3. Step 3. "circle" is an action, so it goes on top of the stack. It is now the newest.

   actions: line circle undo square fill undo undo text
   stack: line circle  (top at 1)
   

4. Step 2. "undo" takes "circle" off the top, because it is the newest action still kept. Taking the top off is called a pop. "line" is the top again.

   actions: line circle undo square fill undo undo text
   stack: line circle  (top at 0)
   

5. Step 3. "square" is an action, so it goes on top of the stack. It is now the newest.

   actions: line circle undo square fill undo undo text
   stack: line square  (top at 1)
   

6. Step 3. "fill" is an action, so it goes on top of the stack. It is now the newest.

   actions: line circle undo square fill undo undo text
   stack: line square fill  (top at 2)
   

7. Step 2. "undo" takes "fill" off the top, because it is the newest action still kept. "square" is the top again.

   actions: line circle undo square fill undo undo text
   stack: line square fill  (top at 1)
   

8. Step 2. "undo" takes "square" off the top, because it is the newest action still kept. "line" is the top again.

   actions: line circle undo square fill undo undo text
   stack: line square  (top at 0)
   

9. Step 3. "text" is an action, so it goes on top of the stack. It is now the newest.

   actions: line circle undo square fill undo undo text
   stack: line text  (top at 1)
   

10. Step 4. Left on the stack: "line" and "text". These actions were never undone, and they are already in order, oldest first.

    actions: line circle undo square fill undo undo text
    stack: line text  (top at 1)
    

The code

The numbered comments are the steps of the method.

function solve(actions) {
  // 1. Start with an empty stack of the actions still kept
  const stack = [];
  for (const action of actions) {
    // 2. An undo takes the top action off, if the stack has one
    if (action === "undo") {
      if (stack.length > 0) stack.pop();
      continue;
    }
    // 3. Any other action goes on top of the stack
    stack.push(action);
  }
  // 4. What is left, read from the bottom up, is the answer
  return stack;
}

def solve(actions):
    # 1. Start with an empty stack of the actions still kept
    stack = []
    for action in actions:
        # 2. An undo takes the top action off, if the stack has one
        if action == "undo":
            if stack:
                stack.pop()
            continue
        # 3. Any other action goes on top of the stack
        stack.append(action)
    # 4. What is left, read from the bottom up, is the answer
    return stack

How to spot it

Given: Things open and close, one inside another

What opened last must close first. Keep the open ones on a stack, and each close only looks at the top.

Asked: Undo, cancel or go back to the most recent step

The step to take away is the newest one still kept, and that is the top of a stack.

Asked: An item combines with, or cancels, the one right before it

After a cancel, the item before that becomes the neighbor. A stack keeps that earlier item ready on top.

Looks like it, but is not

• For each item you need the nearest later item that is larger. Use Monotonic stack. It is a stack too, but items are taken off by comparing sizes, so the stack stays in order.
• Besides putting items on top and taking them off, another question about the items must be answered fast. Use Purpose-built data structure. A plain stack shows only its top. For the extra question you must store something more and keep it up to date.
• You only ask whether a value came earlier, anywhere in the list. Use Hash set membership. The match can be any earlier item, not the newest one. A set finds it wherever it was.

Cost and mistakes

Time is about n steps for n items, written O(n): each item goes on the stack once and comes off at most once. Extra space is the stack, which holds every item when nothing is taken off.

Watch out

• Check that the stack is not empty before you take from it or read its top. In Python, pop on an empty list stops the program with an error.
• Look at what is left on the stack at the end. Leftover items are often the answer, or the sign that something opened and never closed.

In the 150

2 problems of the 150 use it. Naming them gives their method away, so the list is folded.