List operation while implementing stack

Question

This is a very basic problem of implementing a queue operation using two stacks.

Until now there are no issues with the logic but the testing tool report it takes more time than usual.

Test case includes total 100K operations of enqueue, dequeue and show_front. Each item is of 9 digits.

The test tool expects it to be completed by 10 seconds.

I tried with both Python way and traditional algorithmic way but both did not help. I could not find much content with Python list optimization that I can map here.

1. Quora link
2. Stack Overflow link

Listed two of the implementations for reference:

Try 1:

class MyQueue(object):
    def __init__(self):
        self.stk1 = [] # To store
        self.stk2 = [] # To dequeue

    def peek(self):
        return self.stk1[0]

    def pop(self):
        for i in range(len(self.stk1)-1):
            self.stk2.append(self.stk1.pop())
        self.stk1.pop()
        for x in range(len(self.stk2)):
            self.stk1.append(self.stk2.pop())

    def put(self, value):
        self.stk1.append(value) 

Try 2:

class MyQueue(object):    
    def __init__(self):
        self.stk1 = [] # To store
        self.top1 = -1
        self.stk2 = [] # To dequeue
        self.top2 = -1

    def peek(self):
        return self.stk1[0]

    def pop(self):
        if self.top1 == 0:
            self.stk1.pop()
            self.top1 -= 1
            return
        while self.top1 > 0:
            self.top2 += 1
            self.stk2.insert(self.top2,self.stk1.pop(self.top1))
            self.top1 -= 1
        self.stk1.pop()
        self.top1 -= 1
        while self.top2 >=0:
            self.top1 += 1
            self.stk1.insert(self.top1,self.stk2.pop(self.top2))
            self.top2 -= 1

    def put(self, value):
        self.top1 += 1
        self.stk1.insert(self.top1,value)

I'm not able to understand if append, insert or pop is taking more time. (Would pre-allocated array of specified size help in Python?)

Note: The testing tool is from a web based platform for developers to practice coding. I am making this question for suggestions about optimization that may help here.

Answer 1

I don't think that your solutions are quite abiding by the rules. You're allowed "push, pop and show_top". The lists in python do stack push with append and stack pop with pop, but all the action is at the end of the list. That is, your show_top operation should be implemented something like self.stk1[-1] (In Python indexing with negative numbers counts backwards from the end of the list)

The fundamental issue with your solution which is why it is taking up so much time is that the pop operation is always messing with the entire queue. If you've got 50k elements in self.stk1, the last thing you want to do every time you want to access one of them is copy them one at a time to self.stk2, and then copy them all back like The Grand Old Duke of York. (This is especially relevant because Python lists are arrays, and as you push and pop them you trigger yet more copying as the backing array has to resize!)

---

There is a standard algorithm for solving this problem, defined by the following rules.

• When you want to push something into the queue, you push it onto stack 1.

• When you want to read something out of the queue, or pop something out of the queue, you take it from stack 2.

• When stack 2 is empty (and needs accessing), you pop-push move all of stack 1 onto stack 2.

The logic here is that the pop-push move flips the stack, because the top of stack 1 is the first thing pushed to the bottom of stack 2, the bottom of stack 1 is popped last and therefore pushed to the top of stack 2, and everything else in the middle. This flip is necessary because the queue reads values in the opposite order from a stack.

The reason that this is massively more efficient is that there is no mechanism for anything going from stack 2 to stack 1. That means that you can't waste time copying the same long strings of elements back and forth. Instead every element is pushed to stack 1, popped from stack 1 and pushed to stack 2, and popped from stack 2, all at most once. This means that push and pop operations are "amortized constant time".

By the way, one point of code style. My answer would have been much easier to read if I'd said "The input stack" and "The output stack". Similarly, your code would benefit if you named your variables something more descriptive than stk1 and stk2

Answer 2

This answer assumes:

1. You must implement this queue yourself
2. You must use two stacks to implements this queue
3. Besides using [0] to peek, no other indexing or slicing is allowed, all interaction with the stacks must be through pop and append.

If any of these assumptions doesn't hold, there are much better ways to do this in Python. Within those bounds, I'd suggest you use your first solution, but modify it to only roll one stack into the other when absolutely necessary. I'd implement it something like this:

class MyQueue(object):
    def __init__(self):
        self.stk1 = []  # To store
        self.stk2 = []  # To dequeue
        self.is_forward = True

    @staticmethod
    def roll(stk_from, stk_to):
        while stk_from:
            stk_to.append(stk_from.pop())

    @property
    def forward(self):
        if not self.is_forward:
            self.roll(self.stk2, self.stk1)
            self.is_forward = True

        return self.stk1

    @property
    def backward(self):
        if self.is_forward:
            self.roll(self.stk1, self.stk2)
            self.is_forward = False

        return self.stk2

    def peek(self):
        return self.stk1[0]

    def pop(self):
        self.forward.pop()

    def put(self, value):
        self.backward.append(value)