_devblogs
Published in

_devblogs

DS with JS — Stack & Queue

Data Structures with JavaScript — Chapter Three — Stacks and Queues

❗️All the code snippets you will see below are just Pseudo code. If you want to see working code — click here

Prerequisites

Before proceeding further, make sure you have gone through both of these posts first because I am using Linked Lists to implement Stack and Queue rather than Arrays.

  1. DS with JS — Linked Lists
  2. DS with JS — Linked Lists — II

Why to use Linked Lists while implementing Stacks and Queues ?

I found some lines over this —

…because linked lists store data elements in linear sequences, they can be used to give alternative implementations of stacks and queues. One advantage to using linked lists is that we don’t have to worry about filling up something like an array — we can just keep allocating cells as long as we need to (unless we run out of memory). Implementing a stack using a linked list is particularly easy because all accesses to a stack are at the top. One end of a linked list, the beginning, is always directly accessible. We should therefore arrange the elements so that the top element of the stack is at the beginning of the linked list, and the bottom element of the stack is at the end of the linked list. We can represent an empty stack with null…

another reason is that you will able to practice linked-lists while implementing stacks and queues which will give you the understanding of how Stacks and Queues works while making you strong with linked-lists.

read full article over here..

Lets’ begin!!

Stack Definition
This is how stack works…

Core

⚜️ The list

  1. Push
  2. Pop
  3. Peek
  4. Reverse
  5. Length
  6. Search
  7. IsEmpty
  8. Traverse

Lets do some code now…

Initial Stack

🔅 Push

push( item ){
let node = new Node( item )
if( this.top ) {
node.next = this.top
this.top = node
} else {
this.top = node
}
}
Push Operation

🔅 Pop

pop() {
if( this.top ) {
let itemToPop = this.top
this.top = this.top.next
return itemToPop.data
} else {
log('Stack is empty!')
return false;
}
}
Pop Operation

🔅 Peek

peek() {
if( this.top ) {
return this.top.data
} else {
return null
}
}
Peek Operation

🔅 Reverse

reverse() {
let current = this.top
let prev = null;
while( current ) {
let next = current.next
current.next = prev
prev = current
current = next
}
this.top = prev
}

⚠️ It is same as reversing a Singly-Linked List

Reverse Operation

🔅 Length, Search & IsEmpty

length() {
let current = this.top
let counter = 0
while( current ) {
counter++
current = current.next
}
return counter
}
search( item ) {
let current = this.top
while( current ) {
if( current.data === item ) return true
current = current.next
}
return false
}
isEmpty() {
return this.length > 1
}
Length, Search & IsEmpty Operation

🔅 Traverse

traverse( fn ) {
let current = this.top
while( current ) {
fn( current )
current = current.next
}
}
Traverse Operation
Queue Definition
This is how Queue works…

Core

⚜️ The list

  1. Enqueue
  2. Dequeue
  3. Length
  4. Peek
  5. IsEmpty
  6. Traverse
Initial Queue

🔅 Enqueue

enqueue( item ) {
let node = new Node( item )
if( !this.head ) {
this.head = node
this.tail = node
} else {
this.tail.next = node
this.tail = node
}
}
Enqueue Operation

🔅 Dequeue

dequeue() {
if( !this.head ) {
return 'No item'
} else {
let itemToPop = this.head
this.head = this.head.next
return itemToPop
}
}
Dequeue Operation

🔅 Length, Peek & IsEmpty

length() {
let current, counter
[ current, counter ] = [ this.head, 0 ]
while( current ) {
counter++
current = current.next
}
return counter
}
peek() {
if( this.head ) {
return this.head.data
} else {
return 'Empty'
}
}
isEmpty() {
return this.length() < 1
}
Length, Peek & IsEmpty Operation

🔅 Traverse

traverse( fn ) {
let current = this.head
while( current ) {
fn( current )
current = current.next
}
}
Traverse Operation

You can implement any operation over these stacks and queues which you can implement using Linked Lists.

Practice

Last important thing…

For details — http://bigocheatsheet.com/

About this post

This post is the third instalment to its series “DS with JS”. There will be more in this series. Next will be on next Monday Morning. Stay tuned!

That’s It

Happy Coding !!

🎧 Listening to “Touch — Matia Cupelli” . Sadness, broken heart, piano & dreams.. only thing missing is — this music…

If you like this article, please give it some claps 👏 and share it! If you do not like this post or have any type of questions regarding anything that i mentioned in this post. Feel free to ask me. Just post an issue in my “Ask Me Anything” by clicking here.

For more like this, follow me on Medium or Twitter. To ask a Question visit this link. More about me on my website.

--

--

--

Stories for Full-Stack Web developers which help them in pursuing their goals as a developer, mastering the modern web technologies and *hacking the web.

Recommended from Medium

A brief toe-dip into Three.js

A guide to JavaScript variable hoisting 🚩 with let and const

VueJS Datatables GitHub 2022

Configure React to Import SVGs as React Components.

HTML-The Skeleton(formatting)

Laravel Livewire | CRUD Application Tutorial

JavaScript Code Broken Down into AST

React Cocktail Recipes

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Gaurav Mehla

Gaurav Mehla

Software engineer & Web hacker. Spent 30+% of life on playing with JS

More from Medium

Implementing Graphs with JavaScript

A Directed Graph

Adding Promise Support to a Node.js Library

Dockerize React App

Homemade Caching and Pruning in JavaScript