Using collections.deque for Queues and Stacks
and I’ll add two more people,
"Susan". As you can see, the leftmost person was the first to enter the queue, and the rightmost was the last. Since this is a queue, the person who is enqueued first should be the first to dequeue. That can be accomplished with the
.popleft() method, just like this.
'Mary' has been removed. Every time we call
.popleft(), we remove the head element from the linked list. Stacks follow a similar idea, except we only use the head—or left side—of the linked list.
01:19 One place you might use a stack is when implementing a short-term collection of web pages. This linked list could store a collection of pages the user has recently visited, starting with the most recent and ending with the oldest.
01:41 Let’s inspect our stack. Everything looks good so far. Now, what happens when the user wants to go back to the first web page they visited? In a normal web browser, that would look like the user pressing the back button a few times. If you think about it, going back is the equivalent of removing items from the top of the stack.
We can do that with the
.popleft() method. If I call that enough times, then the only thing in our history will be the first web page. You just learned how you can use
.popleft() methods of the
deque object to simulate stack and queue behavior, implemented using a linked list.
02:29 As you can see, linked lists are a great choice when you need to frequently work with either end of the list. Next, let’s implement a linked list from scratch without the use of any Python modules.
Become a Member to join the conversation.