The stack: everything happens at the top
A stack is a list with only one open end: the top. push adds at the top and pop takes from the top. At first, top is null.
A stack is a list with only one open end: the top.
push adds at the top and pop takes from the top. At first, top is null.
A stack is a list with only one open end: the top. push adds at the top and pop takes from the top. At first, top is null.
push("A") creates a node and leaves it at the top.
Each new node points to the old top and becomes the new top.
No loops: pushing costs O(1), however many nodes there are.
push("A") creates a node and leaves it at the top. Each new node points to the old top and becomes the new top. No loops: pushing costs O(1), however many nodes there are.
pop() returns the data at the top and moves the top down. Out goes "C".
Then "B" leaves: last in, first out. That is LIFO.
pop() returns the data at the top and moves the top down. Out goes "C". Then "B" leaves: last in, first out. That is LIFO.
Out goes "A" and the top is null again: the stack is empty.
Another pop() stops at the guard and throws NoSuchElementException.
Out goes "A" and the top is null again: the stack is empty. Another pop() stops at the guard and throws NoSuchElementException.
A queue opens both ends: you enter at the back and leave from the front.
With a single node, front and back point to the same one. enqueue costs O(1).
Each arrival hooks onto the back, and the back moves to it.
A queue opens both ends: you enter at the back and leave from the front. With a single node, front and back point to the same one. enqueue costs O(1). Each arrival hooks onto the back, and the back moves to it.
dequeue() takes from the front: first "A", then "B". It is arrival order.
The nodes do not shift: only the front moves on. FIFO, also in O(1).
dequeue() takes from the front: first "A", then "B". It is arrival order. The nodes do not shift: only the front moves on. FIFO, also in O(1).
Out goes "C" and the front becomes null.
But the back still points to a node that no longer belongs to the queue.
That is why, if the front becomes null, also back = null.
Out goes "C" and the front becomes null. But the back still points to a node that no longer belongs to the queue. That is why, if the front becomes null, also back = null.
The stack reverses the order: it fits undo or the call stack.
The queue keeps arrival order: the print queue, turns.
They only touch their ends, so all their operations cost O(1).
The stack reverses the order: it fits undo or the call stack. The queue keeps arrival order: the print queue, turns. They only touch their ends, so all their operations cost O(1).