스택과 큐 연습문제

📌코딩인터뷰 완전분석 - 면접문제 - 스택과 큐 part 문제풀이 (파이썬 사용)

3.2 스택 Min : 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min 함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다.

class Stack:
    #생성자
    def __init__(self):
        self.container = list()
        self.min_container = list()

    def push(self, data):
        self.container.append(data)

        # 최소값 갱신
        if not self.min_container or data < self.min_container[-1]:
            self.min_container.append(data)
        
    def pop(self):
        pop_data = self.container.pop()

        # 삭제되는 데이터가 최소값이라면 최소값을 갱신
        if pop_data == self.min_container[-1]:
            self.min_container.pop()

        return pop_data
        
    # min함수
    def min(self):
        if not self.min_container:
            return None
        
        return self.min_container[-1]

stack1 = Stack()
stack1.push(5)
stack1.push(7)
stack1.push(4)
stack1.push(1)
stack1.push(9)

print(stack1.min_container)
print(stack1.min())

3.5 스택 정렬: 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성하라. 추가적으로 하나 정도의 스택은 사용해도 괜찮지만, 스택에 보관된 요소를 배열 등의 다른 자료구조로 복사할 수는 없다. 스택은 push, pop, peek, isEmpty의 네 가지 연산을 제공해야 한다.

class Stack:
    def __init__(self):
        self.container = list()

    def push(self, data):
        self.container.append(data)
        
    def pop(self):
        if not self.isEmpty():
            return self.container.pop(-1)
        else:
            print("Stack underflow")
            exit()

    def peek(self):
        if not self.isEmpty():
            return self.container[-1]
        else:
            print("underflow")
            exit()
    
    def isEmpty(self):
        if len(self.container)==0:
            return True
        return False

class Forsort:

    def __init__(self):
        self.item = Stack()
        self.item = [7, 10, 5, 9, 8]

    def sorting(self):
        stack_b = Stack()
        while self.item.isEmpty() != True:
            tmp = self.item.pop()
            while stack_b.isEmpty() != True and stack_b.peek() > tmp :
                self.item.push(stack_b.pop())
            stack_b.push(tmp)

        while stack_b.isEmpty() != True:
            self.item.push(stack_b.pop())

        return self.item

sort1 = Forsort()
print(sort1.sorting())