큐(Queue), 스택(Stack)

목차

큐(Queue)

• 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식입니다
  • 
  • 출처 : 위키피디아
• 줄 서기 개념을 생각하면 됩니다. (먼저 줄 선 사람이 먼저 나가게 됩니다.)
• 파이썬에서는 deque를 이용하면 쉽게 구현이 가능합니다.

• from collections import deque
  
  q = deque()
  
  for i in range(5):
      q.append(i)
      
  while q:
      print(q.popleft())
      
  """
  0
  1
  2
  3
  4
  """

스택(Stack)

• 스택(stack)은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO(Last In First Out)으로 되어 있습니다.
  • 
  • 출처 : 위키피디아
• 책 쌓기 개념을 생각하면 됩니다. (책을 쌓게 되면 제일 위에 쌓인 책을 먼저 꺼내게 됩니다.)
• 파이썬에서는 그냥 리스트를 사용해서 append와 pop을 이용하면 쉽게 구현이 가능합니다.

• stack = []
  
  for i in range(5):
      stack.append(i)
      
  while stack:
      print(stack.pop())
      
  """
  4
  3
  2
  1
  0
  """

예시

• [백준 5430] AC
  • R : 뒤집기 / D : 첫 번째 수 버리기 
  • 배열이 비어있는데 D를 사용한 경우 에러가 발생
  • 테스트 개수는 100개 / 배열에 들어있는수는 100000개 / 함수 p의 길이는 100000개 
  • 단순히 모든 경우를 계산하는 경우를 생각해보겠습니다. 1케이스에 대해 최대의 경우를 생각해보면 10만개의 배열에 10만개의 명령이 수행될 수 있습니다. 첫번째 수를 버리는 pop의 경우 시간복잡도가 O(1)이지만, 리스트뒤집기의 경우 O(N)이 발생합니다. 따라서 모든 내용이 뒤집기로만 이루어진경우 100000*100000 으로 시간초과가 발생할 수 있습니다.
  • 따라서 뒤집기 연산이 있을경우 직접 수행하지 않고, 뒤집어지고 D를 한 경우는 마지막 수를 버린것과 동일하기 때문에,  flag를 통해 앞에서 꺼낼지 뒤에서 꺼내지만 체크해주면 됩니다.
  • 코드

    • import sys
      from collections import deque
      import ast
      
      input = sys.stdin.readline
      
      t = int(input())
      
      for _ in range(t):
          order_list = list(input())
          n = int(input())
          arr = deque(ast.literal_eval(input()))
      
          answer = []
      
          flag = 0  # 0이면 앞에서 / 1이면 뒤에서
          for order in order_list:
              if order == "R":
                  if flag == 0:
                      flag = 1
                  else:
                      flag = 0
      
              elif order == "D":
                  if len(arr) > 0:
                      if flag == 0:
                          arr.popleft()
                      else:
                          arr.pop()
                  else:
                      arr = "error"
                      break
      
          if type(arr) == deque:
              arr = list(arr)
              if len(arr) == 0:
                  print("[]")
              elif flag == 0:
                  print("[" + ",".join(map(str, arr)) + "]")
              else:
                  print("[" + ",".join(map(str, arr[::-1])) + "]")
          else:
              print(arr)

• [백준 1725] 히스토그램
  • 이 문제는 분할 정복, 세그먼트 트리, 스택 방식 등 다양한 방식으로 문제를 해결 할 수 있습니다. 그 중에서 스택 방식으로 푸는 방식을 살펴보도록 하겠습니다.
  • 다음 바의 높이가 스택의 top에 있는 높이보다 클 경우(또는 스택이 비어있는경우), 스택에 다음바의 높이를 넣어줍니다.
    • 뒤에 것이 크다면 계단식으로 뒤에서부터 넓이를 구해주면 되기때문입니다. 
    • 아래는 계단식으로 뒤에서부터 넓이를 구해주는 예시입니다.
      • 
  • 다음 바의 높이가 스택의 top에 있는 높이보다 작을 경우, 다음 바의 높이가 제일 큰 값이 될때까지 이전 바들을 스택에서 꺼낸다음 각각의 넓이 값을 구해줍니다. 그 후 다음 바를 스택에 넣어줍니다.(다음바의 높이가 스택의 top에 있는 높이보다 커졌기 때문에(또는 스택이 비었기 때문에))
    • 다음 바의 높이가 더 작다면, 최대 높이 값이 작아지기 때문에 더이상 스택에 다음 바의 높이보다 큰값들을 둘 필요가 없습니다.
    • 뒤에 것이 더 작다면 이제는 계단식이 되지 않기 때문에, 해당 넓이는 미리 계산을 해두는 것입니다. 뒤에것들보다 큰것들을 또 따로 보게 되면, 이것들 역시 계단식으로 형성되어져 있을 것입니다. 이것들에 대해서도 계단식으로 넓이를 구해주면 됩니다. 
      • 
  • 결국, 스택에 들어가는 개수는 봉의 개수이기때문에 결국엔 시간복잡도는 O(n)이 될것입니다. (스택에 있는 값들에 대해서만 연산이 진행되기때문에)
    • 분할정복은 O(nlogn)으로 해결되기 때문에 분할정복으로 풀때보다 시간 효율성이 더 좋습니다.
  • 코드

    • import sys
      
      input = sys.stdin.readline
      
      n = int(input())
      
      arr = [int(input()) for _ in range(n)] + [0]
      
      stack = []
      max_area = 0
      for i, height in enumerate(arr):
      
          while stack and arr[stack[-1]] > height:
              h_idx = stack.pop()
              if stack:
                  width = i - (stack[-1] + 1)
      
              else:
                  width = i
              max_area = max(max_area, width * arr[h_idx])
      
          stack.append(i)
      
      print(max_area)

• [백준 2493] 탑
  • 설명
    • 수신기를 받는 기둥만 중요하기 때문에, 만약 현재까지의 기둥보다 더 큰 기둥이 온다면, 그 앞에 기둥들은 무의미해집니다. 따라서 현재 기둥 높이보다 작은 기둥들은 모두 stack에서 pop을 진행합니다.
    • 그 후, stack에 만약 값이 없다면 현재 기둥이 가장 높은 것이므로 0을 추가해주고, 만약 값이 있다면 해당 기둥으로 쏘는 것이기때문에 해당 기둥의 인덱스를 추가해줍니다.
    • 그리고 현재 막대의 높이를 stack에 추가시켜줍니다.
    • stack에 원소를 넣고 빼는 작업으로 시간은 2*N이 걸릴것입니다. 따라서 시간복잡도는 O(N)이 됩니다.
    • 
  • 코드

    • import sys
      
      input = sys.stdin.readline
      
      n = int(input())
      
      arr = list(map(int, input().split()))
      stack = []
      answer = []
      for idx, item in enumerate(arr):
          while stack:
              if stack[-1][0] < item:
                  stack.pop()
              else:
                  break
      
          if stack:
              answer.append(stack[-1][1])
          else:
              answer.append(0)
      
          stack.append((item, idx + 1))
      
      print(*answer)