원형 큐(Circular Queue)와 트리 순회(Tree traversal)

원형 큐(Circular Queue)

• 선형 큐의 문제점을 보완하기 위한 자료구조
• 크기가 정해져 있는 배열(list)
• head, tail이 존재
• empty : head == tail
• full : tail + 1 == head
• tail은 마지막 데이터의 다음을 가리킨다.

  class CQueue:
      MAXSIZE = 10
      
      def __init__(self):
          self.__container = [None for _ in range(CQueue.MAXSIZE)]
          self.__head = 0
          self.__tail = 0
  
      def is_empty(self):
          if self.__head == self.__tail:
              return True
          return False
  
      def is_full(self):
          next = self.__step_forward(self.__tail)
          if next == self.__head:
              return True
          return False
  
      def enqueue(self, data):
          if self.is_full():
              raise Exception("The queue is full.")
          self.__container[self.__tail] = data
          # tail은 마지막 데이터의 다음을 가리킨다.
          self.__tail = self.__step_forward(self.__tail)
  
      def dequeue(self):
          if self.is_empty():
              raise Exception("The queue is empty.")
          
          ret = self.__container[self.__head]
          self.__head = self.__step_forward(self.__head)
          return ret
  
      def peek(self):
          if self.is_empty():
              raise Exception("The queue is empty.")
  
          return self.__container[self.__head]
  
      # 편의 함수
      def __step_forward(self, x):
          x += 1
          if x >= CQueue.MAXSIZE:
              x = 0
          return x
  
  # test code
  if __name__ == "__main__":
      cq = CQueue()
  
      for i in range(8):
          cq.enqueue(i)
  
      for i in range(5):
          print(cq.dequeue(), end=" ")
  
      print()
  
      for i in range(8, 14):
          cq.enqueue(i)
  
      while not cq.is_empty():
          print(cq.dequeue(), end=" ")
  
      print()
  
      for i in range(10):
          print(cq._CQueue__container[i], end="  ")

순회

• 재방문을 허용하지 않고 트리를 구성하는 모든 노드에 다해서 반드시 한번씩 방문하는 것
• Stack 계열의 알고리즘
  • DFS(Depth First Search) : 깊이 우선 탐색
  • 재귀(recursion)와 반복문, stack 자료구조를 통한 구현 - stack frame
  • 전위 순회(preorder traversal)
    • root -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
  • 중위 순회(inorder traversal)
    • 왼쪽 서브 트리 -> root -> 오른쪽 서브 트리
  • 후위 순회(postorder traversal)
    • 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> root

      class Stack:
          def __init__(self):
              self.container = list()
      
          def is_empty(self):
              if not self.container:
                  return True
              else:
                  return False
      
          # 래핑 함수 : 기존에 있던 함수의 기능을 재정의해서 사용하는 함수
          def push(self, data):
              self.container.append(data)
      
          def pop(self):
              return self.container.pop()
      
          def peek(self):
              return self.container[-1]
      
      # traversal(순회)
      # 재방문없이 어떤 자료구조의 모든 데이터(노드)를 방문하는 것
      class TreeNode:
          def __init__(self, data):
              self.data = data
              self.left = None
              self.right = None
      
      # 전위 순회
      def preorder(node):
          # base case
          if not node:
              return
          
          # 방문했다는 표시를 print로 함
          print(node.data, end=' ')
          # 왼쪽 자식
          preorder(node.left)
          # 오른쪽 자식
          preorder(node.right)
      
      # 중위 순회
      def inorder(node):
          # base case
          if not node:
              return
      
          inorder(node.left)
          print(node.data, end=' ')
          inorder(node.right)
          
      # 후위 순회
      def postorder(node):
          # base case
          if not node:
              return
      
          postorder(node.left)
          postorder(node.right)
          print(node.data, end=' ')
      
      # stack을 이용한 전위 순회
      def iter_preorder(cur):
          s = Stack()
      
          while True:
              while cur:
                  # 방문은 print로 표현
                  print(cur.data, end=" ")
                  s.push(cur)
                  cur = cur.left
              if s.is_empty():
                  break
      
              cur = s.pop()
              cur = cur.right
      
      # stack을 이용한 중위 순회
      def iter_inorder(cur):
          s = Stack()
      
          while True:
              while cur:
                  s.push(cur)
                  cur = cur.left
      
              if s.is_empty():
                  break
      
              cur = s.pop()
              # 방문은 print로 표현
              print(cur.data, end=" ")
              cur = cur.right
      
      # stack을 이용한 후위 순회
      def iter_postorder(cur):
          s1 = Stack()
          s2 = Stack()
      
          s1.push(cur)
      
          while not s1.is_empty():
              cur = s1.pop()
              if cur.left:
                  s1.push(cur.left)
              if cur.right:
                  s1.push(cur.right)
              s2.push(cur)
          
          while not s2.is_empty():
              cur = s2.pop()
              # 방문은 print로 표현
              print(cur.data, end = " ")
      
      # test code
      if __name__ == "__main__":
          n1 = TreeNode(1)
          n2 = TreeNode(2)
          n3 = TreeNode(3)
          n4 = TreeNode(4)
          n5 = TreeNode(5)
          n6 = TreeNode(6)
          n7 = TreeNode(7)
      
          n1.left = n2
          n1.right = n3
          n2.left = n4
          n2.right = n5
          n3.left = n6
          n3.right = n7
      
          # preorder(n1)
          # print("")
          # inorder(n1)
          # print("")
          # postorder(n1)
      
          iter_preorder(n1)
          print("")
          iter_inorder(n1)
          print("")
          iter_postorder(n1)