How do you implement a Stack and a Queue in JavaScript

Question

What is the best way to implement a Stack and a Queue in JavaScript   I m looking to do the shunting-yard algorithm and I m going to need these data-structures

User · Accepted Answer

var stack       stack push 2            stack is now  2  stack push 5            stack is now  2  5  var i   stack pop       stack is now  2  alert i                 displays 5  var queue       queue push 2              queue is now  2  queue push 5              queue is now  2  5  var i   queue shift       queue is now  5  alert i                   displays 2   taken from  9 javascript tips you may not know

User · Answer

If you wanted to make your own data structures  you could build your own   var Stack   function      this top   null    this size   0      var Node   function data     this data   data    this previous   null      Stack prototype push   function data      var node   new Node data      node previous   this top    this top   node    this size    1    return this top      Stack prototype pop   function       temp   this top    this top   this top previous    this size -  1    return temp       And for queue   var Queue   function       this first   null    this size   0      var Node   function data      this data   data    this next   null      Queue prototype enqueue   function data      var node   new Node data      if   this first       this first   node      else       n   this first      while  n next          n   n next            n next   node         this size    1    return node      Queue prototype dequeue   function       temp   this first    this first   this first next    this size -  1    return temp

User · Answer

A little late answer but i think this answer should be here  Here is an implementation of Queue with O 1  enqueue and O 1  dequeue using the sparse Array powers  Sparse Arrays in JS are mostly disregarded but they are in fact a gem and we should put their power in use at some critical tasks  So here is a skeleton Queue implementation which extends the Array type and does it s things in O 1  all the way   x000D   x000D  class Queue extends Array     constructor        super       Object defineProperty this  head    value         0                                         writable      true                                         enumerable    false                                         configurable  false                                                 enqueue x        this push x       return this        dequeue         var first      return this head  lt  this length     first   this this head                                         delete this this head                                           first                                                                             void 0     perfect undefined       peek         return this this head          var q   new Queue    console log q dequeue             doesn t break console log q enqueue 10          add 10 console log q enqueue  DIO        add  DIO   Last In Line cCc R J DIO reis cCc  console log q                     display q console log q dequeue             lets get the first one in the line console log q dequeue             lets get DIO out from the line x000D   as-console-wrapper     max-height  100   important    x000D   x000D   x000D   So do we have a potential memory leak here  No i don t think so  JS sparse arrays are non contiguous  Accordingly deleted items shouln t be a part of the array s memory footprint  Let the GC do it s job for you  It s free of charge  One potential problem is that  the length property grows indefinitely as you keep enqueueing items to the queue  However still one may implement an auto refreshing  condensing  mechanism to kick in once the length reaches to a certain value

User · Answer

You can use your own customize class based on the concept  here the code snippet which you can use to do the stuff         Stack implementation in JavaScript       function Stack       this top   null    this count   0     this getCount   function         return this count         this getTop   function         return this top         this push   function data        var node           data  data        next  null            node next   this top      this top   node       this count           this peek   function         if  this top     null          return null        else         return this top data               this pop   function         if  this top     null          return null        else         var out   this top        this top   this top next        if  this count  gt  0            this count--                 return out data               this displayAll   function         if  this top     null          return null        else         var arr   new Array           var current   this top          console log current         for  var i   0  i  lt  this count  i              arr i    current data          current   current next                 return arr                and to check this use your console and try these line one by one    gt  gt  var st   new Stack      gt  gt  st push  BP      gt  gt  st push  NK      gt  gt  st getTop      gt  gt  st getCount      gt  gt  st displayAll      gt  gt  st pop      gt  gt  st displayAll      gt  gt  st getTop      gt  gt  st peek

User · Answer

If you understand stacks with push   and pop   functions  then queue is just to make one of these operations in the oposite sense  Oposite of push   is unshift   and oposite of pop   es shift    Then     classic stack var stack       stack push  first       push inserts at the end stack push  second    stack push  last    stack pop      pop takes the  last  element    One way to implement queue is to insert elements in the oposite sense than a stack var queue       queue unshift  first      unshift inserts at the beginning queue unshift  second    queue unshift  last    queue pop       first     other way to do queues is to take the elements in the oposite sense than stack var queue       queue push  first      push  as in the stack inserts at the end queue push  second    queue push  last    queue shift      but shift takes the  first  element

User · Answer

var x   10     var y   11     var Queue   new Array      Queue unshift x     Queue unshift y      console log Queue       Output  11  10     Queue pop     console log Queue       Output  11

User · Answer

Here is my Implementation of Stacks   function Stack     this dataStore       this top   0  this push   push  this pop   pop  this peek   peek  this clear   clear  this length   length    function push element    this dataStore this top      element    function peek     return this dataStore this top-1     function pop     return this dataStore --this top     function clear     this top   0    function length     return this top     var s   new Stack    s push  David    s push  Raymond    s push  Bryan    console log  length      s length     console log s peek

User · Answer

The regular Array structure in Javascript is a Stack  first in  last out  and can also be used as a Queue  first in  first out  depending on the calls you make   Check this link to see how to make an Array act like a Queue   Queues

User · Answer

There are quite a few ways in which you can implement Stacks and Queues in Javascript  Most of the answers above are quite shallow implementations and I would try to implement something more readable  using new syntax features of es6  and robust   Here s the stack implementation   class Stack     constructor    items       this  items           if items length gt 0        items forEach item   gt  this  items push item            push    items         push item to the stack      items forEach item   gt  this  items push item         return this  items          pop count 0         pull out the topmost item  last item  from stack     if count   0        return this  items pop        else        return this  items splice  -count  count          peek           see what s the last item in stack     return this  items this  items length-1         size          no  of items in stack     return this  items length        isEmpty           return whether the stack is empty or not     return this  items length  0        toArray        return this  items          And this is how you can use the stack    let my stack   new Stack 1 24 4       1  24  4  my stack push 23     1  24  4  23  my stack push 1 2 342      1  24  4  23  1  2  342  my stack pop       1  24  4  23  1  2  my stack pop 3     1  24  4  my stack isEmpty      false my stack size      3   If you would like to see the detailed description about this implementation and how it can be further improved  you can read here   http   jschap com data-structures-in-javascript-stack   Here s the code for queue implementation in es6    class Queue   constructor    items        initialize the items in queue    this  items            enqueuing the items passed to the constructor    this enqueue    items        enqueue    items         push items into the queue     items forEach  item   gt  this  items push item        return this  items         dequeue count 1         pull out the first item from the queue     this  items splice 0 count       return this  items         peek          peek at the first item from the queue     return this  items 0         size          get the length of queue     return this  items length        isEmpty          find whether the queue is empty or no     return this  items length   0         Here s  how you can use this implementation   let my queue   new Queue 1 24 4       1  24  4  my queue enqueue 23     1  24  4  23  my queue enqueue 1 2 342      1  24  4  23  1  2  342  my queue dequeue       24  4  23  1  2  342  my queue dequeue 3     1  2  342  my queue isEmpty      false my queue size      3   To go through the complete tutorial of how these data structures have been implemented and how can these further be improved  you may want to go through the  Playing with data structures in javascript  series at jschap com   Here s the links for queues - http   jschap com playing-data-structures-javascript-queues

User · Answer

The stack implementation is trivial as explained in the other answers   However  I didn t find any satisfactory answers in this thread for implementing a queue in javascript  so I made my own   There are three types of solutions in this thread    Arrays - The worst solution  using array shift   on a large array is very inefficient  Linked lists - It s O 1  but using an object for each element is a bit excessive  especially if there are a lot of them and they are small  like storing numbers  Delayed shift arrays - It consists of associating an index with the array  When an element is dequeued  the index moves forward  When the index reaches the middle of the array  the array is sliced in two to remove the first half    Delayed shift arrays are the most satisfactory solution in my mind  but they still store everything in one large contiguous array which can be problematic  and the application will stagger when the array is sliced   I made an implementation using linked lists of small arrays  1000 elements max each   The arrays behave like delayed shift arrays  except they are never sliced  when every element in the array is removed  the array is simply discarded   The package is on npm with basic FIFO functionality  I just pushed it recently  The code is split into two parts   Here is the first part      Queue contains a linked list of Subqueue    class Subqueue  lt T gt      public full         return this array length  gt   1000         public get size         return this array length - this index         public peek    T       return this array this index          public last    T       return this array this array length-1          public dequeue    T       return this array this index            public enqueue elem  T        this array push elem          private index  number   0    private array  T             public next  Subqueue lt T gt    null      And here is the main Queue class   class Queue lt T gt      get length         return this  size         public push    elems  T          for  let elem of elems          if  this bottom full              this bottom   this bottom next   new Subqueue lt T gt                   this bottom enqueue elem              this  size    elems length         public shift    T       if  this  size     0          return undefined             const val   this top dequeue        this  size--      if  this  size  gt  0  amp  amp  this top size     0  amp  amp  this top full               Discard current subqueue and point top to the one after       this top   this top next            return val         public peek    T       return this top peek           public last    T       return this bottom last           public clear         this bottom   this top   new Subqueue        this  size   0         private top  Subqueue lt T gt    new Subqueue      private bottom  Subqueue lt T gt    this top    private  size  number   0      Type annotations    X  can easily be removed to obtain ES6 javascript code

User · Answer

If you re looking for ES6 OOP implementation of Stack and Queue data-structure with some basic operations  based on linked lists  then it may look like this   Queue js  import LinkedList from     linked-list LinkedList    export default class Queue     constructor         this linkedList   new LinkedList           isEmpty         return  this linkedList tail         peek         if   this linkedList head          return null             return this linkedList head value         enqueue value        this linkedList append value          dequeue         const removedHead   this linkedList deleteHead        return removedHead   removedHead value   null         toString callback        return this linkedList toString callback           Stack js  import LinkedList from     linked-list LinkedList    export default class Stack     constructor         this linkedList   new LinkedList                     return  boolean          isEmpty         return  this linkedList tail                   return             peek         if   this linkedList tail          return null             return this linkedList tail value                   param     value         push value        this linkedList append value                    return             pop         const removedTail   this linkedList deleteTail        return removedTail   removedTail value   null                   return               toArray         return this linkedList        toArray          map linkedListNode   gt  linkedListNode value         reverse                     param  function   callback        return  string          toString callback        return this linkedList toString callback           And LinkedList implementation that is used for Stack and Queue in examples above may be found on GitHub here

User · Answer

Javascript array shift   is slow especially when holding many elements  I know two ways to implement queue with amortized O 1  complexity    First is by using circular buffer and table doubling  I have implemented this before  You can see my source code here  https   github com kevyuu rapid-queue  The second way is by using two stack  This is the code for queue with two stack  function createDoubleStackQueue     var that       var pushContainer       var popContainer        function moveElementToPopContainer         while  pushContainer length    0             var element   pushContainer pop            popContainer push element            that push   function element        pushContainer push element       that shift   function         if  popContainer length     0            moveElementToPopContainer              if  popContainer length     0            return null        else           return popContainer pop              that front   function         if  popContainer length     0            moveElementToPopContainer              if  popContainer length     0            return null            return popContainer popContainer length - 1       that length   function         return pushContainer length   popContainer length      that isEmpty   function         return  pushContainer length   popContainer length      0      return that     This is performance comparison using jsPerf  CircularQueue shift   vs Array shift    http   jsperf com rapidqueue-shift-vs-array-shift  As you can see it is significantly faster with large dataset

User · Answer

Construct a Queue using two Stacks      O 1  for both enqueue and dequeue operations    class Queue     constructor         this s1          in     this s2          out        enqueue val        this s1 push val          dequeue         if  this s2 length     0          this  move               return this s2 pop       return undefined if empty         move         while  this s1 length          this s2 push this s1 pop

User · Answer

Create a pair of classes that provide the various methods that each of these data structures has  push  pop  peek  etc    Now implement the methods   If you re familiar with the concepts behind stack queue  this should be pretty straightforward  You can implement the stack with an array  and a queue with a linked list  although there are certainly other ways to go about it   Javascript will make this easy  because it is weakly typed  so you don t even have to worry about generic types  which you d have to do if you were implementing it in Java or C

User · Answer

My implementation of Stack and Queue using Linked List   x000D   x000D     Linked List x000D  function Node data    x000D    this data   data  x000D    this next   null  x000D    x000D   x000D     Stack implemented using LinkedList x000D  function Stack     x000D    this top   null  x000D    x000D   x000D  Stack prototype push   function data    x000D    var newNode   new Node data   x000D   x000D    newNode next   this top    Special attention x000D    this top   newNode  x000D    x000D   x000D  Stack prototype pop   function     x000D    if  this top     null    x000D      var topItem   this top data  x000D      this top   this top next  x000D      return topItem  x000D      x000D    return null  x000D    x000D   x000D  Stack prototype print   function     x000D    var curr   this top  x000D    while  curr    x000D      console log curr data   x000D      curr   curr next  x000D      x000D    x000D   x000D     var stack   new Stack    x000D     stack push 3   x000D     stack push 5   x000D     stack push 7   x000D     stack print    x000D   x000D     Queue implemented using LinkedList x000D  function Queue     x000D    this head   null  x000D    this tail   null  x000D    x000D   x000D  Queue prototype enqueue   function data    x000D    var newNode   new Node data   x000D   x000D    if  this head     null    x000D      this head   newNode  x000D      this tail   newNode  x000D      else   x000D      this tail next   newNode  x000D      this tail   newNode  x000D      x000D    x000D   x000D  Queue prototype dequeue   function     x000D    var newNode  x000D    if  this head     null    x000D      newNode   this head data  x000D      this head   this head next  x000D      x000D    return newNode  x000D    x000D   x000D  Queue prototype print   function     x000D    var curr   this head  x000D    while  curr    x000D      console log curr data   x000D      curr   curr next  x000D      x000D    x000D   x000D  var queue   new Queue    x000D  queue enqueue 3   x000D  queue enqueue 5   x000D  queue enqueue 7   x000D  queue print    x000D  queue dequeue    x000D  queue dequeue    x000D  queue print    x000D   x000D   x000D

User · Answer

you can use WeakMaps for implementing private property in ES6 class and benefits of String propeties and methods in JavaScript language like below   const  items   new WeakMap     class Stack     constructor          items set this            push obj       items get this  push obj      pop       const L    items get this  length    if L   0      throw new Error  Stack is empty      return  items get this  pop       peek       const items    items get this     if items length     0      throw new Error   Stack is empty      return items items length-1      get count       return  items get this  length       const stack   new Stack       now in console    stack push  a     stack push 1    stack count     gt  2   stack peek      gt  1   stack pop       gt  1   stack pop       gt   a    stack count     gt  0   stack pop       gt  Error Stack is empty

User · Answer

Here is a fairly simple queue implementation with two aims    Unlike array shift    you know this dequeue method takes constant time  O 1    To improve speed  this approach uses many fewer allocations than the linked-list approach    The stack implementation shares the second aim only      Queue function Queue             this q   new Array 5           this first   0          this size   0    Queue prototype enqueue   function a            var other          if  this size    this q length                    other   new Array this size 2                   for  var i   0  i  lt  this size  i                              other i    this q  this first i  this size                                     this first   0                  this q   other                    this q  this first this size  this q length    a          this size       Queue prototype dequeue   function             if  this size    0  return undefined          this size--          var ret   this q this first           this first    this first 1  this q length          return ret     Queue prototype peek   function     return this size  gt  0   this q this first    undefined     Queue prototype isEmpty   function     return this size    0         Stack function Stack             this s   new Array 5           this size   0    Stack prototype push   function a            var other      if  this size    this s length                other   new Array this s length 2               for  var i   0  i  lt  this s length  i    other i    this s i               this s   other            this s this size      a     Stack prototype pop   function             if  this size    0  return undefined          return this s --this size      Stack prototype peek   function     return this size  gt  0   this s this size-1    undefined

User · Answer

No Array s        Javascript stack linked list data structure  no array   function node value  noderef        this value   value      this next   noderef    function stack         this push   function  value            this next   this first          this first   new node value  this next             this pop   function              var popvalue   this first value          this first   this first next          return popvalue            this hasnext   function              return this next    undefined            this isempty   function              return this first    undefined              Javascript stack linked list data structure  no array  function node value  noderef        this value   value      this next   undefined    function queue         this enqueue   function  value            this oldlast   this last          this last   new node value           if  this isempty                this first   this last          else             this oldlast next   this last            this dequeue   function              var queuvalue   this first value          this first   this first next          return queuvalue            this hasnext   function              return this first next    undefined            this isempty   function              return this first    undefined

User · Answer

Arrays   Stack   var stack          put value on top of stack stack push 1      remove value from top of stack var value   stack pop      Queue   var queue          put value on end of queue queue push 1      Take first value from queue var value   queue shift

User · Answer

Here is the linked list version of a queue that also includes the last node  as suggested by  perkins and as is most appropriate      QUEUE Object Definition  var Queue   function       this first   null    this last   null    this size   0      var Node   function data      this data   data    this next   null      Queue prototype enqueue   function data      var node   new Node data      if   this first      for empty list first and last are the same     this first   node      this last   node      else      otherwise we stick it on the end     this last next node      this last node         this size    1    return node      Queue prototype dequeue   function       if   this first    check for empty list     return null     temp   this first     grab top of list   if  this first  this last        this last null      when we need to pop the last one       this first   this first next     move top of list down   this size -  1    return temp

User · Answer

Seems to me that the built in array is fine for a stack  If you want a Queue in TypeScript here is an implementation         A Typescript implementation of a queue      export default class Queue      private queue         private offset   0     constructor array                Init the queue using the contents of the array     for  const item of array          this enqueue item                          returns  number  the length of the queue          public getLength    number       return  this queue length - this offset                    returns  boolean  true if the queue is empty  and false otherwise          public isEmpty    boolean       return  this queue length     0                   Enqueues the specified item             param item - the item to enqueue         public enqueue item        this queue push item                    Dequeues an item and returns it  If the queue is empty  the value        code null  is returned             returns  any          public dequeue    any          if the queue is empty  return immediately     if  this queue length     0          return null                store the item at the front of the queue     const item   this queue this offset           increment the offset and remove the free space if necessary     if    this offset   2  gt   this queue length          this queue   this queue slice this offset         this offset   0                return the dequeued item     return item                   Returns the item at the front of the queue  without dequeuing it        If the queue is empty then   code null  is returned             returns  any          public peek    any       return  this queue length  gt  0   this queue this offset    null            And here is a Jest test for it  it  Queue        gt      const queue   new Queue      expect queue getLength    toBe 0     expect queue peek    toBeNull      expect queue dequeue    toBeNull       queue enqueue 1     expect queue getLength    toBe 1     queue enqueue 2     expect queue getLength    toBe 2     queue enqueue 3     expect queue getLength    toBe 3      expect queue peek    toBe 1     expect queue getLength    toBe 3     expect queue dequeue    toBe 1     expect queue getLength    toBe 2      expect queue peek    toBe 2     expect queue getLength    toBe 2     expect queue dequeue    toBe 2     expect queue getLength    toBe 1      expect queue peek    toBe 3     expect queue getLength    toBe 1     expect queue dequeue    toBe 3     expect queue getLength    toBe 0      expect queue peek    toBeNull      expect queue dequeue    toBeNull          Hope someone finds this useful    Cheers   Stu

User · Answer

Regards   In Javascript the implementation of stacks and queues is as follows   Stack  A stack is a container of objects that are inserted and removed according to the last-in-first-out  LIFO  principle    Push  Method adds one or more elements to the end of an array and returns the new length of the array  Pop  Method removes the last element from an array and returns that element    Queue  A queue is a container of objects  a linear collection  that are inserted and removed according to the first-in-first-out  FIFO  principle    Unshift  Method adds one or more elements to the beginning of an array  Shift  The method removes the first element from an array     x000D   x000D  let stack       x000D   stack push 1     1  x000D   stack push 2     1 2  x000D   stack push 3     1 2 3  x000D    x000D  console log  It was inserted 1 2 3 in stack       stack   x000D   x000D  stack pop       1 2  x000D  console log  Item 3 was removed       stack   x000D   x000D  stack pop       1  x000D  console log  Item 2 was removed       stack   x000D   x000D   x000D  let queue       x000D  queue push 1     1  x000D  queue push 2     1 2  x000D  queue push 3     1 2 3  x000D   x000D  console log  It was inserted 1 2 3 in queue       queue   x000D   x000D  queue shift       2 3  x000D  console log  Item 1 was removed       queue   x000D   x000D  queue shift       3  x000D  console log  Item 2 was removed       queue   x000D   x000D   x000D

User · Answer

Or else you can use two arrays to implement queue data structure   var temp stack   new Array    var stack   new Array     temp stack push 1   temp stack push 2   temp stack push 3     If I pop the elements now then the output will be 3 2 1  But we want FIFO structure so you can do the following   stack push temp stack pop     stack push temp stack pop     stack push temp stack pop      stack pop      Pop out 1 stack pop      Pop out 2 stack pop      Pop out 3

User · Answer

------------------------------------------------------------------   Defining Stack Operations using Closures in Javascript  privacy and  state of stack operations are maintained    author Arijt Basu  Log  Sun Dec 27  2015  3 25PM  -------------------------------------------------------------------      var stackControl   true  var stack    function array            array                 --Define the max size of the stack         var MAX SIZE   5           function isEmpty                 if  array length  lt  1  console log  Stack is empty                       isEmpty             return                push  function ele                    if  array length  lt  MAX SIZE                        array push ele                      return array                    else                       console log  Stack Overflow                                                pop  function                     if  array length  gt  1                        array pop                        return array                    else                       console log  Stack Underflow                                                               var list   5         console log stack list   if  stackControl        console log stack pop         console log stack push 3        console log stack push 2        console log stack pop         console log stack push 1        console log stack pop         console log stack push 38        console log stack push 22        console log stack pop         console log stack pop         console log stack push 6        console log stack pop         End of STACK Logic     Defining Queue operations    var queue    function array        array           var reversearray        --Define the max size of the stack     var MAX SIZE   5       function isEmpty             if  array length  lt  1  console log  Queue is empty               isEmpty         return           insert  function ele                if  array length  lt  MAX SIZE                    array push ele                  reversearray   array reverse                    return reversearray                else                   console log  Queue Overflow                                    delete  function                 if  array length  gt  1                      reversearray   array reverse                    array pop                    return array                else                   console log  Queue Underflow                                           console log queue insert 5   console log queue insert 3   console log queue delete 3

User · Answer

Javascript has push and pop methods  which operate on ordinary Javascript array objects  For queues  look here  http   safalra com web-design javascript queues   Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object  Although this is a simple way to implement queues  it is very inefficient for large queues     because of the methods operate on arrays  the shift and unshift methods move every element in the array each time they are called  Queue js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time  As a result  for larger queues  it can be significantly faster than using arrays

[javascript] How do you implement a Stack and a Queue in JavaScript?

Examples related to javascript

Examples related to data-structures

Examples related to stack

Examples related to queue