Using Lists as Stacks and Queues in Python

Before reading about stacks and queues, you may wish to read about – How to create and modify lists in python.

What is a Stack?

A stack is a data structure that could be represented by a pile where insertion and deletion of items takes place only at a single end called top of the stack. The basic way to access data in stack is by Last In First Out(LIFO) method. To understand the structure of stack, imagine a pile of books (call it stack). One can use only the top end of the pile to add or remove a book to the stack. Also, index numbers are not assigned to elements in a stack, hence, the elements in the middle of a stack cannot be accessed directly.

Using List as a Stack

We create a list called stack.

stack = ["geography","statistics","biology","linear algebra"]
stack

[‘geography’, ‘statistics’, ‘biology’, ‘linear algebra’]

Insertion to a Stack
Now we use append() to add new elements to the stack. Here the last element being added is “economics”.

stack.append("physics")
stack.append("history")
stack.append("economics")
stack

[‘geography’,’statistics’, ‘biology’, ‘linear algebra’, ‘physics’, ‘history’, ‘economics’]

Deletion from a Stack
Now we remove the element last added by using pop() without an index number. Remember elements in a stack do not have index numbers.

stack.pop()

‘economics’

stack.pop()

‘history’

We see that our stack follows the principle of LIFO (as mentioned above). Lets check our stack after removing the last two elements.

stack

[‘geography’, ‘statistics’, ‘biology’, ‘linear algebra’, ‘physics’]

What is a Queue?

A queue is a data structure that could be represented by a queue(sequence of people) at a ticket counter. It has a front and a back. At a ticket counter queue, new persons join at the back and the first person buys the tickets first and leaves first. Similarly, the data structure queue follows the principle of First In First Out(FIFO). Addition of elements is called “Enqueue” and Removal of elements is called “Dequeue”. Enqueue takes place at the back, while Dequeue takes place at the front.

 

Using List as a Queue
To use list as a queue, we use collections.deque. It was designed to have faster appends and pops from both ends of a list.
from collections import deque

Now, we create a queue by using deque()on a list.

queue = deque(["rohan", "sameer", "adil", "saksham"])
queue

deque([‘rohan’, ‘sameer’, ‘adil’, ‘saksham’])

Insertion to a Queue
We use append() to add an element at the end of the queue.

queue.append("priya")
queue.append("aashi")
queue

deque([‘rohan’, ‘sameer’, ‘adil’, ‘saksham’, ‘priya’, ‘aashi’])

Deletion from a Queue
We use popleft() to remove the element at the beginning of the queue.

queue.popleft()

‘rohan’

queue.popleft()

‘sameer’

We see that our queue follows the principle of FIFO (as mentioned above). Lets check our queue after removing the first two elements.

queue

deque([‘adil’, ‘saksham’, ‘priya’, ‘aashi’])

Advertisements

3 thoughts on “Using Lists as Stacks and Queues in Python

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s