Stack vs. Queue — How To, When To, and Why To Use Them (2023)

Everything you need to know about using the stack and queue data structures

Stack vs. Queue — How To, When To, and Why To Use Them (1)

Published in

Better Programming

·

10 min read

·

Jan 28, 2022

--

Stack vs. Queue — How To, When To, and Why To Use Them (3)

Linear data structures are essential to software engineering and provide the foundations required to build the many features we use every day — think news feeds and notifications systems. When given the task to build these features, many engineers simply turn to arrays without considering two very important data structures: stacks and queues.

This article is a deep dive into the stack and queue data structures, their use cases, trade-offs and implementations. By the end of this article, you’ll have a clear understanding of stacks and queues to be able to use them in your own engineering tasks.

Before diving into the rabbit hole, it’s best to understand the reasons why you might want to consider a stack or queue rather than an array. As mentioned earlier a stack, queue and array are all linear data structures — however, the most performant operations differ between these data structures.

Three different notations can be used when comparing the performance of operations — Big O, Omega and Theta. Big O is more commonly used as it represents the worse case scenario.

By using contiguous memory storage, arrays execute random element access the fastest out of the three data structures — random access has a time complexity of O(1). The downside of using an array is that you can only achieve O(n) when searching, inserting and deleting elements. Alternatively, you’ll only achieve O(n) when using a stack or queue for random access, but insertions and deletions will have a time complexity of O(1).

Stack vs. Queue — How To, When To, and Why To Use Them (4)

Ultimately, the data structure you should use depends on the most common operation(s) required given the use case.

Now that you know when to avoid using an array, let’s take a look at stack vs queue in detail.

The most tangible way to visualise a stack is to think of a stack of plates. When adding a plate to your stack, you wouldn’t want to try placing it somewhere in the middle; instead, you’ll add it to the top of the stack. Similarly, when removing plates from the stack you’d start from the top first and make your way down. This is exactly how a stack data structure behaves, in other words, it inserts and deletes elements in a LIFO manner (last-in-first-out).

Stack vs. Queue — How To, When To, and Why To Use Them (5)

To achieve a constant time complexity (O(1)) for insertions and deletions, stacks are built using linked lists. This is because elements change their location in memory when an insertion or deletion occurs on an array; hence it’s linear time complexity (O(n)). Whereas that behaviour does not occur in linked lists, but we’ll go into that more later in this article.

Just like stacks, queues also exist in the physical world — think of a queue of people lining up to a cash register. Just as the first person to line up would be the first served, the first element added to a queue will be the first element to be deleted — following the FIFO principle (first-in-first-out).

Stack vs. Queue — How To, When To, and Why To Use Them (6)

Queues also use linked lists under the hood to ensure a time complexity of O(1) when inserting and deleting elements.

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. Below is a list of applications for both a stack and queue.

Stack use cases

  • A stack can be used to store operations that were triggered to implement the undo functionality.
  • “Back” buttons for navigation (“Next” navigation also uses a stack).
  • 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.

Queue use cases

  • Backend task management where operations are handled in a queue-like manner — such as API calls, database writes and pub/sub messaging systems.
  • Alert and notification systems tend to have a FIFO behaviour, hence a queue can be used to build this.

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. 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.

As mentioned earlier, the most optimal way to build a stack and queue is to use a linked list. This is because linked lists allow you to achieve a time complexity of O(1) when inserting and deleting elements.

Linked lists consist of adjoining nodes containing data, connected together with pointers. There are three forms of linked lists: singly-linked, doubly-linked and circular-linked; we’ll use doubly-linked lists in our example.

A doubly-linked list has three main components: a head — which is the first element, a tail — which is the last element, and a node — which contains its data, a pointer to the next element and a pointer to the previous element.

Stack vs. Queue — How To, When To, and Why To Use Them (7)

A 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 classclass Node:

def __init__(self, data):
self.data = data
self.next = None
self.prev = None

As you can see, our node contains data and two pointers, one to the previous node and one to the next node.

Once you have this written out, you can now move on to building your stack or queue.

The primary methods of a stack and queue are concerned with the insertion and deletion of elements. 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:

  • peek() — returns the top item from the stack or first item from the front of the queue, but does not remove it. It needs no parameters and it does not modify the stack or queue.
  • isEmpty() — tests to see whether the stack or queue is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items on the stack or queue. It needs no parameters and returns an integer.

How to build a stack

Although a doubly-linked list contains both a head and a tail, a stack is only concerned about its head, which is referred to as the top of the stack. Let’s start off by creating an instance variable for the top of the stack, as well as a size instance variable:

# Creating a stack classclass Stack:
def __init__(self):
self.top = None
self.size = 0

Size method
Next up is the size method, which simply returns the size of the stack:

def getSize(self):
return self.size

isEmpty method
Next, we can implement the isEmpty method — all that’s needed is to test whether the stack is empty and return a boolean:

def isEmpty(self):
return self.size == 0

Peek method
Next up, we can implement the peek method, there are two things we need to do:

  1. Sanitary check to see if the stack is empty and raise an exception if it is.
  2. Return the data from the top item of the stack.
def peek(self):
if
self.isEmpty(): #1
raise Exception("Peeking from an empty stack")
return self.top.data #2

Now we can move on to our main operations: push elements to the top of the stack and pop elements from the top of the stack.

Push method
Starting off with the push operation, there are four steps required:

  1. Create a Node instance and set its next pointer to the stack’s original top node.
  2. If there is an existing top to the stack, set its prev variable to the new node.
  3. Update the top instance variable to the new node.
  4. Increase the size of the stack by one.
def push(self, new_el):
new_node = Node(new_el) #1 - create node
new_node.next = self.top #1 - set next pointer
if self.top != None:
self.top.prev = new_node #2
self.top = new_node #3
self.size += 1 #4

Pop method
And finally is the pop operation which requires six steps:

  1. Retrieve the first node from the stack’s top instance variable.
  2. Set the second node’s prev pointer to None .
  3. Update the top instance variable to the second node.
  4. Set the next pointer to None on the node you are deleting.
  5. Decrease the size of the stack by one.
  6. Return the data for the node you are deleting.
def pop(self):
if self.top == None:
print("Stack is empty")
else:
del_node = self.top #1
del_node.next.prev = None #2
self.top = del_node.next #3
del_node.next = None #4
self.size -= 1 #5
return del_node.data #6

Once your stack has been built, you can use it like so:

stack = Stack() # create a stack instancestack.isEmpty() # logs 'True'stack.push('c')
stack.push('b')
stack.push('a')
stack.top.data # logs 'a'
stack.getSize() # logs '3'
stack.peek() # logs 'a'
stack.pop() # logs 'a'
stack.top.data # logs 'b'
stack.getSize() # logs '2'
stack.isEmpty() # logs 'False'

Unlike a stack, queues are concerned with both the head and tail component of a doubly-linked list as deletions and insertions occur on opposite ends of a queue, referred to as the front (right side of the queue) and rear (left side of the queue). In that case, an instance variable is required for the front and rear of a queue, as well as a size instance variable.

# Creating a queue classclass Queue:
def __init__(self):
self.front = None
self.rear = None
self.size = 0

Size method
Next up is the size method, which simply returns the size of the queue:

def getSize(self):
return self.size

isEmpty method
Next, we can implement the isEmpty method — all that’s needed is to test whether the queue is empty and return a boolean:

def isEmpty(self):
return self.size == 0

Peek method
Next up, we can implement the peek method, there are two things we need to do:

  1. Sanitary check to see if the queue is empty and raise an exception if it is.
  2. Return the data from the front element of the stack.
def peek(self):
if
self.isEmpty(): #1
raise Exception("Peeking from an empty queue")
return self.top.data #2

Now we can move on to our main operations: insert elements to the rear of the queue and delete elements from the front of the queue.

Enqueue method
Starting off with the enqueue method which contains five steps:

  1. Create a Node instance and set its next pointer to the queue’s original rear node.
  2. If there is an existing rear node to the queue, set its prev variable to the new node.
  3. If there was not an existing rear node to the queue (i.e. the queue was empty), set the front instance variable to the new node.
  4. Update the rear instance variable to the new node.
  5. Increase the size of the queue by one.
def enqueue(self, new_el):
new_node = Node(new_el) #1 - create node
new_node.next = self.rear #1 - set next pointer
if self.rear != None:
self.rear.prev = new_node #2
else:
self.front = new_node #3
self.rear = new_node #4
self.size += 1 #5

Dequeue method
The final step is to build the dequeue method which involves six steps:

  1. Retrieve the front node from the queue’s front instance variable.
  2. Get the previous node from the front and set it’s next pointer to None .
  3. Update the front instance variable to the node mentioned in step 2.
  4. Set the prev pointer to None on the node you are deleting.
  5. Decrease the size of the queue by one.
  6. Return the data for the node you are deleting.
def dequeue(self):
if self.front == None:
print("Queue is empty")
else:
del_node = self.front #1
del_node.prev.next = None #2
self.front = del_node.prev #3
del_node.prev = None #4
self.size -= 1 #5
return del_node.data #6

And finally, you can use your queue like so:

queue = Queue() # create a queue instancequeue.isEmpty() # logs 'True'queue.enqueue('c')
queue.enqueue('b')
queue.enqueue('a')
queue.front.data # logs 'c'
queue.rear.data # logs 'a'
queue.getSize() # logs 3
queue.peek() # logs 'c'
queue.dequeue() # logs 'c'
queue.top.data # logs 'b'
queue.rear.data # logs 'a'
queue.getSize() # logs '2'
queue.isEmpty() # logs 'False'

While both stacks and queues are non-primitive, linear data structures that are best implemented using a linked-list the key difference is their LIFO vs FIFO nature.

Given the differences in how elements are inserted and deleted from a stack and queue, the applications in which the data structures are used are entirely different.

Equipping yourself with an in-depth understanding of every data structure available to you will help you build performant and efficient applications given every use case under the sun, I hope this article has helped you build that set of knowledge!

FAQs

Stack vs. Queue — How To, When To, and Why To Use Them? ›

Stacks and queues are used over arrays when sequential access is required. To efficiently remove any data from the start (queue) or the end (stack) of a data structure.

Why do we use stacks and queues? ›

Stacks and queues are used over arrays when sequential access is required. To efficiently remove any data from the start (queue) or the end (stack) of a data structure.

What is a real time example of stack and queue? ›

The stack of trays in a cafeteria; A stack of plates in a cupboard; A driveway that is only one car wide.

Why does queue perform better than stack? ›

The primary difference between Stack and Queue Data Structures is that Stack follows LIFO while Queue follows FIFO data structure type. LIFO refers to Last In First Out. It means that when we put data in a Stack, it processes the last entry first. Conversely, FIFO refers to First In First Out.

What is the difference between a queue and a stack? ›

A stack follows a LIFO (Last In First Out) order, whereas a queue follows a FIFO (First In First Out) order for storing the elements. A stack uses one end known as a top for insertion and deletion whereas a queue uses two ends front and rear for insertion and deletion.

When would you use a queue? ›

Queue is used when things don't have to be processed immediately, but have to be processed in First In First Out order.

When should we use stack? ›

A Stack can be used for evaluating expressions consisting of operands and operators. Stacks can be used for Backtracking, i.e., to check parenthesis matching in an expression. It can also be used to convert one form of expression to another form. It can be used for systematic Memory Management.

What is a real life example of a queue? ›

The ticket queue outside a cinema hall is a real-world example of a queue, where the person who enters first gets the ticket first, and the person who enters last gets the ticket last.

What are two example of queue in real life? ›

You can also explore: Breadth-First Search Algorithm

Some other applications of the queue in real-life are: People on an escalator. Cashier line in a store. A car wash line.

What are the common use cases of stacks and queues? ›

Stacks are used in cache based applications, like recently opened/used application will comes up. Queues are used in deleting/remove the data, like first inserted data needs to be deleted at first.

Why use a queue instead of a database? ›

Message queue is there to help you write losely coupled applications (or application components) and database to save states. You need to get a state, get it from a database. You need to make your components communicate, use a message queue.

What are the advantages of queue? ›

Benefits of Message Queues
  • Better Performance. Message queues enable asynchronous communication, which means that the endpoints that are producing and consuming messages interact with the queue, not each other. ...
  • Increased Reliability. ...
  • Granular Scalability. ...
  • Simplifed Decoupling.

Is a queue or stack more efficient? ›

While queue and stack aren't wildly different in performance, they obviously induce a different node-visiting order. One of them may give a more cache-friendly order than the other, depending on how your nodes are laid out in memory.

What are the limitations of a queue? ›

These limitations of queues include the lack of random access to elements, limited capacity, and memory overhead. Despite these drawbacks, queues remain a useful tool in managing data and are widely used in a variety of applications.

What is the difference between stack queue and array? ›

Stack has a dynamic and fixed size. Queue can contain elements of different data type. Array contains elements of same data type. The stack can contain elements of the different data types.

Can we use stack as queue? ›

A Stack can be implemented using two queues. Let Stack to be implemented be 's' and queues used to implement are 'q1' and 'q2'.

What are the 6 applications of queue? ›

Queues have numerous applications, including job scheduling, printer spooling, breadth-first search, call centre management, CPU task management, and buffering. Queues are essential tools for efficiently managing and organizing data in a way that ensures tasks are executed in the correct order.

In what kind of situations is queuing most appropriate? ›

The following situations are examples of how queueing theory can be applied:
  • Waiting in line at a bank or a store.
  • Waiting for a customer service representative to answer a call after the call has been placed on hold.
  • Waiting for a train to come.
  • Waiting for a computer to perform a task or respond.
Jul 9, 2018

What is a real time example of a stack? ›

The stack data structure is a linear data structure that accompanies a principle known as LIFO (Last In First Out) or FILO (First In Last Out). Real-life examples of a stack are a deck of cards, piles of books, piles of money, and many more.

Which applications may use a stack? ›

Applications of stack:
  • Expression conversion such as infix to postfix, infix to prefix.
  • Expression evaluation.
  • Parsing well-formed parenthesis.
  • Decimal to binary conversion.
  • Reversing a string.
  • Storing function calls.

What are the advantages and disadvantages of stack and queue? ›

Comparison Table for Advantages & Disadvantages of Stack
AdvantagesDisadvantages
It does not get corrupted easilyRandom accessing of data is not possible
It does efficient management of functionsIt causes undesired termination
It has control and smart management of memoryIt has chances of stack overflow
4 more rows
Aug 17, 2021

What is a simple example of queue? ›

The real-world example of a queue is the ticket queue outside a cinema hall, where the person who enters first in the queue gets the ticket first, and the last person enters in the queue gets the ticket at last.

What are common queuing situations? ›

Some common queue situations are waiting in line for service in super-market or banks, waiting for results from computer and waiting in line for bus or commuter rail.

Is queue used in America? ›

Such a group of people is known as a queue (British usage) or line (American usage), and the people are said to be waiting or standing in a queue or in line, respectively.

What are the two 2 basic operations in the queue? ›

Basic Operations of Queue

Enqueue: Add an element to the end of the queue. Dequeue: Remove an element from the front of the queue.

What is the most used stack? ›

Top 7 Tech Stacks That Reign Software Development in 2023
  • MEAN Stack.
  • MERN Stack.
  • MEVN Stack.
  • LAMP Stack.
  • Serverless Stack.
  • Flutter for Web.
  • Ruby on Rails.

Is Kafka a queue? ›

Apache Kafka is not a traditional message queue. Kafka is a distributed messaging system that includes components of both a message queue and a publish-subscribe model. Kafka improves on the deficit of each of those traditional approaches allowing it to provide fault tolerant, high throughput stream processing.

Why is queue faster than list? ›

Queue is significantly faster than List , where memory accesses are 1 vs. n for List in this use case. I have a similar use case but I have hundreds of values and I will use Queue because it is an order of magnitude faster. A note about Queue being implemented on top of List : the key word is "implemented".

What is the purpose of using the queue algorithm? ›

This operation is used to check the status of the stack with the help of top pointer.

What are the drawbacks of queue using array? ›

Drawbacks of Queue Implementation Using Array

In Implementation of queue using array there is a wastage of memory. The available free space in the array can not be used for storing elements. In the above scenario free space is available in the array but when we try to insert element.

Which is easy stack or queue? ›

Stack implementation is easier whereas Queue implementation is tricky. Queue has variants like circular queue, priority queue, doubly ended queue, etc. In contrast, stack does not have variants.

Which data structure is most efficient for queue? ›

One of the most efficient ways to implement both a stack and a queue together is to use a deque (double-ended queue) data structure. A deque is a generalization of a queue that allows elements to be added and removed from both ends, making it a suitable data structure for implementing both a stack and a queue.

Why is stack faster? ›

The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it (a pointer/integer is simply incremented or decremented), while the heap has much more complex bookkeeping involved in an allocation or free.

What is worst case of queue? ›

Worst case

The operation of adding an element to the rear of the queue is known as enqueue, and the operation of removing an element from the front is known as dequeue.

Which operation is not allowed in queue? ›

Queue implementations generally do not allow insertion of null elements.

What are the pros and cons of priority queue? ›

The major advantage of using a priority queue is that you will be able to quickly access the highest priority item with a time complexity of just O(1). The only disadvantage of using Priority Queues are that the enqueue and dequeue operations are slow and have a time complexity of O(log n).

What are the advantages of stack? ›

Advantages of Stack
  • Allows you to manage data in a Last In First Out (LIFO) manner, which Linked list and array cannot.
  • When a function is called, its local variables are stored in a stack, which is automatically destroyed when the function returns.
  • When a variable is not used outside of that function, a stack is used.
Jan 18, 2023

What are the advantages of queue over array? ›

Advantages of Queue:
  • A large amount of data can be managed efficiently with ease.
  • Operations such as insertion and deletion can be performed with ease as it follows the first in first out rule.
  • Queues are useful when a particular service is used by multiple consumers.
Aug 21, 2022

Why use array over stack? ›

The stack can contain elements of different data types. The array contains elements of the same data type. There are limited number of operations can be performed on a stack: push, pop, peek, etc. It is rich in methods or operations that can be perform on it like sorting, traversing, reverse, push, pop, etc.

How do I convert a queue to a stack? ›

To construct a stack using two queues (q1, q2), we need to simulate the stack operations by using queue operations:
  1. push (E element) if q1 is empty, enqueue E to q1. if q1 is not empty, enqueue all elements from q1 to q2, then enqueue E to q1, and enqueue all elements from q2 back to q1.
  2. pop. dequeue an element from q1.
Mar 20, 2023

How many stacks does it take to make a queue? ›

In order to implement the Queue using Stack, we need to consider two stacks.

Can a stack be implemented using queue but then we need to use atleast? ›

A stack can be implemented using two queues. Let stack to be implemented be 'x' and queues used to implement be 'a' and 'b'. This method makes sure that the newly entered element is always at the front of 'a', so that pop operation just dequeues from 'a'.

What is the role of stacks and queues in problem solving? ›

Stacks are used to avoid recursion, a stack can replace the implicit/actual stack of functions called recursively. A queue is a linear data structure in which elements can be inserted only from one side of the list referred to as rear, and the elements can be deleted only from the other side referred to as the front.

What is the purpose of using stack class? ›

The Stack class provides the direct implementation of the stack data structure. However, it is recommended not to use it. Instead, use the ArrayDeque class (implements the Deque interface) to implement the stack data structure in Java.

Why do we need a stack representation? ›

Stack is crucial in the evaluation of several expressions, including postfix to infix, infix to prefix, and prefix to postfix. The implementation of recursion is its principal use. Recursion is utilized to more effectively tackle the issue.

Are stacks and queues more efficient? ›

Stacks and Queues are most efficient at insertion and removal, at O(1) or constant time. Using shift and unshift re-indexes the array, so at best we're in O(n) time, where the time grows as the length of the array grows. Push and pop only change the end of the array, so it works in constant time.

What is generally a stack used for implementing? ›

Stacks are used to implement functions, parsers, expression evaluation, and backtracking algorithms. A pile of books, a stack of dinner plates, a box of pringles potato chips can all be thought of examples of stacks. The basic operating principle is that last item you put in is first item you can take out.

What are the real world problems that can be solved using stacks? ›

5 Real-World Applications of the Stack Data Structure
  • Web Browsing History. One of the most common uses of the stack data structure is in web browsing history. ...
  • Undo/Redo Functionality. ...
  • Call Stack in Programming Languages. ...
  • Expression Evaluation in Mathematics. ...
  • Backtracking in Algorithms.
Apr 2, 2023

Why is stack invented? ›

Together with Klaus Samelson (also of TUM) he invented the stack machine (patented in 1957), a fundamental device for both theory and practice of programming. Stacks are THE way to handle recursive function calls and the dynamic runtime behavior of computer programs. Any modern microprocessor incorporates them.

What is the main advantage of using the stack for storing data in the program? ›

Advantages of Stack

Allows you to manage data in a Last In First Out (LIFO) manner, which Linked list and array cannot. When a function is called, its local variables are stored in a stack, which is automatically destroyed when the function returns.

What is a real-life example of a queue? ›

The ticket queue outside a cinema hall is a real-world example of a queue, where the person who enters first gets the ticket first, and the person who enters last gets the ticket last.

What are the 3 primary methods for a stack? ›

There are basically three operations that can be performed on stacks. They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack (peek or top).

What are the pros and cons of stack? ›

Comparison Table for Advantages & Disadvantages of Stack
AdvantagesDisadvantages
It has a low hardware RequirementUnable to Copy & Paste
Anyone with access can edit the programIt has a limited memory size
It does not get corrupted easilyRandom accessing of data is not possible
4 more rows
Aug 17, 2021

Are queues faster than stacks? ›

While queue and stack aren't wildly different in performance, they obviously induce a different node-visiting order. One of them may give a more cache-friendly order than the other, depending on how your nodes are laid out in memory.

References

Top Articles
Latest Posts
Article information

Author: Prof. Nancy Dach

Last Updated: 21/01/2024

Views: 6161

Rating: 4.7 / 5 (57 voted)

Reviews: 80% of readers found this page helpful

Author information

Name: Prof. Nancy Dach

Birthday: 1993-08-23

Address: 569 Waelchi Ports, South Blainebury, LA 11589

Phone: +9958996486049

Job: Sales Manager

Hobby: Web surfing, Scuba diving, Mountaineering, Writing, Sailing, Dance, Blacksmithing

Introduction: My name is Prof. Nancy Dach, I am a lively, joyous, courageous, lovely, tender, charming, open person who loves writing and wants to share my knowledge and understanding with you.