Using collections.deque for Queues and Stacks

00:00 As you learned earlier, the main difference between a stack and a queue is the way you retrieve elements from each. Let’s use collections.deque to implement both data structures.

00:13 The queue works by appending elements to one side and removing them from the other. Let’s create a queue of people that simulates three people waiting in line.

00:28 Now that we have an empty queue, I’ll enqueue a woman named "Mary"…

00:34 and I’ll add two more people, "John" and "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.

01:02 Now, '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:35 This is the equivalent of adding new items to the top of the stack.

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.

02:05 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 .append(), .appendleft(), and .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.