Stacks: last in, first out
A stack is a pile where you only touch the top, like a pile of plates. Line 1 makes one with a Python list: "A" goes in first, at the bottom, then "B" on top of it.
Adding an item to a stack is called a push. In Python, list.append() does it: "C" lands on top of "B". Nothing underneath moves, so a push is quick however tall the stack is.
Taking the top item off is called a pop. list.pop() removes it and hands it back: "C", the last item pushed. This rule is called LIFO: last in, first out.
Undo keeps your changes on a stack and pops the latest. Python keeps a call stack: each function call pushes a frame, each return pops it. A bracket checker pushes every ( and pops one at each ).
Queues: first in, first out
A queue is a line, like people waiting at a till: you join at the back and leave from the front. Python's collections module has deque, built for this. Line 5 makes a queue of "A", then "B".
Adding an item to a queue is called an enqueue. For a deque, append() does it: "C" joins at the back, behind "B". Nobody already in the line moves.
Taking the front item is called a dequeue. q.popleft() removes it and hands it back: "A", the first item that joined. This rule is called FIFO: first in, first out.
Queues keep things in arrival order. A printer queue prints jobs in the order they were sent. Breadth-first search explores the nearest places first by queueing them. Servers put tasks in a queue for workers to take.
Picking the tool
Compare a list (the tray behind the queue). A list keeps its items packed from the start, so list.pop(0) must move every other item one place forward. Here that is 2 moves; with a million items, nearly a million. Programmers call this O(n).
A deque is built for both ends: popleft() lets the front item go and moves nothing else, so it stays fast however long the queue is (O(1)). Rule of thumb: a list for a stack, a deque for a queue.
Try it in the Python prompt
;; step 1/10 · line 1: stack = ["A", "B"] >>> stack = ["A", "B"] >>> stack ['A', 'B'] >>> stack[-1] # the top: the last item 'B'
The drawing keeps each queue item in its own slot. A Python deque really works like that: it is a chain of fixed-size blocks with a moving front, so popleft() never shifts the other items. A list is one packed row, which is why list.pop(0) has to shift them. O(n) ("order n") means the work grows in step with the number of items n; O(1) means it stays about the same however many items there are.