Chapter 07

큐

Queue

Part 1  큐의 기본 · Queue Basics
Part 2  큐의 일반 구현 · General Queue Implementation
Part 3  원형 큐와 응용 · Circular Queue & Applications

01

Part 1

큐의 기본

Queue Basics

큐의 개념, 원리, 그리고 간단한 구현을 학습합니다.

생활 속 큐 구조

Queue Structures in Daily Life

한국어

우리 주변의 큐

일상생활에서 큐 구조를 쉽게 찾을 수 있습니다.

기차와 터널

기차가 터널에 들어가는 순서대로 터널을 빠져나옵니다.

ATM 대기줄

먼저 줄을 선 사람이 먼저 서비스를 받습니다.

매표소 줄서기

먼저 온 순서대로 표를 구매합니다.

핵심 포인트

먼저 넣은 것이 먼저 나오는 FIFO(First In First Out) 구조가 바로 "큐"입니다! 스택(LIFO)과 반대 개념입니다.

English

Queues Around Us

Queue structures can be easily found in everyday life.

Train & Tunnel

The train exits the tunnel in the same order it entered.

ATM Waiting Line

The first person in line gets served first.

Ticket Booth Line

Tickets are sold in the order people arrived.

Key Point

A FIFO (First In First Out) structure where the first item added is the first removed is called a "Queue"! It's the opposite of a Stack (LIFO).

스택 vs 큐 비교

Stack vs Queue Comparison

한국어

스택과 큐의 차이점

구분	스택 (Stack)	큐 (Queue)
원리	LIFO (후입선출)	FIFO (선입선출)
삽입	push	enQueue
추출	pop	deQueue
확인	peek (top)	peek (front+1)
입/출구	같은 쪽 (top)	다른 쪽 (rear/front)
비유	종이컵 수거함	ATM 대기줄

기억하세요!

스택은 입구 = 출구 (한쪽만), 큐는 입구 ≠ 출구 (양쪽이 다름)!

English

Differences Between Stack and Queue

Category	Stack	Queue
Principle	LIFO (Last In First Out)	FIFO (First In First Out)
Insert	push	enQueue
Remove	pop	deQueue
Peek	peek (top)	peek (front+1)
In/Out	Same end (top)	Different ends (rear/front)
Analogy	Cup collector	ATM waiting line

Remember!

Stack has entrance = exit (one end), Queue has entrance ≠ exit (two different ends)!

큐의 용어와 원리

Queue Terminology & Principles

한국어

큐의 주요 용어

enQueue (인큐) - 삽입

큐에 데이터를 삽입하는 작동. rear(꼬리) 쪽에서 데이터가 들어옵니다.

deQueue (데큐) - 추출

큐에서 데이터를 추출하는 작동. front(머리) 쪽에서 데이터가 나갑니다.

front (머리)

저장된 데이터 중 가장 먼저 들어온 데이터의 바로 앞 위치. 초기값은 -1입니다.

rear (꼬리)

저장된 데이터 중 가장 마지막에 들어온 데이터의 위치. 초기값은 -1입니다.

peek (픽) - 확인

다음에 추출될 데이터를 큐에서 꺼내지 않고 확인만 합니다. front+1 위치의 데이터입니다.

주의!

front는 실제 데이터 위치가 아닌, 가장 앞 데이터의 바로 앞 칸을 가리킵니다. 따라서 실제 첫 번째 데이터는 queue[front+1]에 있습니다.

English

Key Queue Terminology

enQueue - Insert

The operation of inserting data into the queue. Data enters from the rear (tail) side.

deQueue - Remove

The operation of removing data from the queue. Data exits from the front (head) side.

front (head)

The position just before the earliest inserted data. Initial value is -1.

rear (tail)

The position of the most recently inserted data. Initial value is -1.

peek - View

View the next data to be removed without actually removing it. It is at position front+1.

Caution!

front does NOT point to actual data — it points to the position just before the first data. So the actual first element is at queue[front+1].

큐 간단 구현: 생성과 삽입

Simple Queue: Creation & Insertion

한국어

큐 생성 및 enQueue

배열 크기를 지정하여 빈 큐를 생성하고, rear를 증가시키며 데이터를 삽입합니다.

# 큐 생성
queue = [None, None, None, None, None]
front = rear = -1

# 데이터 삽입 (enQueue)
rear += 1
queue[rear] = "화사"
rear += 1
queue[rear] = "솔라"
rear += 1
queue[rear] = "문별"

print('[출구] <-- ', end='')
for i in range(0, len(queue), 1):
    print(queue[i], end=' ')
print('<-- [입구]')

English

Queue Creation & enQueue

Create an empty queue with a fixed size, then insert data by incrementing rear.

# Queue creation
queue = [None, None, None, None, None]
front = rear = -1

# Data insertion (enQueue)
rear += 1
queue[rear] = "화사"
rear += 1
queue[rear] = "솔라"
rear += 1
queue[rear] = "문별"

print('[Exit] <-- ', end='')
for i in range(0, len(queue), 1):
    print(queue[i], end=' ')
print('<-- [Enter]')

1 rear += 1 — move rear forward

2 queue[rear] = data — store data at rear position

3 Repeat for each new item

큐 간단 구현: 추출

Simple Queue: Extraction (deQueue)

한국어

deQueue 과정

front를 증가시키고 해당 위치의 데이터를 꺼낸 후 None으로 비웁니다.

queue = ["화사", "솔라", "문별", None, None]
front = -1
rear = 2

# 첫 번째 추출
front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)   # 화사

# 두 번째 추출
front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)   # 솔라

English

deQueue Process

Increment front, extract data at that position, then set it to None.

queue = ["화사", "솔라", "문별", None, None]
front = -1
rear = 2

# First extraction
front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)   # 화사

# Second extraction
front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)   # 솔라

1 front += 1 — move front forward

2 data = queue[front] — read data

3 queue[front] = None — clear the slot

4 return data — return extracted data

Part 1 연습문제

Part 1 Practice Problems

한국어

연습문제 1-1

크기 5인 빈 큐를 만들고, "정국", "뷔", "지민" 세 명을 차례로 enQueue한 뒤 큐의 상태와 front, rear 값을 출력하시오. 그리고 한 명을 deQueue하여 누가 나왔는지 출력하시오.

## 큐 생성 ##
queue = [None for _ in range(5)]
front = rear = -1

## enQueue 3명 ##
rear += 1
queue[rear] = "정국"
rear += 1
queue[rear] = "뷔"
rear += 1
queue[rear] = "지민"

print("큐 상태:", queue)
print("front:", front, ", rear:", rear)

## deQueue 1명 ##
front += 1
data = queue[front]
queue[front] = None
print("deQueue -->", data)
print("큐 상태:", queue)
print("front:", front, ", rear:", rear)

실행 결과

큐 상태: ['정국', '뷔', '지민', None, None]
front: -1 , rear: 2
deQueue --> 정국
큐 상태: [None, '뷔', '지민', None, None]
front: 0 , rear: 2

연습문제 1-2

큐에 "A", "B", "C", "D"를 삽입한 후 2개를 추출하고, 다시 "E"를 삽입하세요. 각 단계마다 큐 상태, front, rear 값을 출력하시오.

queue = [None] * 5
front = rear = -1

# 4개 삽입
for item in ["A", "B", "C", "D"]:
    rear += 1
    queue[rear] = item
print("삽입 후:", queue, "front:", front, "rear:", rear)

# 2개 추출
for _ in range(2):
    front += 1
    data = queue[front]
    queue[front] = None
    print("deQueue:", data)
print("추출 후:", queue, "front:", front, "rear:", rear)

# 1개 삽입
rear += 1
queue[rear] = "E"
print("삽입 후:", queue, "front:", front, "rear:", rear)

실행 결과

삽입 후: ['A', 'B', 'C', 'D', None] front: -1 rear: 3
deQueue: A
deQueue: B
추출 후: [None, None, 'C', 'D', None] front: 1 rear: 3
삽입 후: [None, None, 'C', 'D', 'E'] front: 1 rear: 4

English

Practice 1-1

Create an empty queue of size 5, enQueue "정국", "뷔", "지민" in order, then print the queue state and front/rear values. Then deQueue one person and print who came out.

## Queue creation ##
queue = [None for _ in range(5)]
front = rear = -1

## enQueue 3 people ##
rear += 1
queue[rear] = "정국"
rear += 1
queue[rear] = "뷔"
rear += 1
queue[rear] = "지민"

print("Queue state:", queue)
print("front:", front, ", rear:", rear)

## deQueue 1 person ##
front += 1
data = queue[front]
queue[front] = None
print("deQueue -->", data)
print("Queue state:", queue)
print("front:", front, ", rear:", rear)

Practice 1-2

Insert "A", "B", "C", "D" into the queue, extract 2, then insert "E". Print the queue state, front, and rear at each step.

queue = [None] * 5
front = rear = -1

# Insert 4 items
for item in ["A", "B", "C", "D"]:
    rear += 1
    queue[rear] = item
print("After insert:", queue, "front:", front, "rear:", rear)

# Extract 2
for _ in range(2):
    front += 1
    data = queue[front]
    queue[front] = None
    print("deQueue:", data)
print("After extract:", queue, "front:", front, "rear:", rear)

# Insert 1 more
rear += 1
queue[rear] = "E"
print("After insert:", queue, "front:", front, "rear:", rear)

02

Part 2

큐의 일반 구현

General Queue Implementation

함수를 활용한 큐의 완성과 개선된 큐를 학습합니다.

큐가 꽉 찼는지 확인 & 삽입 함수

isQueueFull() & enQueue()

한국어

isQueueFull() 함수

rear 값이 SIZE-1과 같으면 큐가 꽉 찬 상태입니다.

def isQueueFull():
    global SIZE, queue, front, rear
    if (rear == SIZE-1):
        return True
    else:
        return False

enQueue() 함수

큐가 꽉 차지 않았으면 rear를 1 증가시키고 데이터를 삽입합니다.

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear += 1
    queue[rear] = data

English

isQueueFull() Function

If rear equals SIZE-1, the queue is full.

def isQueueFull():
    global SIZE, queue, front, rear
    if (rear == SIZE-1):
        return True
    else:
        return False

enQueue() Function

If the queue is not full, increment rear by 1 and insert data.

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("Queue is full.")
        return
    rear += 1
    queue[rear] = data

Key Logic

The queue is full when rear == SIZE - 1, meaning the last index of the array has been reached.

비어있는지 확인 & 추출 & 확인 함수

isQueueEmpty() & deQueue() & peek()

한국어

isQueueEmpty() 함수

front와 rear 값이 같으면 큐가 비어있는 상태입니다.

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

deQueue() 함수

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    return data

peek() 함수

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    return queue[front+1]

English

isQueueEmpty() Function

If front equals rear, the queue is empty.

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

deQueue() Function

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("Queue is empty.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    return data

peek() Function

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("Queue is empty.")
        return None
    return queue[front+1]

Key Difference from Stack

Stack peek returns stack[top], but Queue peek returns queue[front+1] because front is one position before the first data.

전체 소스 코드 Code07-08

Complete Source Code

한국어 - 큐 통합 코드

## 함수 선언 부분 ##
def isQueueFull():
    global SIZE, queue, front, rear
    if (rear == SIZE-1):
        return True
    else:
        return False

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear += 1
    queue[rear] = data

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    return data

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    return queue[front+1]

English - Queue Complete Code

## Function Declarations ##
def isQueueFull():
    global SIZE, queue, front, rear
    if (rear == SIZE-1):
        return True
    else:
        return False

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("Queue is full.")
        return
    rear += 1
    queue[rear] = data

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("Queue is empty.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    return data

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("Queue is empty.")
        return None
    return queue[front+1]

전체 소스 코드 Code07-08 (계속)

Complete Source Code (continued)

한국어 - 메인 코드

## 전역 변수 선언 부분 ##
SIZE = int(input("큐의 크기를 입력하세요 ==> "))
queue = [None for _ in range(SIZE)]
front = rear = -1

## 메인 코드 부분 ##
if __name__ == "__main__":
    select = input("삽입(I)/추출(E)/확인(V)/종료(X) ==> ")

    while (select != 'X' and select != 'x'):
        if select=='I' or select=='i':
            data = input("입력할 데이터 ==> ")
            enQueue(data)
            print("큐 상태 : ", queue)
        elif select=='E' or select=='e':
            data = deQueue()
            print("추출된 데이터 ==> ", data)
            print("큐 상태 : ", queue)
        elif select=='V' or select=='v':
            data = peek()
            print("확인된 데이터 ==> ", data)
            print("큐 상태 : ", queue)
        else:
            print("입력이 잘못됨")

        select = input("삽입(I)/추출(E)/확인(V)/종료(X) ==> ")

    print("프로그램 종료!")

English - Main Code

## Global Variables ##
SIZE = int(input("Enter queue size ==> "))
queue = [None for _ in range(SIZE)]
front = rear = -1

## Main Code ##
if __name__ == "__main__":
    select = input("Insert(I)/Extract(E)/View(V)/Exit(X) ==> ")

    while (select != 'X' and select != 'x'):
        if select=='I' or select=='i':
            data = input("Data to insert ==> ")
            enQueue(data)
            print("Queue state: ", queue)
        elif select=='E' or select=='e':
            data = deQueue()
            print("Extracted data ==> ", data)
            print("Queue state: ", queue)
        elif select=='V' or select=='v':
            data = peek()
            print("Viewed data ==> ", data)
            print("Queue state: ", queue)
        else:
            print("Invalid input")

        select = input("Insert(I)/Extract(E)/View(V)/Exit(X) ==> ")

    print("Program ended!")

순차 큐의 문제점과 개선

Sequential Queue Problem & Improvement

한국어

순차 큐의 문제점

앞쪽에 빈 공간이 있어도 rear가 끝에 도달하면 "꽉 찼다"고 판단합니다.

해결 방법: 데이터를 앞으로 이동

rear가 끝에 도달했지만 앞에 빈 칸이 있으면, 데이터를 왼쪽으로 이동시킵니다.

def isQueueFull():
    global SIZE, queue, front, rear
    if (rear != SIZE-1):
        return False
    elif (rear == SIZE-1) and (front == -1):
        return True
    else:
        for i in range(front+1, SIZE):
            queue[i-1] = queue[i]
            queue[i] = None
        front -= 1
        rear -= 1
        return False

English

Sequential Queue Problem

Even with empty spaces at the front, when rear reaches the end, it reports "full".

The Problem

After several deQueue operations, the front slots are empty. But since rear == SIZE-1, isQueueFull() returns True, wasting space!

Solution: Shift Data Forward

When rear hits the end but front slots are empty, shift all data left.

1 rear != SIZE-1 → Not full (False)

2 rear == SIZE-1 AND front == -1 → Truly full (True)

3 rear == SIZE-1 AND front != -1 → Shift data left, adjust front/rear, return False

Trade-off

Shifting data works but takes O(n) time. For large queues (e.g., 100,000 elements), this causes significant overhead. The solution? Circular Queue (Part 3)!

Part 2 연습문제

Part 2 Practice Problems

한국어

연습문제 2-1 : 맛집 대기줄

유명 맛집의 대기줄을 큐로 구현하시오. 5명이 차례로 줄을 서고, 한 명씩 식당에 들어갑니다. deQueue 할 때 나머지 사람들을 앞으로 이동시키시오.

## 함수 선언 부분 ##
def isQueueFull():
    global SIZE, queue, front, rear
    if (rear == SIZE-1):
        return True
    else:
        return False

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear += 1
    queue[rear] = data

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None

    for i in range(front+1, rear+1):
        queue[i-1] = queue[i]
        queue[i] = None
    front = -1
    rear -= 1
    return data

## 전역 변수 ##
SIZE = 5
queue = [None for _ in range(SIZE)]
front = rear = -1

## 메인 코드 ##
enQueue('정국')
enQueue('뷔')
enQueue('지민')
enQueue('진')
enQueue('슈가')
print("대기 줄 상태 : ", queue)

for _ in range(rear+1):
    print(deQueue(), '님 식당에 들어감')
    print("대기 줄 상태 : ", queue)

print("식당 영업 종료!")

연습문제 2-2

개선된 isQueueFull() 함수(데이터 이동 방식)를 포함한 완전한 큐를 작성하고, 사용자 입력으로 삽입/추출/확인/종료 메뉴를 구현하시오.

## 함수 선언 부분 ##
def isQueueFull():
    global SIZE, queue, front, rear
    if (rear != SIZE-1):
        return False
    elif (rear == SIZE-1) and (front == -1):
        return True
    else:
        for i in range(front+1, SIZE):
            queue[i-1] = queue[i]
            queue[i] = None
        front -= 1
        rear -= 1
        return False

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear += 1
    queue[rear] = data

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    return data

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    return queue[front+1]

## 전역 변수 ##
SIZE = int(input("큐의 크기를 입력하세요 ==> "))
queue = [None for _ in range(SIZE)]
front = rear = -1

## 메인 코드 ##
if __name__ == "__main__":
    select = input("삽입(I)/추출(E)/확인(V)/종료(X) ==> ")
    while (select != 'X' and select != 'x'):
        if select=='I' or select=='i':
            data = input("입력할 데이터 ==> ")
            enQueue(data)
            print("큐 상태 : ", queue)
        elif select=='E' or select=='e':
            data = deQueue()
            print("추출된 데이터 ==> ", data)
            print("큐 상태 : ", queue)
        elif select=='V' or select=='v':
            data = peek()
            print("확인된 데이터 ==> ", data)
            print("큐 상태 : ", queue)
        else:
            print("입력이 잘못됨")
        select = input("삽입(I)/추출(E)/확인(V)/종료(X) ==> ")
    print("프로그램 종료!")

English

Practice 2-1 : Restaurant Waiting Line

Implement a restaurant waiting line using a queue. 5 people line up in order, and each enters the restaurant one by one. When deQueuing, shift remaining people forward.

# See Korean column for full code
# Key difference in deQueue:
# After removing front item,
# shift everyone forward

def deQueue():
    global SIZE, queue, front, rear
    if isQueueEmpty():
        print("Queue is empty.")
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    # Shift everyone forward
    for i in range(front+1, rear+1):
        queue[i-1] = queue[i]
        queue[i] = None
    front = -1
    rear -= 1
    return data

Practice 2-2

Write a complete queue with the improved isQueueFull() (data shifting), and implement an interactive menu for Insert/Extract/View/Exit.

See the Korean column for the complete source code (Code07-10). The key improvement is the 3-case isQueueFull() that shifts data left when rear hits the end but front slots are empty.

03

Part 3

원형 큐와 응용

Circular Queue & Applications

원형 큐의 개념, 구현, 그리고 실전 응용을 학습합니다.

원형 큐의 개념

Circular Queue Concept

한국어

왜 원형 큐가 필요한가?

순차 큐의 한계

크기 10만인 큐에서 앞쪽 일부만 비어 있고 나머지가 꽉 찬 경우, 데이터 이동에 엄청난 시간(오버헤드)이 발생합니다.

원형 큐 = 끝과 처음을 연결!

순차 큐를 구부려서 끝을 이으면 원형 큐가 됩니다. 데이터 이동 없이 front와 rear가 순환합니다.

English

Why Do We Need a Circular Queue?

Sequential Queue Limitation

In a queue of size 100,000 where only a few front slots are empty, shifting all data causes enormous overhead.

Circular Queue = Connect End to Start!

By bending the sequential queue into a ring, front and rear wrap around — no data movement needed.

Key Formula

Instead of rear += 1, we use:
rear = (rear + 1) % SIZE
This makes the index wrap around: after the last slot, it goes back to 0.

Initialization Difference

Sequential queue: front = rear = -1
Circular queue: front = rear = 0

Advantages

No data shifting needed! O(1) for both enQueue and deQueue. The circular structure reuses empty front slots automatically.

원형 큐: 빈 상태 vs 꽉 찬 상태

Circular Queue: Empty vs Full

한국어

빈 상태 확인

front == rear 이면 비어 있음

초기값 front=0, rear=0에서 시작합니다. front와 rear가 같으면 큐가 비어있습니다.

꽉 찬 상태 확인

(rear + 1) % SIZE == front 이면 꽉 참

rear의 다음 칸이 front와 같으면 큐가 꽉 찬 것입니다. 이 때문에 원형 큐는 한 칸을 비워둡니다.

주의: 한 칸은 항상 비워둡니다!

크기 5인 원형 큐에는 최대 4개의 데이터만 저장할 수 있습니다. 한 칸을 비워서 "꽉 참"과 "비어 있음"을 구분합니다.

English

Checking Empty State

front == rear → Empty

Starting from front=0, rear=0. When front and rear are equal, the queue is empty.

Checking Full State

(rear + 1) % SIZE == front → Full

When rear's next position equals front, the queue is full. That's why a circular queue always leaves one slot empty.

# Empty check
def isQueueEmpty():
    if (front == rear):
        return True
    return False

# Full check
def isQueueFull():
    if ((rear+1) % SIZE == front):
        return True
    return False

Warning: One Slot Always Empty!

A circular queue of size 5 can only store 4 items max. The empty slot distinguishes "full" from "empty".

원형 큐: 삽입과 추출

Circular Queue: enQueue & deQueue

한국어

enQueue - 원형 큐 삽입

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear = (rear + 1) % SIZE
    queue[rear] = data

deQueue - 원형 큐 추출

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front = (front + 1) % SIZE
    data = queue[front]
    queue[front] = None
    return data

peek - 원형 큐 확인

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    return queue[(front + 1) % SIZE]

핵심: % (나머지 연산)

모든 인덱스 계산에 % SIZE를 사용하여 배열 끝을 넘어가면 자동으로 처음으로 돌아옵니다!

English

enQueue - Circular Queue Insert

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("Queue is full.")
        return
    rear = (rear + 1) % SIZE
    queue[rear] = data

deQueue - Circular Queue Remove

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("Queue is empty.")
        return None
    front = (front + 1) % SIZE
    data = queue[front]
    queue[front] = None
    return data

peek - Circular Queue View

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("Queue is empty.")
        return None
    return queue[(front + 1) % SIZE]

% Modulo Example (SIZE = 5)

(4 + 1) % 5 = 0 → wraps to start!
(2 + 1) % 5 = 3 → normal increment
(3 + 1) % 5 = 4 → normal increment

전체 소스 코드 Code07-11 (원형 큐)

Complete Circular Queue Code

한국어 - 원형 큐 전체 코드

## 함수 선언 부분 ##
def isQueueFull():
    global SIZE, queue, front, rear
    if ((rear + 1) % SIZE == front):
        return True
    else:
        return False

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear = (rear + 1) % SIZE
    queue[rear] = data

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front = (front + 1) % SIZE
    data = queue[front]
    queue[front] = None
    return data

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    return queue[(front + 1) % SIZE]

English - Circular Queue Full Code

## Global Variables ##
SIZE = int(input("Enter queue size ==> "))
queue = [None for _ in range(SIZE)]
front = rear = 0

## Main Code ##
if __name__ == "__main__":
    select = input("Insert(I)/Extract(E)/View(V)/Exit(X) ==> ")

    while (select != 'X' and select != 'x'):
        if select=='I' or select=='i':
            data = input("Data to insert ==> ")
            enQueue(data)
            print("Queue state: ", queue)
            print("front:", front, ", rear:", rear)
        elif select=='E' or select=='e':
            data = deQueue()
            print("Extracted ==> ", data)
            print("Queue state: ", queue)
            print("front:", front, ", rear:", rear)
        elif select=='V' or select=='v':
            data = peek()
            print("Viewed ==> ", data)
            print("Queue state: ", queue)
            print("front:", front, ", rear:", rear)
        else:
            print("Invalid input")

        select = input("Insert(I)/Extract(E)/View(V)/Exit(X) ==> ")

    print("Program ended!")

Circular vs Sequential

Notice: front = rear = 0 (not -1), and all index operations use % SIZE.

응용 예제: 콜센터 대기 시간

Application: Call Center Wait Time

한국어

콜센터 응답 대기 시간 계산

각 전화에 (유형, 소요시간) 튜플을 사용하여 원형 큐로 대기 시간을 계산합니다.

## 원형 큐 함수 생략 (위와 동일) ##

def calcTime():
    global SIZE, queue, front, rear
    timeSum = 0
    for i in range((front+1)%SIZE, (rear+1)%SIZE):
        timeSum += queue[i][1]
    return timeSum

## 전역 변수 ##
SIZE = 6
queue = [None for _ in range(SIZE)]
front = rear = 0

## 메인 코드 ##
waitCall = [('사용',9), ('고장',3), ('환불',4),
            ('환불',4), ('고장',3)]

for call in waitCall:
    print("대기 예상시간:", calcTime(), "분")
    print("현재 대기 콜 -->", queue)
    enQueue(call)
    print()

print("최종 대기 콜 -->", queue)

실행 결과

대기 예상시간: 0 분
현재 대기 콜 --> [None, None, None, None, None, None]

대기 예상시간: 9 분
현재 대기 콜 --> [None, ('사용', 9), None, None, None, None]

대기 예상시간: 12 분
...
최종 대기 콜 --> [None, ('사용', 9), ('고장', 3), ('환불', 4), ('환불', 4), ('고장', 3)]

English

Call Center Wait Time Calculation

Each call is a tuple (type, duration). Use a circular queue to calculate waiting time.

## Circular queue funcs (same as above) ##

def calcTime():
    global SIZE, queue, front, rear
    timeSum = 0
    for i in range((front+1)%SIZE, (rear+1)%SIZE):
        timeSum += queue[i][1]
    return timeSum

## Global Variables ##
SIZE = 6
queue = [None for _ in range(SIZE)]
front = rear = 0

## Main Code ##
waitCall = [('Usage',9), ('Broken',3), ('Refund',4),
            ('Refund',4), ('Broken',3)]

for call in waitCall:
    print("Expected wait:", calcTime(), "min")
    print("Current calls -->", queue)
    enQueue(call)
    print()

print("Final calls -->", queue)

Real-World Use

This is exactly how real call centers work! New calls enQueue at the back, and the operator deQueues from the front. The wait time is the sum of all preceding call durations.

순차 큐 vs 원형 큐 비교 정리

Sequential vs Circular Queue Summary

한국어

비교 정리

구분	순차 큐	원형 큐
초기값	front=rear=-1	front=rear=0
꽉 참 조건	rear == SIZE-1	(rear+1)%SIZE == front
비어 있음	front == rear	front == rear
삽입 방식	rear += 1	rear = (rear+1)%SIZE
추출 방식	front += 1	front = (front+1)%SIZE
공간 재활용	데이터 이동 필요	자동 순환
최대 저장	SIZE개	SIZE-1개
시간 복잡도	이동 시 O(n)	항상 O(1)

결론

실무에서는 대부분 원형 큐를 사용합니다. 데이터 이동 오버헤드가 없고 효율적이기 때문입니다!

English

Comparison Summary

Category	Sequential Queue	Circular Queue
Initial	front=rear=-1	front=rear=0
Full	rear == SIZE-1	(rear+1)%SIZE == front
Empty	front == rear	front == rear
Insert	rear += 1	rear = (rear+1)%SIZE
Remove	front += 1	front = (front+1)%SIZE
Space Reuse	Requires shifting	Auto circular
Max Storage	SIZE items	SIZE-1 items
Time	O(n) for shift	Always O(1)

Conclusion

In practice, Circular Queues are preferred because they have no data shifting overhead and are always O(1)!

Part 3 연습문제

Part 3 Practice Problems

한국어

연습문제 3-1 : 원형 큐 인터랙티브

원형 큐를 구현하고, 삽입/추출/확인/종료 메뉴를 통해 사용자가 직접 큐를 조작할 수 있게 하시오. 매 조작마다 큐 상태와 front, rear 값을 출력하시오.

## 함수 선언 부분 ##
def isQueueFull():
    global SIZE, queue, front, rear
    if ((rear + 1) % SIZE == front):
        return True
    else:
        return False

def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False

def enQueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print("큐가 꽉 찼습니다.")
        return
    rear = (rear + 1) % SIZE
    queue[rear] = data

def deQueue():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    front = (front + 1) % SIZE
    data = queue[front]
    queue[front] = None
    return data

def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print("큐가 비었습니다.")
        return None
    return queue[(front + 1) % SIZE]

## 전역 변수 선언 부분 ##
SIZE = int(input("큐의 크기를 입력하세요 ==> "))
queue = [None for _ in range(SIZE)]
front = rear = 0

## 메인 코드 부분 ##
if __name__ == "__main__":
    select = input("삽입(I)/추출(E)/확인(V)/종료(X) ==> ")
    while (select != 'X' and select != 'x'):
        if select=='I' or select=='i':
            data = input("입력할 데이터 ==> ")
            enQueue(data)
            print("큐 상태 : ", queue)
            print("front :", front, ", rear :", rear)
        elif select=='E' or select=='e':
            data = deQueue()
            print("추출된 데이터 ==> ", data)
            print("큐 상태 : ", queue)
            print("front :", front, ", rear :", rear)
        elif select=='V' or select=='v':
            data = peek()
            print("확인된 데이터 ==> ", data)
            print("큐 상태 : ", queue)
            print("front :", front, ", rear :", rear)
        else:
            print("입력이 잘못됨")
        select = input("삽입(I)/추출(E)/확인(V)/종료(X) ==> ")
    print("프로그램 종료!")

연습문제 3-2 : 콜센터 대기 시간

원형 큐를 이용하여 콜센터 대기 시간을 계산하시오. 5개의 전화가 ('사용',9), ('고장',3), ('환불',4), ('환불',4), ('고장',3) 순서로 들어올 때, 각 전화마다 현재 대기 시간을 출력하시오.

## 원형 큐 함수 (위 3-1과 동일) ##
## + calcTime 함수 추가 ##

def calcTime():
    global SIZE, queue, front, rear
    timeSum = 0
    for i in range((front+1)%SIZE, (rear+1)%SIZE):
        timeSum += queue[i][1]
    return timeSum

## 전역 변수 ##
SIZE = 6
queue = [None for _ in range(SIZE)]
front = rear = 0

## 메인 코드 ##
if __name__ == "__main__":
    waitCall = [('사용',9), ('고장',3),
                ('환불',4), ('환불',4),
                ('고장',3)]

    for call in waitCall:
        print("귀하의 대기 예상시간은",
              calcTime(), "분입니다.")
        print("현재 대기 콜 -->", queue)
        enQueue(call)
        print()

    print("최종 대기 콜 -->", queue)
    print("프로그램 종료!")

English

Practice 3-1 : Interactive Circular Queue

Implement a circular queue with an Insert/Extract/View/Exit menu. Print the queue state, front, and rear after each operation.

See the Korean column for the complete source code (Code07-11). Key points: front = rear = 0, all index operations use % SIZE.

Practice 3-2 : Call Center Wait Time

Using a circular queue, calculate call center wait times. 5 calls arrive: ('Usage',9), ('Broken',3), ('Refund',4), ('Refund',4), ('Broken',3). Print the current wait time for each call.

# Add calcTime() to circular queue:

def calcTime():
    global SIZE, queue, front, rear
    timeSum = 0
    for i in range((front+1)%SIZE,
                   (rear+1)%SIZE):
        timeSum += queue[i][1]
    return timeSum

# SIZE = 6 (5 calls + 1 empty slot)
# front = rear = 0
# Loop through waitCall list,
# print calcTime() then enQueue

Expected Output

Expected wait: 0 min
Expected wait: 9 min
Expected wait: 12 min
Expected wait: 16 min
Expected wait: 20 min