5. 스택

1. Stack

- 선형 자료구조

- 먼저 들어간 것이 가장 마지막에 나옴(선입후출)

2. Stack ADT

- init(self, size)

- 스택을 초기화 합니다.

- 스택의 크기를 지정합니다.

- put(self, data)

- 스택에 데이터를 저장합니다

- pop(self)

- 스택의 제일 위의 데이터를 반환 하고 삭제합니다.

- peek(self)

- 스택의 제일 위의 데이터를 반환 합니다.

- is_full(self)

- 스택이 가득 차 있는지 확인합니다 

class Stack:
    def __init__(self, size):
        self.list = []
        self.size = size

    def put(self, data):
        if self.is_full():
            return False
        self.list.append(data)

    def pop(self):
        if not self.list:
            return False
        return self.list.pop()

    def peek(self):
        if not self.list:
            return False
        return self.list[-1]

    def is_full(self):
        if len(self.list) == self.size:
            return True
        return False


s = Stack(5)
s.put(1)
s.put(2)
s.put(3)
s.put(4)
s.put(5)
print(f'peek : {s.peek()}')
print(f'full : {s.is_full()}')
print(f'pop : {s.pop()}')
print(f'pop : {s.pop()}')

-----------------------------

peek : 5
full : True
pop : 5
pop : 4

3. Stack 에서 최소 값 구하기

- Big-O(1) 시간을 소모하는 put, pop, get_min(최소 값) 구하는 함수를 만들어라

- 최소값을 기록하는 Stack을 하나 더 생성해서 최소 값을 기록하면 된다.

class Stack:
    def __init__(self, size):
        self.list = []
        self.size = size
        self.min_list = []

    def put(self, data):
        if self.is_full():
            return False
        if self.min_list:
            if self.min_list[-1] > data:
                self.min_list.append(data)
        else:
            self.min_list.append(data)
        self.list.append(data)

    def pop(self):
        if not self.list:
            return False
        if self.min_list[-1] == self.list[-1]:
            self.min_list.pop()
        return self.list.pop()

    def peek(self):
        if not self.list:
            return False
        return self.list[-1]

    def is_full(self):
        if len(self.list) == self.size:
            return True
        return False

    def get_min(self):
        if not self.min_list:
            return False
        return self.min_list[-1]


s = Stack(5)
s.put(5)
s.put(4)
s.put(3)
s.put(2)
s.put(1)
print(f'min : {s.get_min()}')
print(f'pop : {s.pop()}')
print(f'pop : {s.pop()}')
print(f'min : {s.get_min()}')


---------------------------

min : 1
pop : 1
pop : 2
min : 3