Stack & Queue

❗️All the code snippets you will see below are just Pseudo code.

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

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

• Hackerrank — Data Structures