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.

Photo by Markus Spiske on Unsplash

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.

stack concept(Image Source: Author)
Stack(Image Source: Author)

Using Lists as Stack:

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

List methods for implementation of stack in List(Image Source: Author)

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.

Queue concept(Image Source: Author)
Queue(Image Source: Author)

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:

deque methods for queue implementation in List

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s