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.

00:46 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.

01:58 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.

02:15 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.