Implement Stack using Two Queues

Question

A similar question was asked earlier there  but the question here is the reverse of it  using two queues as a stack   The question     Given two queues with their standard operations  enqueue  dequeue  isempty  size   implement a stack with its standard operations  pop  push  isempty  size    There should be two versions of the solution    Version A  The stack should be efficient when pushing an item  and Version B  The stack should be efficient when popping an item    I am interested in the algorithm more than any specific language implementations   However  I welcome solutions expressed in languages which I am familiar  java c  python vb javascript php

User · Answer

The easiest  and maybe only  way of doing this is by pushing new elements into the empty queue  and then dequeuing the other and enqeuing into the previously empty queue  With this way the latest is always at the front of the queue  This would be version B  for version A you just reverse the process by dequeuing the elements into the second queue except for the last one   Step 0    Stack   --- --- --- --- ---                         --- --- --- --- ---   Queue A                Queue B  --- --- --- --- ---    --- --- --- --- ---                                                --- --- --- --- ---    --- --- --- --- ---    Step 1    Stack   --- --- --- --- ---    1                    --- --- --- --- ---   Queue A                Queue B  --- --- --- --- ---    --- --- --- --- ---    1                                           --- --- --- --- ---    --- --- --- --- ---    Step 2    Stack   --- --- --- --- ---    2   1                --- --- --- --- ---   Queue A                Queue B  --- --- --- --- ---    --- --- --- --- ---                           2   1                --- --- --- --- ---    --- --- --- --- ---    Step 3    Stack   --- --- --- --- ---    3   2   1            --- --- --- --- ---   Queue A                Queue B  --- --- --- --- ---    --- --- --- --- ---    3   2   1                                   --- --- --- --- ---    --- --- --- --- ---

User · Answer

import java util Deque  import java util LinkedList  import java util Queue   public class ImplementationOfStackUsingTwoQueue        private static Deque lt Integer gt  inboxQueue   new LinkedList lt  gt         private static Queue lt Integer gt  outboxQueue   new LinkedList lt  gt              public void pushInStack Integer val           inboxQueue add val                  public void popFromStack                     if outboxQueue isEmpty                 while  inboxQueue isEmpty                     outboxQueue add inboxQueue pollLast                                            public static void main String   args                     ImplementationOfStackUsingTwoQueue obj   new ImplementationOfStackUsingTwoQueue                     obj pushInStack 1           obj pushInStack 2           obj pushInStack 3           obj pushInStack 4           obj pushInStack 5           System out println  quot After pushing the values in Queue quot    inboxQueue                    obj popFromStack            System out println  quot After popping the values from Queue quot    outboxQueue

User · Answer

import java util LinkedList  import java util Queue   class MyStack       Queue lt Integer gt  queue1   new LinkedList lt Integer gt         Queue lt Integer gt  queue2   new LinkedList lt Integer gt             Push element x onto stack      public void push int x            if isEmpty                 queue1 offer x            else              if queue1 size   gt 0                   queue2 offer x                   int size   queue1 size                    while size gt 0                       queue2 offer queue1 poll                         size--                                 else if queue2 size   gt 0                   queue1 offer x                   int size   queue2 size                    while size gt 0                       queue1 offer queue2 poll                         size--                                                          Removes the element on top of the stack      public void pop             if queue1 size   gt 0               queue1 poll             else if queue2 size   gt 0               queue2 poll                            Get the top element  You can make it more perfect just example     public int top            if queue1 size   gt 0               return queue1 peek             else if queue2 size   gt 0               return queue2 peek                      return 0                Return whether the stack is empty      public boolean isEmpty             return queue1 isEmpty    amp  amp  queue2 isEmpty

User · Answer

Here s my answer - where the  pop  is inefficient  Seems that all algorithms that come immediately to mind have N complexity  where N is the size of the list  whether you choose to do work on the  pop  or do work on the  push   The algorithm where lists are traded back and fourth may be better    as a size calculation is not needed  although you still need to loop and compare with empty   you can prove this algorithm cannot be written faster than N by noting that the information about the last element in a queue is only available through knowing the size of the queue  and that you must destroy data to get to that element  hence the 2nd queue   The only way to make this faster is to not to use queues in the first place   from data structures import queue  class stack object       def   init   self           q1  queue          q2  queue  only contains one item at most  a temp var   bad        def push self  item           q1 enque item   just stick it in the first queue        Pop is inefficient     def pop self             spin  the queues until q1 is ready to pop the right value           for N 0 to self size-1             q2 enqueue q1 dequeue              q1 enqueue q2 dequeue          return q1 dequeue         property     def size self           return q1 size   q2 size       property     def isempty self           if self size  gt  0             return True         else            return False

User · Answer

As has been mentioned  wouldn t a single queue do the trick  It s probably less practical but is a bit slicker   push x   enqueue x  for queueSize - 1     enqueue dequeue     pop x   dequeue

User · Answer

include  lt bits stdc   h gt  using namespace std  queue lt int gt Q  stack lt int gt Stk  void PRINT stack lt int gt ss   queue lt int gt qq        while  ss size               cout  lt  lt  ss top    lt  lt                ss pop              puts          while  qq size               cout  lt  lt  qq front    lt  lt                qq pop              puts   n----------------------------------      void POP         queue lt int gt Tmp       while  Q size    gt  1             Tmp push  Q front               Q pop              cout  lt  lt  Q front    lt  lt       lt  lt  Stk top    lt  lt  endl      Q pop     Stk pop         Q   Tmp     void PUSH int x         Q push x       Stk push x     int main         while  true             string typ           cin  gt  gt  typ           if  typ     push                  int x               cin  gt  gt  x              PUSH x             else POP            PRINT Stk Q

User · Answer

Python Code Using Only One Queue     class Queue object       def   init   self           self items        def enqueue self item           self items insert 0 item      def dequeue self           if not self isEmpty                 return  self items pop       def isEmpty self           return  self items         def size self           return len self items     class stack object           def   init   self               self q1  Queue             def push self  item               self q1 enqueue item             def pop self               c self q1 size               while c gt 1                   self q1 enqueue self q1 dequeue                    c- 1             return self q1 dequeue              def size self               return self q1 size              def isempty self               if self size  gt  0                 return True             else                 return False

User · Answer

Here s my solution    Concept Behind   push struct Stack  S int data   This function enqueue first element in Q1 and rest in Q2 pop struct Stack  S   if Q2 is not empty the transfers all elem s into Q1 and return the last elem in Q2 else which means Q2 is empty   transfers all elem s into Q2 and returns the last elem in Q1  Efficiency Behind   push struct Stack S int data   O 1   since single enqueue per data pop struct Stack  S   O n   since tranfers worst n-1 data per pop    include lt stdio h gt   include lt stdlib h gt  struct Queue      int front      int rear      int  arr      int size         struct Stack       struct Queue  Q1      struct Queue  Q2         struct Queue  Qconstructor int capacity        struct Queue  Q malloc sizeof struct Queue        Q- gt front Q- gt rear -1      Q- gt size capacity      Q- gt arr malloc Q- gt size sizeof int        return Q        int isEmptyQueue struct Queue  Q        return  Q- gt front  -1         int isFullQueue struct Queue  Q        return   Q- gt rear 1    Q- gt size   Q- gt front         void enqueue struct Queue  Q int data        if isFullQueue Q                         printf  Queue overflow n                return       Q- gt rear Q- gt rear 1   Q- gt size      Q- gt arr Q- gt rear  data      if Q- gt front  -1          Q- gt front Q- gt rear            int dequeue struct Queue  Q        if isEmptyQueue Q            printf  Queue underflow n            return                int data Q- gt arr Q- gt front       if Q- gt front  Q- gt rear          Q- gt front -1      else     Q- gt front Q- gt front 1   Q- gt size      return data                                            main algo                                         struct Stack  Sconstructor int capacity        struct Stack  S malloc sizeof struct Stack        S- gt Q1 Qconstructor capacity       S- gt Q2 Qconstructor capacity       return S    void push struct Stack  S int data        if isEmptyQueue S- gt Q1           enqueue S- gt Q1 data       else         enqueue S- gt Q2 data         int pop struct Stack  S        int i tmp      if  isEmptyQueue S- gt Q2            for i S- gt Q2- gt front i lt  S- gt Q2- gt rear i                 tmp dequeue S- gt Q2               if isEmptyQueue S- gt Q2                   return tmp              else                 enqueue S- gt Q1 tmp                                       else          for i S- gt Q1- gt front i lt  S- gt Q1- gt rear i                 tmp dequeue S- gt Q1               if isEmptyQueue S- gt Q1                   return tmp              else                 enqueue S- gt Q2 tmp                                                                          end of main algo my algo                                         push   O 1     pop   O n                  main         int size      printf  Enter the number of elements in the Stack made of 2 queue s    n        scanf   d   amp size       struct Stack  S Sconstructor size       push S 1       push S 2       push S 3       push S 4       printf   d n  pop S        push S 5       printf   d n  pop S        printf   d n  pop S        printf   d n  pop S        printf   d n  pop S

User · Answer

template  lt typename T gt  class stackfmtoq       queue lt T gt  q1      queue lt T gt  q2  public      void push T data            while   q2 empty                  q1 push q2 front                 q2 pop                      q2 push data           while   q1 empty                  q2 push q1 front                 q1 pop                        T pop             if  q2 empty                  cout  lt  lt   quot Stack is Empty n quot               return NULL                    T ret   q2 front            q2 pop            return ret            T top             if  q2 empty    return NULL          return q2 front

User · Answer

include  stdio h   include  stdlib h   typedef struct       int  q      int size      int front      int rear    Queue  typedef struct       Queue  q1      Queue  q2    Stack   int queueIsEmpty Queue  q        if  q- gt front    -1  amp  amp  q- gt rear    -1            printf   nQUEUE is EMPTY n            return 1            return 0    int queueIsFull Queue  q        if  q- gt rear    q- gt size-1            return 1            return 0    int queueTop Queue  q        if  queueIsEmpty q             return -1            return q- gt q q- gt front     int queuePop Queue  q        if  queueIsEmpty q             return -1            int item   q- gt q q- gt front       if  q- gt front    q- gt rear            q- gt front   q- gt rear   -1            else           q- gt front              return item    void queuePush Queue  q  int val        if  queueIsFull q             printf   nQUEUE is FULL n            return            if  queueIsEmpty q             q- gt front            q- gt rear          else           q- gt rear              q- gt q q- gt rear    val    Queue  queueCreate int maxSize        Queue  q    Queue  malloc sizeof Queue        q- gt front   q- gt rear   -1      q- gt size   maxSize      q- gt q    int  malloc sizeof int  maxSize       return q       Create a stack    void stackCreate Stack  stack  int maxSize        Stack   s    Stack    stack       s    Stack  malloc sizeof Stack          s - gt q1   queueCreate maxSize         s - gt q2   queueCreate maxSize         Push element x onto stack    void stackPush Stack  stack  int element        Stack   s    Stack    stack      queuePush   s - gt q2  element       while   queueIsEmpty   s - gt q1             int item   queuePop   s - gt q1           queuePush   s - gt q2  item             Queue  tmp     s - gt q1        s - gt q1     s - gt q2        s - gt q2   tmp        Removes the element on top of the stack    void stackPop Stack  stack        Stack   s    Stack    stack      queuePop   s - gt q1         Get the top element    int stackTop Stack  stack        Stack   s    Stack    stack      if   queueIsEmpty   s - gt q1           return queueTop   s - gt q1             return -1        Return whether the stack is empty    bool stackEmpty Stack  stack        Stack   s    Stack    stack      if  queueIsEmpty   s - gt q1             return true            return false        Destroy the stack    void stackDestroy Stack  stack        Stack   s    Stack    stack      free   s - gt q1       free   s - gt q2       free   s       int main       Stack  s   NULL    stackCreate  Stack   amp s  10     stackPush  Stack   amp s  44       stackPop  Stack   amp s     printf   n d   stackTop  Stack   amp s      stackDestroy  Stack   amp s     return 0

User · Answer

here is the complete working code in c     It has been implemented with Single Queue   push   1  add new element  2  Remove elements from Queue  totalsize-1  times and add back to the Queue   pop   normal remove       using System      using System Collections Generic      using System Linq      using System Text      using System Threading Tasks       namespace StackImplimentationUsingQueue               class Program                       public class Node                               public int data                  public Node link                            public class Queue                               public Node rear                  public Node front                  public int size   0                  public void EnQueue int data                                        Node n   new Node                        n data   data                      n link   null                      if  rear    null                          front   rear   n                      else                                               rear link   n                          rear   n                                            size                        Display                                      public Node DeQueue                                         Node temp   new Node                        if  front    null                          Console WriteLine  Empty                        else                                               temp   front                          front   front link                          size--                                            Display                        return temp                                    public void Display                                         if  size    0                          Console WriteLine  Empty                        else                                               Console Clear                            Node n   front                          while  n    null                                                        Console WriteLine n data                               n   n link                                                                                              public class Stack                               public Queue q                  public int size   0                  public Node top                  public Stack                                         q   new Queue                                      public void Push int data                                        Node n   new Node                        n data   data                      q EnQueue data                       size                        int counter   size                      while  counter  gt  1                                                q EnQueue q DeQueue   data                           counter--                                                          public void Pop                                         q DeQueue                        size--                                              static void Main string   args                                Stack s  new Stack                    for  int i   1  i  lt   3  i                        s Push i                   for  int i   1  i  lt  3  i                        s Pop                    Console ReadKey

User · Answer

import java util LinkedList  import java util Queue    public class StackQueue        static Queue lt Integer gt  Q1   new LinkedList lt Integer gt         static Queue lt Integer gt  Q2   new LinkedList lt Integer gt         public static void main String args                 push 24           push 34           push 4           push 10           push 1           push 43           push 21           System out println  Popped element is    pop             System out println  Popped element is    pop             System out println  Popped element is    pop                  public static void push int data             Q1 add data               public static int pop              if Q1 isEmpty              System out println  Cannot pop elements    Stack is Empty                return -1                    else                   while Q1 size    gt  1                Q2 add Q1 remove                       int element   Q1 remove            Queue lt Integer gt  temp   new LinkedList lt Integer gt             temp   Q1          Q1   Q2          Q2   temp          return element

User · Answer

Here is very simple solution which uses one Queue and gives functionality like Stack   public class CustomStack lt T gt        Queue lt T gt  que   new Queue lt T gt          public void push T t     STACK   LIFO   QUEUE   FIFO                if  que Count    0                        que Enqueue t                     else                       que Enqueue t               for  int i   0  i  lt  que Count-1  i                                  var data   que Dequeue                     que Enqueue data                                       public void pop                  Console WriteLine   nStack Implementation             foreach  var item in que                        Console Write   n    item ToString       t                       var data   que Dequeue            Console Write   n Dequeing      data              public void top                  Console Write   n Top      que Peek                 So in the above class named  CustomStack  what I am doing is just checking the queue for empty   if empty then insert one and from then on wards insert and then remove insert  By this logic first will come last  Example   In queue I inserted 1 and now trying to insert 2  Second time remove 1 and again insert so it becomes in reverse order   Thank you

User · Answer

Here is some simple pseudo code  push is O n   pop   peek is O 1    Qpush   Qinstance   Qpop   Qinstance    def stack push item       Qpush add item      while Qpop peek      null    transfer Qpop into Qpush         Qpush add Qpop remove         swap   Qpush     Qpush   Qpop     Qpop   swap  def stack pop        return Qpop remove    def stack peek        return Qpop peek

User · Answer

Below is a very simple Java solution which supports the push operation efficient   Algorithm -   Declare two Queues q1 and q2  Push operation - Enqueue element to queue q1  Pop operation - Ensure that queue q2 is not empty  If it is empty  then dequeue all the elements from q1 except the last element and enqueue it to q2 one by one  Dequeue the last element from q1 and store it as the popped element  Swap the queues q1 and q2  Return the stored popped element  Peek operation - Ensure that queue q2 is not empty  If it is empty  then dequeue all the elements from q1 except the last element and enqueue it to q2 one by one  Dequeue the last element from q1 and store it as the peeked element  Enqueue it back to queue q2 and swap the queues q1 and q2  Return the stored peeked element    Below is the code for above algorithm -  class MyStack        java util Queue lt Integer gt  q1      java util Queue lt Integer gt  q2      int SIZE   0           Initialize your data structure here         public MyStack             q1   new LinkedList lt Integer gt             q2   new LinkedList lt Integer gt                     Push element x onto stack         public void push int x            q1 add x           SIZE                     Removes the element on top of the stack and returns that element         public int pop             ensureQ2IsNotEmpty            int poppedEle   q1 remove            SIZE--          swapQueues            return poppedEle                 Get the top element         public int top             ensureQ2IsNotEmpty            int peekedEle   q1 remove            q2 add peekedEle           swapQueues            return peekedEle                 Returns whether the stack is empty         public boolean empty             return q1 isEmpty    amp  amp  q2 isEmpty                    move all elements from q1 to q2 except last element        public void ensureQ2IsNotEmpty             for int i 0  i lt SIZE-1  i                  q2 add q1 remove                              Swap queues q1 and q2        public void swapQueues             Queue lt Integer gt  temp   q1          q1   q2          q2   temp

User · Answer

Q1    10  15  20  25  30  Q2       exp           dequeue n-1 element from Q1 and enqueue into Q2  Q2     10  15  20  25       now Q1 dequeue gives  30  that inserted last and working as stack    swap Q1 and Q2 then GOTO exp

User · Answer

Let S1 and S2 be the two Stacks to be used in the implementation of queues   struct Stack    struct Queue  Q1    struct Queue  Q2      We make sure that one queue is empty always   Push operation   Whichever queue is not empty  insert the element in it    Check whether queue Q1 is empty or not  If Q1 is empty then Enqueue the element in it  Otherwise EnQueue the element into Q1    Push  struct Stack  S  int data             if isEmptyQueue S- gt Q1           EnQueue S- gt Q2  data       else EnQueue S- gt Q1  data            Time Complexity  O 1   Pop Operation  Transfer n-1 elements to other queue and delete last from queue for performing pop operation    If queue Q1 is not empty then transfer n-1 elements from Q1 to Q2 and then  DeQueue the last element of Q1 and return it  If queue Q2 is not empty then transfer n-1 elements from Q2 to Q1 and then  DeQueue the last element of Q2 and return it       int Pop struct Stack  S   int i  size  if IsEmptyQueue S- gt Q2      size size S- gt Q1   i 0  while i lt size-1    EnQueue S- gt Q2  Dequeue S- gt Q1       i      return DeQueue S- gt Q1       else  size size S- gt Q2   while i lt size-1  EnQueue S- gt Q1  Dequeue S- gt Q2     i      return DeQueue S- gt Q2         Time Complexity  Running Time of pop Operation is O n  as each time pop is called  we are transferring all the elements from one queue to oter

User · Answer

import java util                author Mahmood     public class StackImplUsingQueues        Queue lt Integer gt  q1   new LinkedList lt Integer gt         Queue lt Integer gt  q2   new LinkedList lt Integer gt          public int pop             if  q1 peek      null                System out println  The stack is empty  nothing to return                int i   0              return i            else               int pop   q1 remove                return pop                       public void push int data             if  q1 peek      null                q1 add data             else               for  int i   q1 size    i  gt  0  i--                    q2 add q1 remove                               q1 add data               for  int j   q2 size    j  gt  0  j--                    q1 add q2 remove                                         public static void main String   args            StackImplUsingQueues s1   new StackImplUsingQueues                     Stack s1   new Stack            s1 push 1           s1 push 2           s1 push 3           s1 push 4           s1 push 5           s1 push 6           s1 push 7           s1 push 8           s1 push 9           s1 push 10              s1 push 6           System out println  1st       s1 pop             System out println  2nd       s1 pop             System out println  3rd       s1 pop             System out println  4th       s1 pop             System out println  5th       s1 pop             System out println  6th       s1 pop             System out println  7th       s1 pop             System out println  8th       s1 pop             System out println  9th       s1 pop             System out println  10th      s1 pop

User · Answer

queue lt int gt  q1  q2  int i   0   void push int v      if  q1 empty    amp  amp  q2 empty            q1 push v        i   0        else        if  i    0             while   q1 empty     q2 push q1 pop             q1 push v           i   1-i              else           while   q2 empty     q1 push q2 pop             q2 push v           i   1-i                int pop        if  q1 empty    amp  amp  q2 empty     return -1     if  i    1           if   q1 empty                return q1 pop          else if   q2 empty                return q2 pop            else         if   q2 empty                return q2 pop          else if   q1 empty                return q1 pop

User · Answer

We can do this with one queue   push    enqueue new element  If n is the number of elements in the queue  then remove and insert element n-1 times    pop    dequeue      push 1   front                       ---- ---- ---- ---- ---- ----    1                                insert 1  ---- ---- ---- ---- ---- ----    push2  front                       ---- ---- ---- ---- ---- ----    1    2                           insert 2  ---- ---- ---- ---- ---- ----        front                       ---- ---- ---- ---- ---- ----         2     1                     remove and insert 1  ---- ---- ---- ---- ---- ----       insert 3         front                       ---- ---- ---- ---- ---- ----         2     1    3                insert 3  ---- ---- ---- ---- ---- ----              front                       ---- ---- ---- ---- ---- ----               1    3    2           remove and insert 2  ---- ---- ---- ---- ---- ----                   front                       ---- ---- ---- ---- ---- ----                    3    2    1      remove and insert 1  ---- ---- ---- ---- ---- ----    Sample implementation   int stack pop  queue data  q      return queue remove  q      void stack push  queue data  q  int val      int old count   queue get element count  q   i     queue insert  q  val     for  i 0  i lt old count  i            queue insert  q  queue remove  q

User · Answer

Can we just use one queue to implement a stack  I can use two queues  but considering single queue would be more efficient  Here is the code       public void Push T val                queLower Enqueue val              public  T Pop                  if  queLower Count    0                         Console Write  Stack is empty                 return default T                       if  queLower Count  gt  0                        for  int i   0  i  lt  queLower Count - 1 i                                   queLower Enqueue queLower Dequeue                                                  return queLower Dequeue

User · Answer

Here is my solution that works for O 1  in average case  There are two queues  in and out  See pseudocode bellow   PUSH X    in enqueue X   POP  X     if  out isEmpty and  in isEmpty      DUMP in  out    return out dequeue  DUMP A  B      if   A isEmpty      x   A dequeue       DUMP A  B      B enqueue x

User · Answer

Efficient solution in C  public class MyStack       private Queue lt int gt  q1   new Queue lt int gt         private Queue lt int gt  q2   new Queue lt int gt         private int count   0                  Initialize your data structure here              public MyStack                           Push element x onto stack              public void Push int x            count            q1 Enqueue x           while  q2 Count  gt  0                q1 Enqueue q2 Peek                 q2 Dequeue                      var temp   q1          q1   q2          q2   temp                        Removes the element on top of the stack and returns that element              public int Pop             count--          return q2 Dequeue                          Get the top element              public int Top             return q2 Peek                          Returns whether the stack is empty              public bool Empty             if  count  gt  0  return false          return true

User · Answer

Version A  efficient push     push     enqueue in queue1  pop    while size of queue1 is bigger than 1  pipe dequeued items from queue1 into queue2 dequeue and return the last item of queue1  then switch the names of queue1 and queue2    Version B  efficient pop     push    enqueue in queue2 enqueue all items of queue1 in queue2  then switch the names of queue1 and queue2  pop    deqeue from queue1

User · Answer

Here s one more solution    for PUSH    -Add first element in queue 1  -When adding second element and so on   Enqueue the element in queue 2 first and then copy all the element from queue 1 to queue2   -for POP just dequeue the element from the queue from you inserted the last element    So    public void push int data   if  queue1 isEmpty         queue1 enqueue data      else   queue2 enqueue data   while  queue1 isEmpty    Queue2 enqueue queue1 dequeue       EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2            public int pop    int popItem queue2 dequeue    return popItem       There is one problem  I am not able to figure out  how to rename the queues

[algorithm] Implement Stack using Two Queues

Examples related to algorithm

Examples related to data-structures

Examples related to stack