Stack

Algorithms
stack
Catalogue
  1. 1. Queue
    1. 1.1. 225. Implement Stack using Queues
  2. 2. What is Stack?
    1. 2.1. Discussion
  3. 3. Design Data Structure
    1. 3.1. 232.Implement Queue using Stacks
    2. 3.2. 155. Min Stack
    3. 3.3. Min Stack Follow Up
    4. 3.4. 716. Max Stack
    5. 3.5. 20. Valid Parentheses
  4. 4. O(1) Stack
    1. 4.1. Remove 3 or more duplicates repeatedly
    2. 4.2. 844. Backspace String Compare

Logic Data Structure

Queue

  • FIFO == First In First Out, e.g. waith in a line
  • Usages
    • BFS related problems, Tree printout by levels
    • Sliding Window problems(Deque)

225. Implement Stack using Queues

  • Only use one Queue, O(n)push, O(1)pop
  • Two Queues, O(1)push, O(n)pop
    1
    2
    3
    4
    5
    queue = collections.deque()
    queue.append(1)
    queue.appendleft(2)
    queue.pop()
    queue.popleft()

What is Stack?

  • LIFO == Last in First Out, e.g. like a box
  • All operation available: push(), pop(), top()
  • Iterative DFS

Discussion

  • When do we consider “stack” in our algorithm?
  • Answer: when we linear scan an array/a string from left to right, and we need to look back the top element!
      1. Find the biggest Rectangle in Histogram
      1. Reverse Polish notation, a (b + c) -> abc+
      1. String repeatedly deduplication. cabba -> caa -> c

Design Data Structure

232.Implement Queue using Stacks

Implement a Queue by using two stacks

  • Key Point : When we pop all the elements from stack1 to stack2, we do not need to pop all the elements to stack1 again! Just put them to stack2 waiting for pop() function!
  • Time : pop(),amortized O(1); push(),O(1)
  • Space : O(n)
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
class MyQueue(object):

    def __init__(self):
        self.stack1 = [] # Buffer all the new elements
        self.stack2 = [] # Pop out the 1st element

    def push(self, x):
        self.stack1.append(x)


    def pop(self):
        if len(self.stack2) == 0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()


    def peek(self):
        if len(self.stack2) == 0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self):
        return len(self.stack1) == 0 and len(self.stack2) == 0

155. Min Stack

  • Two Stack: original stack & min stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Keep the push and pop function in sync between two stacks
class MinStack(object):

    def __init__(self):
        self.stack = []
        self.minstack = []

    def push(self, x):
        self.stack.append(x)
        cmin = min(x, self.minstack[-1]) if self.minstack else x
        self.minstack.append(cmin)

    def pop(self):
        self.stack.pop()
        self.minstack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.minstack[-1]

Min Stack Follow Up

  • How to optimize the space usage of minstack? (Assume there are a lot of duplicates)
    Try to make the elements in stack2 a descending order and store an element in stack2 <value, size of the stack1 when elements add to stack2>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class MinStack:

        def __init__(self):
            self.stack = []
            self.minStack = []

        def push(self, x):
            self.stack.append(x)
            if not self.minStack or x < self.minStack[-1][0]:
                self.minStack.append((x, len(self.stack)))

        def pop(self):
            self.stack.pop()
            if len(self.stack) < self.minStack[-1][1]:
                self.minStack.pop()


        def top(self):
            return self.stack[-1]


        def getMin(self):
            return self.minStack[-1][0]

716. Max Stack

  • popMax() – Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
  • TreeMap in Java!!!
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
class MaxStack(object):

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

    def push(self, x):
        self.stack.append((x, max(x, self.stack[-1][1] if self.stack else None)))        

    def pop(self):
        return self.stack.pop()[0]

    def top(self):
        return self.stack[-1][0]

    def peekMax(self):
        return self.stack[-1][1]

    def popMax(self):
        m = self.stack[-1][1]
        temp = []
        while self.stack[-1][0] != m:
            temp.append(self.pop()) # temp.insert(0, self.stack.pop())
        self.stack.pop()
        map(self.push, reversed(temp))
        return m
  • TODO : Using Stack for Selection Sort; Implement Deque using stacks

20. Valid Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def isValid(self, s):
        stack = []
        pdic = {'(':')', '{':'}', '[':']'}
        for ch in s:
            if ch in "({[":
                stack.append(pdic[ch])
            else:
                if len(stack) == 0 or stack[-1] != ch:
                    return False
                stack.pop()
        return len(stack) == 0

O(1) Stack

Remove 3 or more duplicates repeatedly

  • Stack + traversal pointer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def removeDuplicates(s):
    stack = []
    i = 0
    print(s)
    while i < len(s):
        if len(stack) > 1 and s[i] == stack[-1] == stack[-2]:
            while i < len(s) and s[i] == stack[-1]:
                i += 1
            stack.pop()
            stack.pop()
        else:
            stack.append(s[i])
            i += 1
    return stack

# TEST
if __name__ == "__main__":
    string = raw_input()
    res = removeDuplicates(string)
    print(res)
  • Use Two pointers to imitate the stack!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def removeDuplicates(s):
        i = 0
        slow = -1
        while i < len(s):
            if slow > 0  and s[i] == s[slow] == s[slow-1]:
                while i < len(s) and s[i] == s[slow]:
                    i += 1
                slow -= 2
            else:
                slow += 1
                s[i], s[slow] = s[slow], s[i]
                i += 1
        return s[:slow+1]

    # TEST
    if __name__ == "__main__":
        string = raw_input()
        res = removeDuplicates(list(string))
        print(res)

844. Backspace String Compare

  • Stack, Space : O(m + n)
  • Two Pointers, Space : O(1)
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
class Solution(object):
    def backspaceCompare(self, S, T):
        p1, p2 = len(S)-1, len(T)-1
        while p1 >= 0 or p2 >= 0:
            back1 = 0
            while (p1 >= 0 and S[p1] == '#') or back1 > 0:
                back1 += 1 if S[p1] == '#' else -1
                p1 -= 1

            back2 = 0
            while (p2 >= 0 and T[p2] == '#') or back2 > 0:
                back2 += 1 if T[p2] == '#' else -1
                p2 -= 1

            if p1 < 0 and p2 < 0:
                return True
            elif p1 < 0 or p2 < 0:
                return False
            else:
                if S[p1] != T[p2]:
                    return False
                else:
                    p1 -= 1
                    p2 -= 1
        return p1 == p2
Share