staqueue.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

'''
StaQueue! A Queue created by using 2 stacks!
'''

# the builtin `list` type in python has all the capabilities
# of a stack, so we use that instead of trying to re-created
# the stack itself as well.

# list operations to use: append() which is like push() and pop()


class Queue(object):

    def __init__(self, items=None):
        self._in_stack = []
        self._out_stack = []
        self._items = items
        if self._items:
            for item in self._items:
                self.enqueue(item)

    def enqueue(self, item):
        '''
        Complexity:
            For each enqueue operation, we first do a push() to in_stack, which is O(1),
            and then we iterate over all the items in the in stack, popping them and pushing
            them onto the out_stack. Both the push and pop themselves are O(1), and iterating
            over n items in the in_stack makes the operation O(n).

            I suppose this can also be reversed, with enqueue having O(1) and dequeue having O(n).
        '''
        # first, lets push the item on the _in_stack
        self._in_stack.append(item)                                         # O(1)

        # now pop all items from the in_stack and push them to the
        # out_stack
        for item in self._in_stack:                                         # O(n)
            popped = self._in_stack.pop(0)
            self._out_stack.append(popped)

    def dequeue(self):
        # the out_stack has all the items in desired order. Just pop!
        return self._out_stack.pop(0)

    def __repr__(self):
        items = self._out_stack
        return '<Queue {0}>'.format(items)


if __name__ == '__main__':
    q = Queue()
    print(q)
    q.enqueue(10)
    q.enqueue(20)
    print(q)
    q.dequeue()
    print(q)
    q.enqueue(30)
    q.enqueue(40)
    print(q)
    q.dequeue()
    print(q)