Data Structures with JavaScript — Chapter Three — Stacks and Queues

Apr 15, 2018 · 5 min read

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

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.

⚜️ The list

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

Lets do some code now…

🔅 Push

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

🔅 Pop

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

🔅 Peek

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

🔅 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

🔅 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}`

🔅 Traverse

`traverse( fn ) {  let current = this.top  while( current ) {   fn( current )   current = current.next  }}`

⚜️ The list

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

🔅 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   }}`

🔅 Dequeue

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

🔅 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}`

🔅 Traverse

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

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

Last important thing…

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.

Written by

_devblogs

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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade