CodingExercises/sortedStack.py at master · JenGoodridge/CodingExercises · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# Code a stack that sorts the integers within.
import unittest
class Item():
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class Stack():
    def __init__(self):
        self.head = None

    def pop(self):  # Remove item from the top of the stack
        self.head = self.head.next

    def push(self, data):  # Push new item onto stack
        self.head = Item(data, self.head)

    def peek(self):
        return self.head

    def isEmpty(self):
        return self.head is None

    def __str__(self):
        string = "["
        current = self.head
        while current is not None:
            string += str(current.data)
            current = current.next
            if current is not None:
                string += ","

        return string + "]"


class Sorted_Stack():
    def __init__(self):
        self.temporaryStack = Stack()
        self.mainStack = Stack()

    def pop(self):
        self.mainStack.pop()

    def push(self, data):
        if self.mainStack.isEmpty():
            self.mainStack.push(data)

        elif self.mainStack.head.data >= data:
            self.mainStack.push(data)

        else:
            while not self.mainStack.isEmpty()and self.mainStack.head.data < data:
                self.temporaryStack.push(self.mainStack.head.data)
                self.mainStack.pop()

            self.mainStack.push(data)

            while not self.temporaryStack.isEmpty():
                self.mainStack.push(self.temporaryStack.head.data)
                self.temporaryStack.pop()

    def peek(self):
        return self.mainStack.peek()

    def isEmpty(self):
        return self.mainStack.isEmpty()

    def printStack(self):
        string = "["
        current = self.mainStack.head
        while current is not None:
            string += str(current.data)
            current = current.next
            if current is not None:
                string += ","

        return string + "]"


#setup for testing
test = Sorted_Stack()
test.push(1)
test.push(5)
test.push(6)
test.push(9)
test.pop()
test.push(-3)
test.push(0)
test.pop()
test.push(-1)


class Test(unittest.TestCase):
    def test_SortedStack(self):
        self.assertEqual(test.printStack(), "[-1,0,5,6,9]")
        test.pop()
        test.push(5)
        self.assertEqual(test.printStack(),"[0,5,5,6,9]")
        test.push(7)
        self.assertEqual(test.printStack(),"[0,5,5,6,7,9]")
        test.pop()
        test.pop()
        test.pop()
        self.assertEqual(test.printStack(),"[6,7,9]")


unittest.main()