How to Use Lists As Stacks and Queues in Python

Let’s learn about how to use list as stacks and queues using collections.deque in python.

Stack:

A stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack according to the last-in first-out (LIFO) principle.
 push adds an item to the top of the stack, pop removes the item from the top.

Using Lists as Stack:

List methods make it very easy to use list as stack.

https://gist.github.com/IndhumathyChelliah/11d1b5685852e1228eee22855434af4c

---

Using Lists as Queues:

Queues:

Queue is a linear data structure where the first element is inserted from one end called REAR and deleted from the other end called as FRONT.In a queue, one end is always used to insert data (enqueue) and the other is used to delete data (dequeue), because queue is open at both its ends.Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

Using Lists as Queues:

We can use list as queues, where first element inserted is retrieved first(FIFO).List is not efficient for this purpose. append() and pop() at end of the list is faster but doing insert() and pop() at beginning of list is slow because all the elements have to be shifted by one.

To implement queue in list, we are using collections.deque.
collections.deque is designed to do fast append and pop at both end of list.

deque means double ended queue.

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

deque methods for queue implementation:

If list is empty,both pop() and popleft() raises IndexError.

https://gist.github.com/IndhumathyChelliah/e4845dc5473ba654c70ed12891dfcab9

---

Resources(Python documentation):

deque objects:
https://docs.python.org/3/library/collections.html#deque-objects

Using Lists as stack:
https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks

Using Lists as Queue:
https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-queues