[Algorithm] 스택(Stack), 큐(queue)

스택 (Stack)

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 스택에 저장된 자료는 선형 구조를 가짐
  • 선형 구조 : 자료 간의 관계가 1대 1
  • 비선형 구조 : 자료 간의 관계가 1대 N (예: 트리)
• 후입선출구조 (LIFO; Last-In-Firsh-Out)

 

스택 연산

• 삽입 : 저장소에 자료 저장 (push)
• 삭제 : 저장소에서 자료를 꺼냄, 꺼낸 자료는 삽입한 자료의 역순 (pop)
• 스택이 공백인지 아닌지 확인 : isEmpty
  • 스택에 원소가 있는지가 궁금하다면 연산을 새롭게 정의하지 않고 !isEmpty와 같이 사용
• 스택의 top에 있는 item(원소)을 반환 : peek

 

스택의 삽입/삭제 과정

• 스택 크기 이상의 자료를 push하는 경우 : overflow
• 자료가 없을 때 pop하는 경우 : underflow

 

큐 (Queue)

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
• 선입선출구조(FIFO; First in First Out)
  • 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제됨
    

    

 

큐 연산

• 큐의 기본 연산
  • 삽입 : enQueue
  • 삭제 : deQueue
• 큐의 주요 연산연산기능

  enQueue(item)	큐의 뒤쪽(rear 다음)에 원소를 삽입
  deQueue()	큐의 앞쪽(front)에서 원소를 삭제하고 반환
  createQueue()	공백 상태의 큐를 생성
  isEmpty()	큐가 공백상태인지 확인
  isFull()	큐가 포화상태인지 확인
  Qpeek()	큐의 앞쪽(front)에서 원소를 삭제 없이 반환

 

선형 큐

• 1차원 배열을 이용한 큐
  • 큐의 크기 == 배열의 크기
  • front : 저장된 첫 번째 원소의 인덱스
  • rear : 저장된 마지막 원소의 인덱스
• 상태 표현
  • 초기 상태 : front = rear = -1
  • 공백 상태 : front = rear
  • 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

 

•  

원형 큐

• 초기 공백 상태 : front = rear = 0
• 인덱스의 순환
  • front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동
  • 이를 위해 나머지 연산자 mod 사용
• front 변수
  • 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠
• 삽입/삭제 위치 삽입 위치삭제 위치

  선형 큐	rear = rear + 1	front = front + 1
  원형 큐	rear = (rear + 1) mod n	front = (front + 1) mod n

 

원형 큐에서의 연산

- 초기 공백 큐 생성

 

• 크기 n인 1차원 배열 생성
• front와 rear를 0으로 초기화

 

- 공백 상태 및 포화 상태 검사 : isEmpty(), isFull()

• 공백상태 : front = rear
  

  def isEmpty():
      return front == rear​

• 포화상태 : 삽입할 rear의 다음 위치 = 현재 front
  (rear + 1) mod n = front
  

  def isFull():
      return (rear+1) % len(queue) == front​

- 삽입 : enQueue(item)

 

• 마지막 원소 뒤에 새로운 원소를 삽입하기 위해
  • rear 값을 조정하여 새로운 원소를 삽입할 자리를 마련
    rear = (rear + 1) mod n
  • 그 인덱스에 해당하는 배열원소 queue[rear]에 item 저장

def enQueue(item):
  global rear
  if isFull():
      print('Queue_Full')
  else:
      rear = (rear + 1) % len(queue)
      queue[rear] = item​

 

 

- 삭제 : deQueue(), delete()

 

• • front 값을 조정하여 삭제할 자리 준비
  • 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능

def deQueue():
  global front
  if isEmpty():
      print('Queue_Empty')
  else:
      front = (front + 1) % len(queue)
      return queue[front]

def delete():
  global front
  if isEmpty():
      print('Queue_Empty')
  else:
      front = (front + 1) % len(queue)

 

연결 큐

• 단순 연결 리스트를 이용한 큐
  • 큐의 원소 : 단순 연결 리스트의 노드
  • 큐의 원소 순서 : 노드의 연결 순서, 링크로 연결되어 있음
  • front : 첫 번째 노드를 가리키는 링크
  • rear : 마지막 노드를 가리키는 링크
• 상태 표현
  • 초기 상태 : front = rear = null
  • 공백 상태 : front = rear = null

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

def enQueue(item): # 연결 큐의 삽입 연산
    global front, rear
    new_node = Node(item)  # 새로운 노드 생성
    if front == None :     # 큐가 비어있다면
        front = new_node
    else:
        rear.next = new_node
    rear = new_node

 

우선순위 큐

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
• 기본 연산
  • 삽입 : enQueue
  • 삭제 : deQueue