toresinc.blogg.se - Link list stack and queue

It needs no parameters and it does not modify the stack or queue.

peek() - returns the top item from the stack or first item from the front of the queue, but does not remove it.

However, the stack abstract data type and queue abstract data type also include three other methods - we will be building them into our stack and queue classes: The primary methods of a stack and queue are concerned with the insertion and deletion of elements. Once you have this written out, you can now move on to building your stack or queue. The best implementation of a stack or queue is one that enforces the LIFO or FIFO behaviour, this is because it is self-documenting and safeguards your application from bugs.ĭoubly-linked list diagram | Created by authorĪ component that is consistent between a stack and queue are nodes, let’s take a look at how we can build a node in Python: # Creating a node class class Node: def _init_(self, data): self.data = data self.next = None self.prev = NoneĪs you can see, our node contains data and two pointers, one to the previous node and one to the next node. It is worth noting that although a stack and queue both use a linked list under the hood, it is not ideal to just use a linked list over a stack and queue if the use cases you need the data structure for does not require all the functionality available to linked lists.

Alert and notification systems tend to have a FIFO behaviour, hence a queue can be used to build this.

Backend task management where operations are handled in a queue-like manner - such as API calls, database writes and pub/sub messaging systems.

Chronological news feeds behave in a LIFO manner to ensure the latest item is at the top of the feed, hence a stack can be used for this.

“Back” buttons for navigation (“Next” navigation also uses a stack).

A stack can be used to store operations that were triggered to implement the undo functionality.

Below is a list of applications for both a stack and queue.

Since the most performant operations for both data structures are insertions and deletions, and the only differing factor is their LIFO or FIFO behaviour, the situations where you would use a stack over a queue and vice versa is purely dependent on whether or not the scenario calls for a LIFO or FIFO nature.