스택(Stack)

스택이란?

LIFO(Last In First Out)의 성격을 가진 자료구조.

데이터를 쌓고나서 데이터를 빼낼 때 마지막으로 넣은 데이터부터 빼내는 자료구조이다. 

참고로 반복문의 무한루프 등으로 메모리의 이 스택 영역이 쌓이고 쌓이다가 터지는 현상을

많이 들어본 스택오버플로우(StackOverflow)라고 한다.

 

 

사용예시

• 웹에서의 뒤로가기 버튼
• Undo / Redo
• React의 Stack Navigator

 

스택의 대표 기능

• Peek
  • 스택의 Top(맨 위) 데이터를 보는 것
• Push
  • 스택의 Top에 원소를 삽입하는 행위
• Pop
  • 스택의 Top에서 원소를 가져오는 행위. Push로 넣었던 원소가 나오게 된다.

 

Peek, Push, Pop 코드 구현

이전 포스팅에서 배웠던 링크드리스트를 통해 스택을 구현해보자

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

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

    def peek(self):
        if self.head is None:
            return None
            # 강의에선 여기서 is_empty()를 만들고 print()로 출력까지 하는데
            # 굉장히 안좋은 코드라고 할 수 있다.
            # 차라리 위에처럼 is_empty()의 내용이 될 코드를 직접 if문 안에서 써주면서
            # self.head가 None이면 None을 리턴한 후
            # stack.pop을 호출하는 곳에서 print()처리를 하던지 하는 방식을 선택해야 한다.
            
        return self.head.data
        # 그냥 head의 위치에 있는 노드의 데이터값을 보여주면 된다.
        
    def push(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        
    def pop(self):
        if self.head is None:	
            return None		
        deleted_head = self.head
        self.head = self.head.next
        return deleted_head.data
        
    # 링크드리스트에서 0번째의 노드를 추가, 제거하는 방법이랑 같다.
    # 스택이기 때문에 추가되는 것과 제거되는 것 모두 head의 위치에 있는 노드를 대상으로 실시한다.
    

# 테스트
stack = Stack()
stack.push(3)
stack.push(6)
stack.push(9)
print('peek: ', stack.peek())	# 9
print('pop: ', stack.pop())	# 9
print('peek: ', stack.peek())	# 6

 

정리

이렇게 링크드리스트를 통해 스택을 구현해봤다.

하지만 실제 코드에서는 파이썬의 list를 이용해 스택으로 사용하기도 한다.

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

 

예제 문제

스택을 응용해 문제를 풀어보자

Q. 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 
발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 
또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4 인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 
그러면, 탑은 다음과 같이 신호를 주고 받습니다. 

높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑에서 수신하고, 
높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 
높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 

높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 
어떤 탑에서도 수신할 수 없습니다.

이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 
각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.

input = [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

output = [0, 0, 2, 2, 4]

내가 푼 방법

# Python의 list를 이용해 스택으로 사용할 수 있다.
# stack = []
# stack.append(4)
# stack.append(3)
# top = stack.pop()
# print(top)

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

def test(heights):
  # heights에서 pop()한 값 target에 대해 남아있는 heights의 마지막 인덱스부터 누가 더 큰지 체크
  # target이 더 크거나 같으면 패스, target이 더 작으면 해당 index의 값 + 1을 stack_1에 쌓는다.
  # 인덱스 0까지 더 큰 탑을 찾지 못하거나 target의 인덱스가 0일 경우는 0을 리턴한다.
  # 이렇게 끝까지 돌아 stack_1을 구했다면 stack_1에 대해 다시 하나씩 pop()을 하여 stack_2에 넣는다.
  # stack_1의 길이가 0이 되고난 후 stack_2를 리턴하면 원하는 답을 구할 수 있다.

  stack_1 = []
  while len(heights) > 0:
    target = heights.pop()
    # print('target: ', target)

    if len(heights) == 0:  # 첫번째 탑에 대한 예외처리
      stack_1.append(0)

    for i, e in reversed(list(enumerate(heights))):
      # print(i, e)
      if e > target:
        stack_1.append(i+1)
        break
      elif i == 0 and e <= target:
        stack_1.append(0)

  # print(stack_1)  # 구해야 하는 stack_2의 반대로 나왔나 확인

  stack_2 = []
  while len(stack_1) > 0:
    stack_2.append(stack_1.pop())

  return stack_2

print(test(heights))

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

다른풀이

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]))

시간복잡도

while문 안에 for문이 들어가는 형태로 시간복잡도는 O(N2)이다.