Reading 10
Stacks and Queues
- Stacks - represented visually, a stack would look like a vertical collection of nodes, where the first node in the stack is at the bottom and the last is at the top.
- Top - The last node in the is called the top. This is different from a linked list, where the front of the list is the first node.
- Pop - refers to the removal of the top node from the stack.
- Peek - checks to see what node is at the top of the stack.
- Push - adds a new node to the top of the stack, making it the new top.
Now that we have the stack and some terms down, let’s examine a queue. Queues take stacks and lay them on their side. Visually you can imagine nodes standing in line. When a node wants to get in the line, or enqueue , it goes to the rear of the line. The last node in the line has a next reference to None.
The dequeue operation removes the node from front of the line. First, you want to ensure the line is not empty so you wouldn’t raise an exception. The idea behind dequeue is that the node will step out of the line, meaning it will no longer be assigned a next value and its previous next value is now the front of the queue.
Peek returns the front value of the queue.
def peek(queue):
return queue.front
is_empty returns a boolean after checking to see whether the queue has any nodes in it or not.