Introduction to Data structures and Algorithms in Python
Published: 2021-10-10 18:44:47

Data structures are a way of organizing and storing data so that they can be accessed and worked with efficiently while Algorithms are sequence of well defined instructions  for solving a problem or a accomplishing a given task.

This article gives a detailed understanding of the most commonly used data structures that is Stack and queue and their implementation in python.


######STACK

Stack is one of the earliest data structure defined in computer science as a linear data structure which stores items using LIFO( Last In First Out) principle for insertion and deletion.

To get a clear understanding of a stack think about a pile/stack of books. You add a book at the top of the stack, so the first one to be picked up will be the last one that was added to the stack.

Stack has two operations:
* Push- adds an item to the top of the stack.

![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sdfuftiufnmwhcpbbh1i.png)
 
* Pop- removes an item from the stack.

![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/92m8rulj7nn08wry5dkf.png)
 

######Why do we use stacks?

* Stack are simple to learn and implement.
* Stack allows us store and retrieve data sequentially.
* Stacks take O(1) time for insert and delete operations.

######Real world use cases of a stack.

* Web browsers use stack to keep track of URL that you have accessed previously. When you visit a new page, it is added to the stack when you hit the back button, stack is popped and previous URL is accessed.
* Undo mechanism in text editor uses stack to keep all changes.
* To implement other data structures- stack is used to implement searches in graphs and trees.
* Compilers and Parsers uses stack

[More applications of Stack Data structures](https://tutorialsbookmarks.com/applications-of-stack-in-data-structure/)

######Stack Methods

Stack operations are implemented using the following methods:
* stack.IsEmpty- Returns True if a stack is empty and false otherwise.
* stack.length()- Returns length of stack.
* stack.top()- returns a pointer/reference to top element in stack.
* stack.push(x)- inserts element x to the top of the stack.
* stack.pop()- Removes top element of stack and returns it.

######Stack implementation in Python.

In python, we can implement stack using the following ways;
1. Using the built-in List data structure. 
2. Using the deque library which efficiently provides stack operations in one object. 

Stack Using List.

To implement stack using list, **append** and **pop** methods are used.
append() method in python adds a single item to the existing list
pop() removes the element at the specified position

Example
```python
s = []
  
s.append('stack')
s.append('queue')
s.append('list')
s.append('tuple')

print(s)
```
Output
```
['stack', 'queue', 'list', 'tuple']
```

Using pop
```python
s.pop()
>>tuple
s.pop()
>>list
s.pop()
>>queue
s.pop()
>>stack
s.pop()
>>IndexError: pop from empty list
```
[Check this implementation](https://colab.research.google.com/drive/1HaKVwd6zhK92vLn45xm1Cim-0fIoD0bu?usp=sharing)

[ Read More about stacks](https://www.edureka.co/blog/stack-in-python/)

######QUEUES
Just like a stack, a queue is a linear data structure. 
Queue stores items using FIFO (First in first out) principle for insertion and deletion.

######Operations Associated with Queue in Python.

 * Enqueue: It adds an element to the end of the queue. When the queue reaches its total capacity, it reaches an overflow condition. 

* Dequeue: Removes an element from the queue.  When the queue becomes empty, it reaches an underflow condition. 

* Front: returns the first item from the queue. 

* Rare: Returns the last item from the queue.

######Applications of a Queue
A queue is useful in the following scenarios;

* Handling interrupts in real-time systems- interrupts are handled in same order as they arrive.
* Handling website traffic.
* Serving request on a single shared resource like a printer or CPU task scheduling.


[Applications of Queue Data Structure]
(https://www.geeksforgeeks.org/applications-of-queue-data-structure/)

######How to implement queue in Python
There are different ways to implement a queue in Python. The 
common ways are;
* Using built-in List data structure.
* Using collections.deque library

######Implementing a Queue in Python with a List

The list’s append() and pop() methods are used to insert and delete elements from the queue.

```python
# Initialize a queue

queue = []

# Adding elements to the queue

queue.append('Python')

queue.append('Javascript')

queue.append('Typescript')
print(queue)
```
Output
```
['Python', 'Javascript', 'Typescript']
```

```python
# Removing elements from the queue



print(queue.pop(0))

print(queue.pop(0))

print(queue.pop(0))


print(queue)
```
Output
```
Python
Javascript
Typescript
[]
```
######Implementing a Queue in Python with collections.deque

The deque class from the python collections module can also be used to implement a queue. It is more efficient because deque provides faster enqueue and dequeue operations.
```python
from collections import deque

queue = deque()

queue.append('Black')

queue.append('White')

queue.append('Orange')

print(queue)
```
Output

```
deque(['Black', 'White', 'Orange'])
```
I hope you enjoy reading the article as much as I enjoyed writing it, the following are the useful resources and reference materials that i used. 

[Find the full source code here](https://colab.research.google.com/drive/1bd6jJFKrOZLgxMC_ieJYJNe2L48n4Fx1?usp=sharing)

[Using the Queue Data Structure in Python](https://www.section.io/engineering-education/queue-data-structure-python/)

[How to implement a queue in Python](https://www.educative.io/edpresso/how-to-implement-a-queue-in-python?utm_term=&utm_campaign=%5BTest%5D+Dynamic+Verticals&utm_source=adwords&utm_medium=ppc&hsa_acc=5451446008&hsa_cam=14045073269&hsa_grp=128822123241&hsa_ad=535845844735&hsa_src=g&hsa_tgt=aud-597782228546:dsa-1394252596758&hsa_kw=&hsa_mt=b&hsa_net=adwords&hsa_ver=3&gclid=Cj0KCQjwnoqLBhD4ARIsAL5JedKJSQeXV9jwhJBGLrU1JocjSGoeNKUGTkvbmC6EPXogXDL7tKFmaBgaAo2CEALw_wcB)