Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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)
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.