Web Dev With Bessem

Data Structures: stacks and Queues

Data Structures: stacks and Queues

bessim boujebli's photo
bessim boujebli
·

5 min read

Introduction

This article is part of my Data Structure series, where I try to explain each Data structure in a simplified way. In this part, I will walk you through Stacks and Queues, I put them together cause they are somewhat similar and simple too.

Stacks

First of all, what is a stack?

In real life, we use the term stack to describe some objects on top of each other. For example, this stack of boxes.

image.png

In this image, if I ask you to grab the third box you will need to take off the first one on the top and then the second until you get to the third. and that is the same principle that your laptop would use when working with stacks.

So stacks in Data Science are a list of similar data types. it's ordered and it's LIFO structure(Last In First Out). Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack.

A Stack has 3 main operations :

  • push: add an element on top of the stack
  • pop: remove the element on top of the stack
  • peek: return the last element on top of the stack

This image from Wikipedia should explain it just fine:

image.png

Application of a Stack

Now, you probably think, how can this data structure be useful I mean it only give u access to the last element of the stack u can only push or pop, an array or a linked List sound so much better, I mean they give so much more power, well ye.. but you don't always want to have a lot of power method and complexities. to demonstrate how useful the Stack can be I will give some Application that you use every day and it's built with stacks.

  • in the text editor when you press the ctr+z to cancel or undo an action that is using stacks
  • in the browser when you press the button to go to the previous page
  • Also a Compiler use it to parse arithmetic expression

Performance of a Stack

  • Insert --> O(1) ==> so fast
  • Delete --> O(1) ==> so fast
  • Search --> O(n) ==> slow

Queues

image.png

What is a Queue ??

Queues are ordered linear data structure just like a stack however it's accessible from both ends and it follows First-In-First-Out methodology. Adding an item is called enqueue and you add the item at the end of the data sequence, you can't add an item at the start of the Queue. Removing an item is called dequeue as you might guess ;).

image.png

A Queue has 5 main operations :

  • Enqueue(): Add an element to the end of the queue.

  • Dequeue(): Remove an element from the front of the queue.

  • IsEmpty(): Check if the queue is empty.

  • IsFull(): Check if the queue is full.

  • Peek(): Get the value of the front of the queue without removing it.

Application of a Queue

  • requests on a single shared resource, like a printer.
  • CPU tasks. The CPU uses it to Schedule his tasks, the tasks are waiting in a queue to be handled by the CPU.
  • Queues are used to implement some algorithms too like Breadth-First Search, BBF.

Performance of a Stack

  • Insert --> O(1) ==> so fast
  • Delete --> O(1) ==> so fast
  • Search --> O(n) ==> slow

This was all for Queues and Stacks, they are fairly simple Data Structures but they are important.

Hashnode2Articles1Weekdata structuresqueuestack