def main():
    my_stack = Stack() 
    for _ in range(10):
        my_stack.push(randint(0, 9))
    sort_stack(my_stack)
    for _ in range(10):
        print my_stack.pop()

def converter(exp, fix="post"):
    """takes simple infix expression and converts to prefix or postfix"""
    tokens = list(exp)
    open_paren, close_paren = "(", ")"

    if fix not in ["pre", "post"]:
        raise ValueError("Must specify conversion as either 'pre' or 'post'")

    if fix == "pre":
        tokens.reverse()
        open_paren, close_paren = ")", "("

    s = Stack()
    result = ''

    for t in tokens:
        if t == open_paren:
            pass
        elif t in ["*", "+", "-", "/"]:
            s.push(t)
        elif t == close_paren and not s.is_empty():
            result += s.pop()
        else:
            result += t

    if fix == "pre":
        return result[::-1]
    return result

 def __init__(self):
     ''' 
     Initialize the queue with two stacks -- an incoming
     and outgoing stack.
     '''
     self.incoming_stack = Stack()
     self.outgoing_stack = Stack()

def heightStack(height, nameStr):
    h = Stack(nameStr)
    while height != 0:
        h.push(height)
        height -= 1

    return h

	def solution(self):
		stck = Stack()
		node = self.goal
		while not node is None:
			stck.push(node.board)
			node = node.prev
		return stck

def test_push_pop(input_list):
    from stack import Stack
    new_stack = Stack()
    for item in input_list:
        new_stack.push(item)
    for item in reversed(input_list):
        assert new_stack.pop() == item

def test_pop_2():
    our_list = ["first", "second", "third", "fourth"]
    our_stack = Stack(our_list)
    assert our_stack.pop() == "fourth"
    assert our_stack.pop() == "third"
    assert our_stack.pop() == "second"
    assert our_stack.pop() == "first"

	def __init__(self):
		'''
		Initialize Queue

		'''
		self.stack1 = Stack()
		self.stack2 = Stack()

def test_count(COUNT_LIST, count):
    """Test to see if stack count is correct."""
    from stack import Stack
    s = Stack()
    for i in COUNT_LIST:
        s.push(i)
    assert s.size() == count

def test_push():
    my_stack = Stack([1, 2, 3])
    my_stack.push(4)
    # assert my_stack.container.display() == (4, 3, 2, 1)
    assert my_stack.pop() == 4
    # check to make sure new stack wasn't initialized
    assert my_stack.pop() == 3

def test_empty():
    """Test case where an empty list is pushed to stack."""
    from stack import Stack
    stacky = Stack()
    stacky.push([])
    with pytest.raises(IndexError):
        stacky.pop().get_data()

def stack_sort(s):
    def find_max(s):
        t = Stack()
        m = None
        while s.size > 0:
            v = s.pop()
            t.push(v)
            if not m or v > m:
                m = v
        while t.size > 0:
            v = t.pop()
            if v != m:
                s.push(v)
        return m

    sort = Stack()

    while s.size > 0:
        m = find_max(s)
        sort.push(m)

    while sort.size > 0:
        s.push(sort.pop())

    return s

def test_push():
    """Test stack push method."""
    from stack import Stack
    from stack import Node
    stack = Stack()
    stack.push(data[0])
    assert isinstance(stack.head, Node)

class VisitOrder:
  
    stack = None 
    level = 0

    node_list = []

    def __init__( self ):
        self.stack = Stack()

    def make_stack( self ):
        while self.stack.length() > 0:
            print "self.stack.length() ==> " + str( self.stack.length() )
            print "Pop the stack ---> " + str( self.stack.pop().value )

    def get_node( self, node_id ):
        for n in self.node_list:
            #print 'get_node ' + str( n.id )
            if n.id == node_id:
                return n
        return None

    def build_tree( self, node ):
         self.level = self.level + 1
         print "in build_tree level : " + str( self.level )
         while len( node.value ) > 0:
             node.left = self.stack.pop() 
             build_tree( node.left )
         
         while len( node.value ) > 0:
             node.right = self.stack.pop()
             build_tree( node.right )

class MyQueue:
    def __init__(self):
        self.stack_in  = Stack()
        self.stack_out = Stack()

    def enqueue(self, item):
        if not self.stack_in.is_empty():
            self.empty_stack(self.stack_in, self.stack_out)
        self.stack_in.push(item)

    def dequeue(self):
        if not self.stack_out.is_empty():
            self.empty_stack(self.stack_out, self.stack_in)
        return self.stack_in.pop()

    def empty_stack(self, stack1, stack2):
        '''
        Empty stack1 into stack2
        '''
        while not stack1.is_empty():
            stack2.push(stack1.pop())

    def print_mq(self):
        self.empty_stack(self.stack_in, self.stack_out)
        print self.stack_out

class StackAllTestCase(unittest.TestCase):
    """Comprehensive tests of (non-empty) Stack."""

    def setUp(self):
        """Set up an empty stack."""
        self.stack = Stack()

    def tearDown(self):
        """Clean up."""
        self.stack = None

    def testAll(self):
        """Test adding and removeping multiple elements."""

        for item in range(20):
            self.stack.add(item)
            assert not self.stack.is_empty(), \
                'is_empty() returned True on a non-empty Stack!'

        expect = 19
        while not self.stack.is_empty():
            assert self.stack.remove() == expect, \
                ('Something wrong on top of the Stack! Expected ' +
                 str(expect) + '.')
            expect -= 1

class Transactor:

    def __init__(self):
        self.stack = Stack()
        self.transaction_queue = []

    def start_transaction(self):
        """ (Transactor) -> NoneType
        Starts an "undo"-able set of events.
        """
        self.transaction_queue = []

    def end_transaction(self):
        """ (Transactor) -> NoneType
        Ends the current set of events.
        """
        self.stack.push(self.transaction_queue)
        self.transaction_queue = []

    def add_action(self, action):
        """ (Transactor, function) -> NoneType
        Adds an action onto the list of transactions.
        """
        self.transaction_queue.append(action)

    def undo(self):
        """ (Transactor) -> NoneType
        Undoes the last set of transactions. Returns true on success, or
        false on failure (indicating there were no more transactions to undo).
        Can throw a stack.EmptyStackError, which should be handled!
        """
        for cmd in reversed(self.stack.pop()):
            cmd()

def revString(string):
	s = Stack()
	for c in string:
		s.push(c)
	
	while not s.isEmpty():
		print(s.pop(), end = '')

class StackWithMin(object):
    def __init__(self, top = None):
        self.top = top 

        #store the min values
        self._min = Stack(top) 

    def min(self):
        retval = self._min.peek()
        if retval is None:
            retval = sys.maxsize
        return retval



    def push(self,data):
        new_node = Node(data, self.top)
        self.top = new_node

        if data <= self.min(): 
            self._min.push(data)


    def pop(self):
        if self.top:
            retval = Node(self.top.data)
            self.top = self.top.next

            if retval.data == self.min():
                self._min.pop()
            return retval

    def peek(self):
        if self.top:
            return self.top.data

def codeeval_input2():
    stack = Stack()
    node1 = Node(10, None)
    node2 = Node(-2, node1)
    node3 = Node(3, node2)
    node4 = Node(4, node3)
    stack.head = node4
    return stack