Questions

  • Stack과 Queue의 차이점은 무엇인가요? (N사 전화면접)
  • 큐 삽입(enqueue) / 삭제(dequeue) 함수를 배열 / 링크드리스트로 구현하라.
  • 스택 2개로 큐 1개를 구현한 MyQueue 클래스를 구현하라.


Queue

Stack과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조 (뒤에서 삽입, 앞에서 삭제)

ex: 줄서기

Untitled

특징

  • 선입선출구조 (FIFO, First-In, First-Out)

    **: queue에 삽입한 순서대로 원소가 저장되고, 가장 먼저 삽입된 원소가 가장 먼저 삭제됨

  • Front (머리) : Queue의 맨 앞. 즉, 저장된 원소 중 첫 번째 원소
  • Rear (맨 뒤) : Queue의 맨 뒤. 저장된 원소 중 마지막 원소


Queue의 활용 예 : Buffer(버퍼)

Queue를 활용한 또 다른 예

버퍼란?

  • 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
  • 물리적인 장치의 처리 속도 차에서 발생하는 대기 시간을 극복하기 위한 방법
  • 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용됨
  • 버퍼링 : 버퍼를 활용하는 방식, 또는 버퍼를 채우는 동작

버퍼의 자료 구조

  • 데이터를 전송하는 동안 일시적으로 저장하는 영역이므로, 순서대로 데이터가 전달되어야 함

          → **FIFO** (선입선출) 방식 필요


버퍼의 활용

Queue의 종류

Lec01/Untitled 2



Linear Queue (선형 큐)

선형 Queue를 구현하는 방법은 여러 가지가 있지만,

보통 선형 자료 구조 중 하나인 1차원 리스트를 이용하여 구현한다.

  • Queue의 크기 = 리스트의 크기
  • front : 저장된 첫 번째의 원소의 index, rear : 저장된 마지막 원소의 index

  • Queue의 상태 표현

    초기 상태 비어 있기 때문에 저장된 원소가 없음
    front, rear = -1  
    공백 상태 초기 상태 이외에 Queue가 비어 있는 상태
    front = rear  
    포화 상태 Queue가 가득 차있는 상태. (n : 리스트의 크기, n-1 : 리스트의 마지막 인덱스)
    rear = n-1  


선형 큐 구현 과정


초기 공백 Queue 생성

  • 크기가 n인 1차원 리스트를 생성
  • front와 rear값을 -1로 초기화


삽입 (enQueue(item))

def enQueue(item):      # enqueue 과정 구현
	global rear
	if isFull() : print("Queue_Full")      # queue가 가득 찬 상태에서는 더 이상 원소 삽입 불가
	else : 
		rear += 1
		Q[rear] = item
  • rear값을 하나 증가시켜 새로운 원소 삽입할 자리를 마련

  • 그 index에 해당하는 리스트 원소 Q[rear]에 item을 저장

    ※ rear = n-1인 상태 (queue가 가득 찬 상태)에서는 더 이상 원소를 삽입할 수 없기 때문에 queue가 가득 차 있음을 알려주어야 함


삭제 (deQueue())

def deQueue():
	global front
	if isEmpty() : print("Queue_Empty")      # queue가 빈 상태에서는 더 이상 원소 삭제 불가하기 때문에 비어있음을 알려주어야 함

	else: 
		front += 1
		return Q[front]
  • front값을 하나 증가시켜 queue에 남아있는 첫 번째 원소로 이동

  • 새로운 첫 번째 요소를 return (삭제와 동일한 기능을 함)

    ※ queue가 비어있는 상태에서는 더 이상 원소를 삽입할 수 없기 때문에 queue가 비어있음을 알려주어야 함


isEmpty(), isFull()

def isEmpty() :                          # 공백 상태
	return front == rear

def isFull() :                           # 포화 상태
	return rear == len(Q) - 1
  • 공백 상태 / 반환상태인 경우 각 알고리즘에 따라 참/거짓을 반환


Qpeek()

def Qpeek():
	if isEmpty() : print("Queue_Empty")    # Queue가 비어있을 경우 비어있다고 알려줌
	else : return Q[front+1]               # Queue의 첫 번째에 있는 원소 반환
  • queue의 맨 앞에 있는 원소를 검색하는 연산

  • 현재 front의 한 자리 뒤 즉, queue의 첫 번째에 있는 원소 반환

    ※ 여기서 주의할 점은 front의 값이 변경되지 않아야 한다는 것!


선형 Queue의 문제점

리스트의 크기를 고정해서 구현한 선형 큐는 메모리 낭비 / 잘못된 포화 인식 문제가 발생한다.

**문제 1 메모리의 낭비**

리스트의 크기 고정 → 사용할 queue의 크기만큼 미리 확보해야 함 → 메모리의 낭비 발생

**문제 2 잘못된 포화상태 인식**

Lec01/Untitled 3

   원소의 삽입/삭제 반복 →  rear = n-1인 상태(=포화 상태)로 인식

                            → 리스트의 앞부분에 공간이 있음에도 더 이상의 삽입을 수행하지 않게 됨


선형 Queue의 장단점

Lec01/Untitled 4


단점 해결 방법

  • 원형 Queue 사용으로 메모리 절약 가능
  • Python의 리스트 특성(동적 변경 가능)을 사용한 Queue 사용으로 메모리 절약
  • Singly Linked List로 구현한 Queue 사용으로 메모리 동적 확보
  • Queue 라이브러리를 사용하여 구현



Circular Queue (원형 큐)

선형 Queue의 단점 보완한 해결 방법

  • 1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 Queue를 이룬다고 가정하고 사용하는 방법

    Lec01/Untitled 5


원형 큐 특징

  • 초기 공백 상태

    : front, rear = 0 (↔ 선형 queue : front, rear = -1)

  • Index의 순환

    : front, rear이 n-1(리스트의 마지막 인덱스) 가리킨 후, 0 (리스트의 첫 인덱스)으로 이동

    : 이를 위해 나머지 연산자 % 이용

  • front 변수

    : 공백 상태/포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈 자리로 둠

  • 삽입 위치 및 삭제 위치

      삽입 위치 삭제 위치
    선형 Queue rear = rear + 1 front = front + 1
    원형 Queue rear = (rear +1) % n front = (front + 1) % n

    ※ 삽입, 삭제의 위치가 n보다 커질 경우 %n을 통해 index 재조정


원형 Queue의 연산 과정

  1. Queue 생성

     createQueue()

    Lec01/Untitled 6

    front, rear = 0 (초기화)

  2. 원소 A 삽입

     enQueue(A)

    Lec01/Untitled 7

    front = 0, rear+=1, Q[rear] = A

  3. 원소 B 삽입

     enQueue(B)

    Lec01/Untitled 8

    front = 0, rear+=1, Q[rear] = B

  4. 원소 삭제

     deQueue()

    Lec01/Untitled 9

    front+=1, Q[front] 삭제

  5. 원소 C 삽입

     enQueue(C)

    Lec01/Untitled 10

    front = 1, rear+=1, Q[rear] = C

  6. 원소 D 삽입

    Lec01/Untitled 11

    포화상태가 됨 (front자리 사용 X)


원형 큐 구현

초기 공백 Queue 생성

  • 크기가 n인 1차원 리스트 cQ를 생성
  • front와 rear값을 0으로 초기화

isEmpty(), isFull()

def isEmpty() :                          # 공백 상태
	return front == rear

def isFull() :                           # 포화 상태
	return (rear+1) % len(cQ) == front
  • 공백 상태 : front == rear
  • 포화 상태 : 삽입할 rear의 다음 위치 = 현재 front
  • 공백 상태 / 반환상태인 경우 각 알고리즘에 따라 참/거짓을 반환

삽입 (enQueue(item))

def enQueue(item):      # enqueue 과정 구현
	global rear

	if isFull() : 
		print("Queue_Full")      # queue가 가득 찬 상태에서는 더 이상 원소 삽입 불가

	else : 
		rear = (rear + 1) % len(cQ)
		cQ[rear] = item
  • rear값을 조정(+1와 %)하여 새로운 원소 삽입할 자리를 마련

  • 그 index에 해당하는 리스트 원소 cQ[rear]에 item을 저장

    ※ Queue가 포화인지 꼭 check

삭제 (deQueue())

def deQueue():
	global front

	if isEmpty() :       # queue가 빈 상태에서는 더 이상 원소 삭제 불가하기 때문에 비어있음을 알려주어야 함
		print("Queue_Empty")

	else: 
		front = (front + 1) % len(cQ)
		return cQ[front]
  • front값을 조정(+1와 %)하여 삭제할 자리를 준비

  • 새로운 front 원소를 return (삭제와 동일한 기능을 함)

    ※ Queue가 공백인지 꼭 check

Python으로 구현한 원형 큐의 삽입 및 삭제 함수

def isEmpty() :
	return front == rear

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

def enQueue(item):      # 원형 Queue의 삽입 연산
	global rear
	if isFull() : 
		print("Queue_Full")
	else : 
		rear = (rear + 1) % len(cQ)
		cQ[rear] = item

def deQueue():      # 원형 Queue의 삭제 연산
	global front
	if isEmpty() :
		print("Queue_Empty")
	else: 
		front = (front + 1) % len(cQ)
		return cQ[front]

cQ_SIZE = 3
cQ = [0] * cQ_SIZE

# front, rear를 0으로 초기화
front = rear = 0

enQueue('A')
enQueue('B')
enQueue('C')
print(deQueue())
print(deQueue())
print(deQueue())      # FIFO 구조 확인 가능