자료구조 3주차_스택

자료구조 3주차_스택 & 큐

---

스택(Stack)

Last In First Out

되돌리기 할때 사용!

 

• push(data) : 맨 위에 데이터 넣기
• pop() : 맨 위의 데이터 뽑기
• peek() : 맨 위의 데이터 보기
• isEmpty() : 스택이 비었는지 안 비었는지 여부 반환

 

📌 스택 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


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

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return "Stack is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    def peek(self):
        if self.is_empty():
            return "Stack is Empty"
        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None

stack = Stack()
stack.push(3)
print(stack.peek()) # 3
stack.push(4)
print(stack.peek()) # 4
print(stack.pop()) # 4
print(stack.peek()) # 3
print(stack.is_empty()) #False
print(stack.pop()) # 3
print(stack.is_empty()) #True

하지만 stack은 넘치면 StackOverflow 가 발생!
반복문의 종료조건을 해주지 않으면,,, overflow발생.

비동기적으로 사용할 수 있어서 많이 쓰임.

---

스택을 구현했지만 실제 코드에서는 파이썬의 list를 이용해 스택 사용

stack = []            # 빈 스택 초기화
stack.append(4)       # 스택 push(4)
stack.append(3)       # 스택 push(3)
top = stack.pop()     # 스택 pop
print(top)            # 3!

 

📌 탑 문제

[6, 9, 5, 7, 4] # 라고 입력된다면,

# 아래 그림처럼 탑이 있다고 보시면 됩니다!
<- <- <- <- <- 레이저의 방향
   I 
   I
   I     I
I  I     I
I  I  I  I  
I  I  I  I  I
I  I  I  I  I
I  I  I  I  I
I  I  I  I  I

[0, 0, 2, 2, 4] # 다음과 같이 반환하시면 됩니다!

레이저는 왼쪽으로 수신하는데 왼쪽 탑이 현재 탑보다 커야지 수신 가능!

 

 

📄 나의 코드

top_heights = [6, 9, 5, 7, 4]


def get_receiver_top_orders(heights):
    raizer = [0] * len(heights)

    for i in reversed(range(1, len(heights))):
        for j in reversed(range(i)):
            # print(i, j)
            if heights[i] < heights[j]:
                raizer[i] = j + 1
                break
    return raizer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

풀긴 풀었는데, stack을 딱히 이용하지는 못한 느낌...

 

📄 코드

top_heights = [6, 9, 5, 7, 4]


def get_receiver_top_orders(heights):
    answer = [0] * len(heights)
    while heights:
        height = heights.pop()
        for idx in range(len(heights) - 1, -1, -1):
            if heights[idx] > height:
                answer[len(heights)] = idx + 1
                break
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

print("정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 = ",get_receiver_top_orders([6,9,5,7,4]))
print("정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 = ",get_receiver_top_orders([3,9,9,3,5,7,2]))
print("정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 = ",get_receiver_top_orders([1,5,3,6,7,6,5]))