Stack and Queue in Python

Have you ever wanted to eat at your favorite restaurant but saw a stack of books or had to wait in line? Every day, we come across things that resemble a stack and a queue. The most self-explanatory data structures are arguably stacks and queues; even so, they might be daunting to certain people.
In this note, we will discuss what stacks and queues are in the context of computer science, the operations we can carry out with them, and a small Python implementation of each.

Stack

A stack is a linear data structure with push and pop as its two primary operations. Push means to add anything to the top of the stack. Pop signifies the removal of an element from the stack's top. Due to its support for quick last-in, first-out (LIFO) semantics for inserts and deletes, stacks are referred to as a LIFO (Last in, First out) system. Typically, stacks do not permit random access to the things they contain, unlike lists or arrays.
Performance-wise, insert and delete operations on a proper stack implementation should take O(1) time.
Stacks can only be moved in one direction, so if we wanted to add anything to the structure or take something away, we would have to start from the top of the stack.
The stack's construction is identical to a stack of plates. When setting the table, we never begin by taking the very bottom plate; instead, we begin by making the plate from the top of the stack and placing it on the table. Newly washed dishes are placed at the top of the stack. In stacks, just the top of the stack may be used for insertion and deletion. This practice is known as Last In, First Out (LIFO).

Operations of Stack

A similar concept may be applied to the stack ADT to produce a collection of objects. It utilizes two main operations:

• Pushing something up to the top of the stack
• Removing a newly added item from a stack using a pop command

• Getting the last element from the stack using the peek method.

  The time complexity of a stack

• push-O(1)

• pop-O(1)

• peek-O(1)

When are stacks useful?

Tracing back to access the previous elements- for instance, undo operations in editors are similar to popping a recently pushed code change from the stack of edit history. Similar to popping a website visit that was recently pushed into the history stack of a browser, back operations in browsers do the same thing.

How does create your own stack

class Stack:
    def __init__(self):
        self.stack = []    
    def pop(self):
        if self.is_empty():
            return None
        else:
            return self.stack.pop()    
    def push(self,data):
        return self.stack.append(data)    
    def top(self):
        if self.is_empty():
            return None
        else:
            return self.stack[-1]  
    def is_empty(self):
        return self.len() == 0 
    def len(self):
        return len(self.stack)    
s = Stack()
s.push(5)   # s=[5]
s.push(4)   # s =[5,4]
s.push(6)   # s =[5,4,6]
s.push(9)   # s = [5,4,6,9]
s.push(1)   # s = [5,4,9,6,1]
s.push(2)   # s = [5,4,9.6,1,2]
print(s.top())  # top of the stack is 2
print(s.pop())  # poped element is 2
print(s.len())  #lenght of stack is 5

Output

Implementing stacks as arrays versus linked lists

Linked lists are frequently used in stack operations. They naturally lend themselves to functioning exactly like singly-linked lists since they can only "grow" in one way, allowing us to add and delete members from a single location.

Remember that the linked list contains a head node and that adding members to the beginning of the linked list has constant space-time complexity (O(1)). I love that! We can do that single action regardless of the size of our stack in roughly the same amount of time since we are just adding and deleting from the top (our head node).
Can we use arrays to implement a stack? Yes; however, arrays are static data structures, thus there is a disadvantage to this. A collection of data in memory with a defined size is known as a static data structure. However, there is no upper limit to the size of a stack; it can expand indefinitely!

When utilizing an array to construct a stack, things might become pretty nasty if we try to add more components to the stack than the array can hold.
Since the stack believes it can expand as big as it wants, it won't stop us from adding additional items, but the array won't have enough room to provide the new elements we are adding adequate memory. An overflowing stack is the result of everything! That's never a good thing. For instance, each shelf on our bookshelf can hold 10 books. We are constantly adding to our collection of books, which has outgrown our bookshelves.
Linked lists, on the other hand, are dynamic data structures. Their memory may change in size. A dynamic data structure may fluctuate in size and shape as well as the amount of memory it requires; therefore, it doesn't require a specific amount of memory to be set aside for it to exist. When a stack is implemented using a linked list, stack overflows are rather infrequent. That would only ever occur if we used up all of the available memory on our computers. If that were the case, we'd be dealing with a much worse issue (like a memory leak).
To summarise, many stacks are linked list implementations for the following reasons:

• continuous complexity of space-time
• the capacity to expand rapidly in size. ##Building up a stack It's fantastic that we now understand what a stack is, but how challenging is it to construct one? Happy news: In Python, creating a stack is surprisingly simple because of lists []. We can add and remove components from the bottom of the stack.

Output

Queue

Enqueue and dequeue are the two primary operations of a queue, which is a data structure. Enqueue: Add a component to the queue's end. Dequeue: Take an item out of the queue by moving it to the bottom. First in, first out (FIFO) is the term used to describe queues as a data structure. Queues normally do not permit random access to the items they hold, unlike lists or arrays.
Performance-wise, insert and delete operations on a well-implemented queue should take O(1) time.
An open-ended data structure is a queue. Data is always added to one end (enqueued), and removed from the other (dequeued). First In First Out (FIFO) approach is modified in this.
The primary distinction between a queue and a stack is that components in a queue are added to the bottom and removed from the top, but elements in a stack are added to the top and removed from the top in just one direction.
A line of patrons waiting to enter a restaurant is a prime illustration of a queue. Each new client enters the queue at the back. Always start serving the person in front of the queue. First in, first out policy refers to the practise of serving the first client in line.

Operations of Queue

Similarly, we can put a new item in the queue and remove from the front of the queue. There are two main queue operations:
Enqueue means to add a new item to the rear (end) of the queue.
Dequeue means to take the first thing out of line, or to serve the first person in line.

Time complexity of a stack

• enqueue-O(1)
• dequeue-O(1)

When are queues useful?

When you want to handle items as they come in one at a time, you utilize queues. Examples include processing hundreds of queries to a web server, printing several papers, and uploading a lot of photos.
Queues are used in a wide variety of algorithms, scheduling issues, and parallel programming issues. Breadth-first search (BFS) on a tree or graph data structure is a quick approach that uses a queue.

How to create your own Queue

class Queue:
    def __init__(self):
        self.queue = []    
    def enqueue(self,data):
        self.queue.insert(0,data)    
    def dequeue(self):
        if self.is_empty():
            return None
        else:
            return self.queue.pop()    
    def len(self):
        return len(self.queue)    
    def is_empty(self):
        return self.len() == 0
q = Queue()
q.enqueue(3)  # q = [3]
q.enqueue(4)  # q = [4,3]
q.enqueue(7)  # q = [7,4,3]
q.enqueue(1)  # q = [1,7,4,3]
q.enqueue(2)  # q = [2,1,7,4,3]
print(q.dequeue())
print(q.len())

Output

Implementing Queue as arrays versus linked list

As we already know, when more components are put onto the stack than the allotted size of the array can support, implementing a stack as an array can lead to a messy stack overflow. Accordingly, it turns out that, depending on the circumstances and conditions, arrays may wind up being even poorer implementation tools when it comes to queues.
When we are aware of the size of our data structure in advance, arrays may be incredibly powerful. But there are several occasions when we are unsure of the size of the line. What transpires then when we need to add (enqueue) an element to a queue? In other words, if we are utilizing an array and do not know the queue size in advance, we will exhaust the memory and space that has been allocated. Therefore, we must duplicate the information in our array, then set aside more room and memory, and finally enqueue a new element at the end of the queue.
With array-based queue implementations, there is an additional layer of complexity because we enqueue (add) at the back of the array and dequeue (remove) from the front. While this isn't always a bad thing because accessing the first or last element in an array doesn't take too long, it isn't as convenient as with stacks, where adding and removing items all take place from one end of the structure. We will need to be able to reach both ends of our expanding array, which will increase the space-time complexity.
Things are made easier with a linked list implementation of a queue. Since memory can be spread and the linked list may expand dynamically (so long as we don't use up all of the computer's memory), we don't need to worry about the queue size in advance. Because we can easily locate a memory area and add a node with information about its next neighbor, enqueuing and dequeuing are easier to handle. There's no need to duplicate our queue, as we would have to if we were using an array approach. Additionally, if we add pointer references to the start and end of our list, we may enqueue or dequeue one element without having to go through the entire structure.
The space-time complexity of the enqueue and dequeue functions on a queue becomes constant time, or O(1), once the requirement to traverse through the queue is removed. This means that, regardless of the size of the queue, adding or removing an element always takes a fixed amount of time.

Building up a Queue

queue = [3,4,3,7,1,8,4,3,2]
queue.append(9) # 9 is added to the queue
print(queue)
queue.pop() # remove the first element from the queue. 
print(queue)

Output

Conclusion

We studied the most basic concepts of stack and queue in this note. We were familiar with how to use queues and stacks in Python. Both a stack and a queue can be implemented validly in array or linked list form. But it's crucial to understand how these two implementations differ from one another and when one could be more practical for us.
Two essential Python data structures that are frequently used for effectively managing and organizing data are stack and queue. A queue adheres to the FIFO (First In, First Out) philosophy, whereas a stack follows the LIFO (Last In, First Out) idea. Comprehending these ideas facilitates the resolution of programming issues and the creation of effective algorithms.
Lists and collections are two of the techniques that Python offers to build a stack and a queue. deque module. Developers can enhance their applications' performance, readability, and efficiency by selecting the right data structure based on the needs of an issue. Therefore, anyone studying Python and data structures must have a solid grasp of stacks and queues.