Stacks and queues are both lists. But they have different and stricter rules. This article will discuss stacks and queues. First, there will be a stack implementation and then a queue with stacks.

Stack

Stacks are lists with the last-in-first-out (LIFO) rules. The element that goes in last, goes out first.

You might think about what can be the use of that. One good example is the undo operation in the editor. When we ‘undo’, it reverses the last operation. A compiler checks the matching parenthesis using a stack. Here is the functionality required for the stack:

1. Initialization of an empty list.
2. Adding the elements to the list.
3. Popping out the elements from the list.
4. Check if the list is empty.
5. Determine the top element of the list.
6. Get the list.

Python Implementation of the functionality above:

class Stack():
    def __init__(self):
        self.elements = []def push(self, element):
        self.elements.append(element)def pop(self):
        return self.elements.pop()def is_empty(self):
        return self.elements == []def peek():
        if not self.elements.is_empty():
            return self.elements[-1]def get_elements(self):
        return self.elements

Queue

A queue is also a list or a container. It follows first-in-first-out(FIFO) rule. A good example is a line in a grocery shop. A person who comes in the line first gets the chance to pay and leave first. When a new person wants to be in the line, s/he has to go in the back of the line. The queue has two operations. Enqueue and dequeue. Where enqueue means to add the elements in the list or container. Dequeue means to remove an element from the bottom of the list.

Here is the picture that clearly shows the difference between stack and queue:

We can implement a queue using two stacks.

1. Enqueue the elements in stack1.
2. Dequeue can be tricky. Because stack removes an element from the top. But queue removes an element from the bottom. We need to pop all the elements from stack1 and keep adding them in the stack2. So, the bottom element of the stack1 will be the top element of stack2. Now if we pop an element from the stack2, we popped the bottom element of stack1. So, that’s our dequeue operation. After the operation is done, we should put the elements back in the stack1 again. Here is how the code looks like:

class Queue:
    def __init__(self):
        self.stack_1 = Stack()
        self.stack_2 = Stack()def enqueue(self, item):
        self.stack_1.push(item)def dequeue(self):
        if not self.stack_1.is_empty():
            while self.stack_1.size()> 0:
                self.stack_2.push(self.stack_1.pop())
            res = self.stack_2.pop()
            while self.stack_2.size()>0:
                self.stack_1.push(self.stack_2.pop())
            return res

I wanted to share this because it is a good practice material who is learning algorithm and data structure.

Here is an article on some problem solving using the sorting algorithm:

1. Finding the intersection of two sets of coordinates and sorting the buckets by color.