QueueFromStacksAndBack

QueueFromStacksAndBack

"""
PROBLEM - Stack from two Queues
"""

"""

STACK - LIFO, I/O from the SAME, ONE side
      - tracks TOP
      - push/pop on TOP
QUEUE - FIFO, Input at END, Output from FRONT; from DIFFERENT, TWO sides
      - tracks HEAD, TAIL
      - remove from HEAD, appends to TAIL

KEY POINT:

- We need to REVERSE FIFO order to LIFO; 

  e.g. Q1
       1, 2, 3
       
       BUT want to REMOVE in REVERSE order:
       3, 2, 1   

CAREFUL:

- VALUE of TOP vs INDEX
- TRICK: use SWAP of buffer references to avoid COPY!

SIMPLIFY ASSUMPTIONS:

- internal Queues are NOT BOUNDED -- so don't need to check for FULL,
  OTHERWISE, need to check that on INPUT QUEUE, to then transfer to OUTPUT QUEUE,
  which in turn needs to check itself for FULL condition, which then propagate external STACK API FULL condition!

TEST CASES:

- push
  - unlimited
- pop
  - throw/raise exception when empty, OR return None

TRICKY-KEY-DECISIONs:  

- backlog items accumulated in INPUT Q, 
  but when to TRANSFER item from INPUT Q to 
  REMAIN Q
- doing this full BLOCK-at-a-TIME rather than one-at-a-time on EACH operation
- this matters on EACH pop!  cannot do a block operation that applies for 
  SEVERAL pops!

"""

"""

SOLUTIONS:  (from LeetCode diagrams)
https://leetcode.com/articles/implement-stack-using-queues/

APPROACH1: just transfer older elements to get new bottom element only when pop 
=> PUSH just appends to inputQ
TOP item is always at END of inputQ (FIFO)
=> on EACH POP; transfer all elements EXCEPT last one to remainQ (FIFO)
- removes last element from inputQ as the TOP
- SWAP references for remainQ and inputQ to avoid costly copy, so remainQ is 
empty at end of this
=> PUSH is O(1) to add to end of inputQ on EACH operation
=> POP is O(n) to transfer to remainQ and swap on EACH operation 

APPROACH2:  maintain invariant LIFO with element-by-element reversal on access
=> maintains oldQ in LIFO order as invariant
=> on EACH PUSH, append to newQ; then transfer whatever is in oldQ to end,
- SWAP references for oldQ and newQ to avoid costly copy; so newQ is empty at end of this
=> on POP, just remove from HEAD of oldQ which is in FIFO order 
=> PUSH is O(n) on transfer oldQ to newQ on EACH operation
=> POP is O(1) to remove from HEAD of oldQ

APPROACH3: from one Q; ROTATE elements to REVERSE order
O(n)
=> on each PUSH, append latest to END of Q
   then LOOP to remove from front of the Q to essentially REVERSE order! 
   then add to END of Q,
   thus ROTATING until you reach TOP, to INVERT ORDER!
O(1)
=> POP just removes from HEAD of Q 

=================================================================

VARIATION:  Q from 2 STACKs 

APPROACH1: - read into FIFO inputS; but on pop from empty FIFO outputS, 
             need to transfer into outputS to simulate LIFO ordering
             i.e. REV on REV is like getting orig ordering back!
=> PUSH onto inputS
=> POP from outputS => on EMPTY requires transfer from inputS to invert ORDER
=> TRICK:  no need to do transfer on EACH operation, just when outputS is empty!

inputS   outputS
3           1  
2           2  
1           3 

=> PUSH Amortized O(n)
=> POP O(1)

APPROACH2: - maintain invariantLIFO stack
=> on EACH push, unload invariantS to bufferS, add new item to bottom
                 transfer BACK to maintain LIFO order
=> POP is O(1) constant

APPROACH3: - Q from a SINGLE STACK
- http://javabypatel.blogspot.in/2016/11/implement-queue-using-one-stack-in-ja.html
=> ENQ PUSHes onto oneSTACK
=> DEQ uses RECURSIVE call-stack as a second STACK;  i.e. REV of REV is orig FIFO 
            where DEPTH-FIRST call POPs stack to get to BOTTOM element (FIRST FIFO)
            and then on return from recursion stack, re-append the element popped
            to RESTORE the stack elements again!
"""
def recursiveDeQ(oneStack):

    if (len(oneStack) == 0):
        return None
    elif (len(oneStack) == 1):
        # this will REMOVE from BOTTOM item of STACK
        return oneStack.pop()
    else:
        # iteratively pop() recent data from END of Stack to get 
        # toward older HEAD data
        stageData = oneStack.pop()
        # RECURSE to get to BOTTOM or DEPTH of callstack and hence oneStack data
        nextQItem = recursiveDeQ(oneStack)
        # RESTORE all HIGHER data on Stack AFTER return result from DEPTHrecursion
        oneStack.append(stageData)
        # PROPAGATE DEPTH return BOTTOM-UP THROUGH ALL CALLSTACK levels based 
        # on RECURSIVE RETURNed item!
        return nextQItem
 
"""    
def deQueue(self):
    return recursiveDeQ(self.oneStack)
"""

print("***** TEST DRIVER for QUEUE from oneStack with Recursion and restore")
print("DEBUG in OPPOSITE order to reflect List STACK same-side access semantics")

inOrderData = [1, 2, 3]

item1 = recursiveDeQ(inOrderData)
print(item1)
print(inOrderData[::-1])

item2 = recursiveDeQ(inOrderData)
print(item2)
print(inOrderData[::-1])

item3 = recursiveDeQ(inOrderData)
print(item3)
print(inOrderData[::-1])

itemNone = recursiveDeQ(inOrderData)
print(itemNone)
print(inOrderData[::-1])
 

# revString with DFS Recursion instead of LOOP
# => read FORWARDS, but writes BACKWARDS via DFS
def revString(aString, idx):
    
    if not aString:
        return aString
    
    if (idx == (len(aString) - 1)):
        return aString[idx]
        
    else:
        # INCREMENT index as read FORWARDS
        # POST-recursion, APPENDs DEPTH-FORWARD letters 
        # BEFORE current idx letter to BACKUP TREE BRANCH REVERSAL!
        # D
        #  \
        #   A  
        #    \
        #     G   
        #      \
        #       N  
        #        \
        laterDepth = revString(aString, (idx + 1))
        # EFECTIVELY BACKTRACK
        partReversed = laterDepth + aString[idx] 
        return partReversed

print (revString("Dagny", 0))        
        
"""

# IMPLEMENTING APPROACH 1 where we transfer from FIFO inputQ to remainQ on pop()
class Stack:
    
    # PYTHONIC:  self is first param of member function, 
    #            and def is a member function
    def __init__(self):
        
        self.top = None   
        self.inputQ = []
        # self.inQ_Front = 0    ALWAYS 0
        self.remainQ = []
        # self.outQ_Front = 0   ALWAYS 0
   
        
    def push(self, item):

        # CASE 0:  append new item onto inputQ no matter what,
        #          and this won't affect remainQ
        self.inputQ.append(item)
        # TRICK:  DYNAMIC-track of TOP value
        self.top = item
        
    def pop(self):
        
        # CASE 1:  inputQ is empty, no items to pop
        if not self.inputQ:
            return None
        else:
            # CASE 2: if inputQ already has at least one item, 
            #         transfer to remainQ
            
            # BUGFIX:  List pop defaults to operate on END; 
            #          but we need specify index 0 with HEAD
            # ATTN:  evaluate initial condition prior to WHILE
            item = self.inputQ.pop(0)
            # print ("DEBUG PRE-TRANSFER\n {}, {}, {}".format(item, self.inputQ, self.remainQ))
            
            # BUGFIX:  We want to stop ONE-BELOW the END in the Q
            #          So lookback to NEXT lower TOP, and cache at END of while 
            #          BEFORE update of NEXT iteration position!
            # SIMPLIFYING ASSUMPTION:  we can get len or size of Q, so stop at
            #                          size = 1 or CURRENT TOP, but cache nextTop
            nextTop = None
            while ((item != self.top) and self.inputQ):
                self.remainQ.append(item)
                # BUGFIX:  lookback to NEXT lower TOP
                nextTop = item
                item = self.inputQ.pop(0)
                # print ("DEBUG WHILE-TRANSFER\n {}, {}, {}".format(item, self.inputQ, self.remainQ))
             
            # ATTN:  multiple exit conditions after WHILE, and may need to 
            #        process remainder!
            # print("DEBUG POST-EXIT TRANSFER \n {}".format(self))
            
            # update top to next recent item, and return cached priorTop
            priorTop = self.top
            self.top = nextTop # gets init to None when last one element popped
            
            # TRICK to restore dataQs without deep copy being necessary!
            self.inputQ, self.remainQ = self.remainQ, self.inputQ 
            
            # print("DEBUG EXIT TRANSFER WITH UPDATED PRIOR TOP \n {}".format(self.top))
      
        return priorTop   
        
    # PYTHONIC: line-breaks and output String formatting!
    def __repr__(self):
        
        # TODO, string concat OK with + here
        msg = "\n***STACK*** \
        \nTOP: {} \
        \nINQ: {} \
        \nREMAINQ: {}\n".format(self.top, self.inputQ, self.remainQ)
        
        return msg 
    
"""
# TEST DRIVER
"""

print("=> LOAD INPUT Q")

myStack = Stack()
print(myStack)

myStack.push(1)
print(myStack)

myStack.push(2)
print(myStack)

myStack.push(3)
print(myStack)

print("=> POP 3")
item3 = myStack.pop()
print(item3)
print(myStack)

print("=> POP 2")
item2 = myStack.pop()
print(item2)
print(myStack)

print("=> POP 1")
item3 = myStack.pop()
print(item3)
print(myStack)

print("=> POP EMPTY")
item4 = myStack.pop()
print(item4)
print(myStack)

print("=> LOAD INPUT Q after emptying")
myStack.push(5)
print(myStack)

print("=> POP 5")
item5 = myStack.pop()
print(myStack)
"""