스택

• push : 스택에 데이터를 넣음

• pop : 스택에서 데이터를 꺼냄

• top : 푸시 팝이 이루어지는(나중에 들어간 데이터, 먼저 나올 데이터가 있는) 윗부분

• bottom : 먼저 들어간 데이터가 쌓이는 아랫부분

  ⇒ 넣은(push) 데이터는 스택 꼭대기(top)에 쌓이고, 꺼낼 때도(pop) 꼭대기(top)에서 데이터가 나옴, 방금 넣은걸 꺼내는거

• 스택 구현하기 - 고정길이스택.. 실제로는 가변리스트로 쓰는거같음

• 용어만 정리하자면

• 스택 크기(capacity)
  : 스택의 최대 크기를 나타내는 int형 정수, 스택으로 쓸 배열의 길이 // = len(stk)

• 스택 포인터(ptr)
  : 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값
  : 비어있으면 0, 가득차있으면 capacity와 같음
  : 마지막에 푸시한 데이터는 stk[ptr-1]에 있음
  : 데이터를 푸시할때 ptr을 1씩 증가시키고, 팝할때 ptr을 1씩 감소시킴

• 고정 길이 스택 구현 - FixedStack 클래스

  # 고정 길이 스택 클래스 FixedStack 구현하기
  # Do it! 실습 4-1 [A]
  from typing import Any
  
  class FixedStack:
      """고정 길이 스택 클래스"""
  
      class Empty(Exception):
          """비어 있는 FixedStack에 pop 또는 peek를 호출할 때 내보내는 예외 처리"""
          pass
  
      class Full(Exception):
          """가득 찬 FixedStack에 push를 호출할 때 내보내는 예외 처리"""
          pass
  
      def __init__(self, capacity: int = 256) -> None:
          """초기화"""
          self.stk = [None] * capacity  # 스택 본체
          self.capacity = capacity      # 스택의 크기
          self.ptr = 0                  # 스택 포인터
  
      def __len__(self) -> int:
          """스택에 쌓여있는 데이터 개수를 반환"""
          return self.ptr
  
      def is_empty(self) -> bool:
          """스택이 비어 있는가?"""
          return self.ptr <= 0
  
      def is_full(self) -> bool:
          """스택은 가득 찼는가?"""
          return self.ptr >= self.capacity
  
  # Do it! 실습 4-1 [B]
      def push(self, value: Any) -> None:
          """스택에 value를 푸시"""
          if self.is_full():              # 스택이 가득 참
              raise FixedStack.Full
          self.stk[self.ptr] = value
          self.ptr += 1
  
      def pop(self) -> Any:
          """스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
          if self.is_empty():             # 스택이 비어 있음
               raise FixedStack.Empty
          self.ptr -= 1
          return self.stk[self.ptr]
  
      def peek(self) -> Any:
          """스택에서 데이터를 피크(꼭대기 데이터를 들여다 봄)"""
          if self.is_empty():             # 스택이 비어 있음
              raise FixedStack.Empty
          return self.stk[self.ptr - 1]
  
      def clear(self) -> None:
          """스택을 비움(모든 데이터를 삭제)"""
          self.ptr = 0
  
  # Do it! 실습 4-1 [C]
      def find(self, value: Any) -> Any:
          """스택에서 value를 찾아 첨자(없으면 -1)를 반환"""
          for i in range(self.ptr - 1, -1, -1):  # 꼭대기 쪽부터 선형 검색
              if self.stk[i] == value:
                  return i  # 검색 성공
          return -1         # 검색 실패
  
      def count(self, value: Any) -> bool:
          """스택에 포함되어있는 value의 개수를 반환"""
          c = 0
          for i in range(self.ptr):  # 바닥 쪽부터 선형 검색
              if self.stk[i] == value:
                  c += 1             # 들어 있음
          return c
  
      def __contains__(self, value: Any) -> bool:
          """스택에 value가 있는가?"""
          return self.count(value)
  
      def dump(self) -> None:
          """덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
          if self.is_empty():  # 스택이 비어 있음
              print('스택이 비어 있습니다.')
          else:
              print(self.stk[:self.ptr])

• 스택 프로그램

  # [Do it! 실습 4-2] 고정 길이 스택 FixedStack의 사용하기
  
  from enum import Enum
  from fixed_stack import FixedStack
  
  Menu = Enum('Menu', ['푸시', '팝', '피크', '검색', '덤프', '종료'])
  
  def select_menu() -> Menu:
      """메뉴 선택"""
      s = [f'({m.value}){m.name}' for m in Menu]
      while True:
          print(*s, sep = '   ', end='')
          n = int(input(': '))
          if 1 <= n <= len(Menu):
              return Menu(n)
  
  s = FixedStack(64)  # 최대 64개를 푸시할 수 있는 스택
  
  while True:
      print(f'현재 데이터 개수: {len(s)} / {s.capacity}')
      menu = select_menu()  # 메뉴 선택
      
      if menu == Menu.푸시:  # 푸시
          x = int(input('데이터를 입력하세요.: '))
          try:
              s.push(x)
          except FixedStack.Full:
              print('스택이 가득 차 있습니다.')
  
      elif menu == Menu.팝:  # 팝
          try:
              x = s.pop()
              print(f'팝한 데이터는 {x}입니다.')
          except FixedStack.Empty:
              print('스택이 비어 있습니다.')
  
      elif menu == Menu.피크:  # 피크
          try:
              x = s.peek()
              print(f'피크한 데이터는 {x}입니다.')
          except FixedStack.Empty:
              print('스택이 비어 있습니다.')
  
      elif menu == Menu.검색:  # 검색
          x = int(input('검색할 값을 입력하세요.: '))
          if x in s:
              print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
          else:
              print('검색값을 찾을 수 없습니다.')
  
      elif menu == Menu.덤프:  # 덤프
          s.dump()
  
      else:
          break

큐

• 스택처럼 데이터를 임시저장할 때 사용하는 자료구조

• 데이터의 입출력은 선입선출(FIFO)

• 먼저 들어간 게 먼저 나옴

• enqueue : 큐에 데이터를 추가

• dequeue : 큐에서 데이터를 꺼냄

• front : 데이터를 꺼내는 쪽

• rear : 데이터를 넣는 쪽;

• 배열로 큐 구현하기

  • 배열의 앞에서부터 순서대로 데이터를 저장하고(예를들어 19, 22, 37, 53 이렇게 4개의 데이터가 순서대로 들어있다 치고) 이름은 que로 함
    // 인덱스 0인 원소가 큐의 첫번째 원소
  • 24를 인큐(enqueue) : 마지막 데이터가 저장된 que[3]의 다음 인덱스 que[4]에 24를 저장
    // 복잡도 O(1)
  • 19를 디큐(dequeue) : que[0]에 저장된 19를 꺼내고, 두번째 이후의 모든 원소를 앞으로 당겨야함
    // 복잡도 O(n)
  • 우선순위 큐 가 있음

• 링 버퍼로 큐 구현하기

  • 디큐할때 배열 안의 원소를 통째로 옮기지 않아도 되는 큐
  • 링 버퍼 : 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
  • front : 맨 앞 원소의 인덱스(디큐에 데이터가 나갈 위치
  • rear : 맨 끝 원소 바로 뒤의 인덱스(인큐에 데이터가 저장되는 위치)
  • front와 rear는 논리적인 데이터 순서일 뿐, 배열의 물리적 원소의 순서는 아님
  • 인큐와 디큐를 수행하면 front와 rear의 값이 바뀜
  • 한번 해보면
    1. 7개의 데이터 35, 56, 24, 68, 95, 73, 19 가 배열 que에 que[7], que[8], ..., que[11], que[0], que[1] 에 순서대로 저장됨
       front 값은 7, rear 값은 2
    2. 여기에 82를 인큐하면 맨끝원소 다음인 que[rear]에 82를 저장하고 rear 값을 1 증가시킴
    3. 여기서 35를 디큐하면 맨 앞 원소인 que[front]에서 35를 꺼내고 front 값을 1 증가시킴
  • 링 버퍼로 큐를 구현하면 원소를 옮길 필요없이 front, rear의 값만 바꿔주면 돼서 복잡도도 O(1)
  • 크기가 정해진 고정 길이 큐 임

• 고정 길이 큐 클래스 - FixedQueue

  # 고정 길이 큐 클래스 FixedQueue 구현하기
  # Do it! 실습 4-3 [A]
  from typing import Any
  
  class FixedQueue:
  
      class Empty(Exception):
          """비어 있는 FixedQueue에 대해 deque 또는 peek를 호출할 때 내보내는 예외처리"""
          pass
  
      class Full(Exception):
          """가득 찬 FixedQueue에 enque를 호출할 때 내보내는 예외처리"""
          pass
  
      def __init__(self, capacity: int) -> None:
          """초기화 선언"""
          self.no = 0     # 현재 데이터 개수
          self.front = 0  # 맨앞 원소 커서
          self.rear = 0   # 맨끝 원소  커서
          self.capacity = capacity      # 큐의 크기
          self.que = [None] * capacity  # 큐의 본체
  
      def __len__(self) -> int:
          """큐에 있는 모든 데이터 개수를 반환"""
          return self.no
  
      **def is_empty(self) -> bool:**
          """큐가 비어 있는지 판단"""
          return self.no <= 0
  
      **def is_full(self) -> bool:**
          """큐가 가득 찼는지 판단"""
          return self.no >= self.capacity
  
  # Do it! 실습 4-3 [B]
      def enque(self, x: Any) -> None:
          """데이터 x를 인큐"""
          if self.is_full():
              raise FixedQueue.Full  # 큐가 가득 찬 경우 예외처리를 발생
          self.que[self.rear] = x    # rear인덱스에 값을 저장
          self.rear += 1    # rear값을 1 증가
          self.no += 1    # 개수도 1 증가
          if self.rear == self.capacity:    # rear가 크기랑 같아지면 
              self.rear = 0    # 0으로 만들어줌, 인덱스는 n-1까지니까.
  
  # Do it! 실습 4-3 [C]
      def deque(self) -> Any:
          """데이터를 디큐합니다"""
          if self.is_empty():
              raise FixedQueue.Empty  # 큐가 비어 있는 경우 예외처리를 발생
          x = self.que[self.front]    # front인덱스의 값을 꺼내줌
          self.front += 1    # front값을 1 증가
          self.no -= 1    # 개수는 1감소
          if self.front == self.capacity:    # front도 크기랑 같아지면
              self.front = 0    # 0으로 만들어줌
          return x    # 꺼낸 값 저장한 변수 반환
  
  # Do it! 실습 4-3 [D]
      def peek(self) -> Any:
          """데이터를 피크합니다(맨 앞 데이터를 들여다 봄)"""
          if self.is_empty():
              raise FixedQueue.Empty  # 큐가 비어 있으면 예외처리를 발생
          return self.que[self.front]
  
      def find(self, value: Any) -> Any:
          """큐에서 value를 찾아 인덱스를 반환하고 없으면 -1을 반환합니다"""
  				# for문 개수만큼 돌면 front 더해준 인덱스부턴데
  				# i+front에 크기로 나눠서 나머지 구해주면 인덱스 맞춰서 돌아줌
          for i in range(self.no):
              idx = (i + self.front) % self.capacity
              if self.que[idx] == value:  # 검색 성공
                  return idx
          return -1  # 검색 실패
  
      def count(self, value: Any) -> bool:
          """큐에 포함되어 있는 value의 개수를 반환합니다"""
          c = 0
          for i in range(self.no):  # 큐 데이터를 선형 검색
              idx = (i + self.front) % self.capacity
              if self.que[idx] == value:  # 검색 성공
                  c += 1  # 들어있음
          return c
  
      def __contains__(self, value: Any) -> bool:
          """큐에 value가 포함되어 있는지 판단합니다"""
          return self.count(value)
  
      def clear(self) -> None:
          """큐의 모든 데이터를 비웁니다"""
          self.no = self.front = self.rear = 0
  
      def dump(self) -> None:
          """모든 데이터를 맨 앞에서 맨 끝 순서로 출력합니다"""
          if self.is_empty():  # 큐가 비어 있으면 예외처리를 발생
              print('큐가 비어 있습니다.')
          else:
              for i in range(self.no):
                  print(self.que[(i + self.front) % self.capacity], end=' ')
              print()

• 링 버퍼로 큐 프로그램 만들기

  # [Do it! 실습 4-4] 고정 길이 큐 클래스(FixedQueue)를 사용하기
  
  from enum import Enum
  from fixed_queue import FixedQueue
  
  Menu = Enum('Menu', ['인큐', '디큐', '피크', '검색', '덤프', '종료'])
  
  def select_menu() -> Menu:
      """메뉴 선택"""
      s = [f'({m.value}){m.name}' for m in Menu]
      while True:
          print(*s, sep='   ', end='')
          n = int(input(': '))
          if 1 <= n <= len(Menu):
              return Menu(n)
  
  q = FixedQueue(64)  # 최대 64개를 인큐할 수 있는 큐 생성(고정 길이)
  
  while True:
      print(f'현재 데이터 개수: {len(q)} / {q.capacity}')
      menu = select_menu()   # 메뉴 선택
  
      if menu == Menu.인큐:  # 인큐
          x = int(input('인큐할 데이터를 입력하세요.: '))
          try:
              q.enque(x)
          except FixedQueue.Full:
              print('큐가 가득 찼습니다.')
  
      elif menu == Menu.디큐:  # 디큐
          try:
              x = q.deque()
              print(f'디큐한 데이터는 {x}입니다.')
          except FixedQueue.Empty:
              print('큐가 비어 있습니다.')
  
      elif menu == Menu.피크:  # 피크
          try:
              x = q.peek()
              print(f'피크한 데이터는 {x}입니다.')
          except FixedQueue.Empty:
              print('큐가 비었습니다.')
  
      elif menu == Menu.검색:  # 검색
          x = int(input('검색할 값을 입력하세요.: '))
          if x in q:
              print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}입니다.')
          else:
              print('검색값을 찾을 수 없습니다.')
  
      elif menu == Menu.덤프:  # 덤프
          q.dump()
      else:
          break

우선순위 큐

• 힙 자료구조를 사용
• 들어간 순서에 상관없이 우선순위가 가장 높은 데이터를 가장 먼저 나옴
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용
• 힙을 쓰는 이유
• 리스트로 하면??
  • 우선순위가 높은 순서대로 앞부분부터 넣으면 반환할때는 앞에꺼 꺼내면 되지만
  • 우선순위가 중간인 것이 들어가려면 이후 데이터의 인덱스를 한칸씩 밀어야함
  • 최악의 경우 삽입해야 하는 위치를 찾기위해 모든 인덱스를 탐색해야 할수도.
  • 이러면 시간복잡도가 삭제는 O(1), 삽입은 O(n)
• 연결리스트로 하면??
  • 우선순위 높은 순서로 연결시키면 반환은 리스트처럼 쉽지만
  • 삽입과정에서 리스트처럼 위치를 찾아야함
  • 이때도 삭제는 O(1), 삽입은 O(n)
• 힙으로 구현하면
  • 삭제나 삽입 과정에서 모두 부모와 자식간의 비교만 이루어짐
• 대부분 라이브러리를 지원하기 때문에 힙을 구현하진 않을 거고
• heapq라이브러리를 쓸거

참고 ::

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

점프 투 파이썬

[파이썬] heapq 모듈 사용법