Blog Image

Per ardua ad astra.

"Hello, World!" 🤖

250x250

📅

D-Day

Microsoft Student (2023)👨🏻‍💻

Computer Science/자료구조

[Python] 큐(Queue)

2022. 7. 1. 22:56

728x90

큐(Queue)

큐(Queue)

선입선출(First In First Out, FIFO)의 특징을 갖는 자료구조
큐는 양쪽이 뚫려 있는 구조이다.
- 한쪽에서는 삽입만 진행되고, 다른 쪽에서는 추출만 진행된다.
큐에 데이터를 삽입하는 동작을 enQueue(인큐)라고 하며, 데이터를 추출하는 동작을 deQueue(데큐)라고 한다.
큐의 중요한 용어로 front(머리)와 rear(꼬리)가 있다.
- 머리는 저장된 데이터 중 첫 번째 데이터를 가리킨다.
- 꼬리는 저장된 데이터 중 마지막 데이터를 가리킨다.
첫 번째 데이터 앞을 front가 가리켜야 한다.

데이터 삽입 : enQueue

데이터 추출 : deQueue

구현

① 큐의 초기화

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

② 데이터 삽입

큐가 꽉 찼는지 확인하는 함수

데이터를 삽입할 때는 큐가 이미 꽉 찼는지 확인해야 한다.
rear 값이 '큐 크기-1' 과 같다면 큐가 꽉 찬 상태다.

if (rear값 == 큐크기-1) :
    큐가 꽉 찼음.

함수 완성하기

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

SIZE = 5
queue = ["화사", "솔라", "문별", "휘인", "선미"]
front = -1
rear = 4

print("큐가 꽉 찼는지 여부 ==>", isQueueFull())

큐가 꽉 찼는지 여부 ==> True

큐에 데이터를 삽입하는 함수

먼저 큐가 꽉 찼는지 확인하고, 여유가 있다면 데이터를 삽입한다.

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

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

SIZE = 5
queue = ["화사", "솔라", "문별", "휘인", None]
front = -1
rear = 3

print(queue)
enQueue("선미")
print(queue)
enQueue("태연")

['화사', '솔라', '문별', '휘인', None]
['화사', '솔라', '문별', '휘인', '선미']
큐가 꽉 찼습니다.

isQueueFull() 함수를 없애고, enQueue() 함수만으로 기능 구현하기

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

SIZE = 5
queue = ["화사", "솔라", "문별", "휘인", None]
front = -1
rear = 3

print(queue)
enQueue("선미")
print(queue)
enQueue("태연")

③ 데이터 추출

데이터를 추출하기 전에 먼저 스택에 데이터가 있는지 확인해야 한다.
스택에 데이터가 없는데도 데이터를 추출하려고 시도할 때는 별도의 조치를 취해야 한다.

큐가 비었는지 확인하는 함수

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

if (front값 == rear값) :
    큐가 비었음.

함수 완성하기

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

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

print("큐가 비었는지 여부 ==>", isQueueEmpty())

큐가 비었는지 여부 ==> True

큐에서 데이터를 추출하는 함수

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

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

SIZE = 5
queue = ["화사", None, None, None, None]
front = -1
rear = 0

print(queue)
retData = deQueue()
print("추출한 데이터 -->", retData)
print(queue)
retData = deQueue()

['화사', None, None, None, None]
추출한 데이터 --> 화사
[None, None, None, None, None]
큐가 비었습니다.

isQueueEmpty() 함수를 없애고, deQueue() 함수만으로 기능 구현하기

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

SIZE = 5
queue = ["화사", None, None, None, None]
front = -1
rear = 0

print(queue)
retData = deQueue()
print("추출한 데이터 -->", retData)
print(queue)
retData = deQueue()

④ 데이터 확인

다음에 추출된 데이터를 큐에 그대로 두고 확인만 하는 것을 Peek(픽)이라고 한다.
front+1 위치의 값을 확인한 후 front 값은 변경 없이 그대로 두는 것이다.

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

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

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

print(queue)
retData = peek()
print("다음에 추출될 데이터 확인 -->", retData)
print(queue)

['화사', '솔라', '문별', None, None]
다음에 추출될 데이터 확인 --> 화사
['화사', '솔라', '문별', None, None]

큐 완성

기능 통합 버전

앞서 작성한 큐의 데이터 삽입, 추출, 확인을 통합한 코드를 작성해본다.

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]

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("프로그램 종료!")

큐의 크기를 입력하세요 ==> 5
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 화사
큐 상태 :  ['화사', None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 솔라
큐 상태 :  ['화사', '솔라', None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 문별
큐 상태 :  ['화사', '솔라', '문별', None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==>  화사
큐 상태 :  [None, '솔라', '문별', None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==>  솔라
큐 상태 :  [None, None, '문별', None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==>  문별
큐 상태 :  [None, None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
큐가 비었습니다.
추출된 데이터 ==>  None
큐 상태 :  [None, None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> X
프로그램 종료!

기능 통합 버전 개선

앞서 작성한 큐는 잘 작동하는 것처럼 보이지만, 약간의 문제점이 있다.
- deQueue를 하면 큐의 앞쪽은 계속 비워지지만 다시 사용하지는 않는다.
- 크기가 5칸인 큐는 초기 상태에서 front와 rear가 모두 -1을 가리키다 데이터를 5개 삽입하면 여유 공간이 없어 더 이상 데이터가 입력되지 않는다.
  - 이 상태에서 두 번 deQueue하면 앞의 두 요소가 추출되어 앞쪽에 여유 공간이 2칸 생겨도 더 이상 데이터가 삽입되지 않는다.
- 한 번 큐가 꽉 차면 rear가 '큐 크기-1'로 고정되고, 앞쪽에 여유 공간이 생겨도 rear 값은 변경되지 않기 때문에 앞쪽 공간을 사용할 수 없다.
이 문제를 해결하려면 큐 데이터를 앞으로 한 칸 당긴 후 삽입하면 된다.

if (rear값 != 큐크기-1) :
    큐가 꽉 차지 않았음.
elif (rear값 == 큐크기-1) and (front == -1) :
    큐가 꽉 찼음.
else :
    데이터를 앞으로 당기면 큐가 꽉 차지 않음.

① rear ≠ 큐 크기-1인 경우

현재 rear 값은 2이고, '큐 크기-1'의 값은 4이므로, 두 값이 같지 않아 rear 뒤에 여유가 있는 상태이다.
큐가 꽉 차지 않았다는 의미의 False를 반환한다.

② rear = 큐 크기-1, front = -1인 경우

rear 가 '큐 크기-1' 값인 4와 같고, front도 맨 앞인 -1이라면 더 이상 공간이 없다.
큐가 꽉 찼다는 의미의 True를 반환한다.

③ rear = 큐 크기-1, front ≠ -1인 경우

rear 가 '큐 크기-1' 값인 4와 같지만, front가 -1이 아닌 상태이다.
즉, 앞에 여유 공간이 있는 경우이다.

이때는 다음 순서로 전체를 왼쪽으로 한 칸씩 이동시켜 마지막에 빈칸을 만들어야 한다.

① front+1 위치부터 rear 위치까지 왼쪽으로 한 칸씩 이동시킨다.
② front 값에서 1을 뺀다. (front를 왼쪽으로 한 칸 이동한다.)
③ rear 값에서 1을 뺀다. (rear를 왼쪽 한 칸 이동한다.)
④ 큐가 꽉 차지 않았다는 의미의 False를 반환한다.

큐가 꽉 찼는지 확인하는 함수 개선 버전

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

SIZE = 5
queue = [None, None, "문별", "휘인", "선미"]
front = 1
rear = 4

print("큐가 꽉 찼는지 여부 ==>", isQueueFull())
print("큐 상태 ==> ", queue)

큐가 꽉 찼는지 여부 ==> False
큐 상태 ==>  [None, '문별', '휘인', '선미', None]

개선된 큐 완성

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("프로그램 종료!")

큐의 크기를 입력하세요 ==> 5
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> I
입력할 데이터 ==> 화사
큐 상태 :  ['화사', None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> I
입력할 데이터 ==> 솔라
큐 상태 :  ['화사', '솔라', None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> I
입력할 데이터 ==> 문별
큐 상태 :  ['화사', '솔라', '문별', None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> I
입력할 데이터 ==> 휘인
큐 상태 :  ['화사', '솔라', '문별', '휘인', None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> I
입력할 데이터 ==> 선미
큐 상태 :  ['화사', '솔라', '문별', '휘인', '선미']
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> E
추출된 데이터 ==>  화사
큐 상태 :  [None, '솔라', '문별', '휘인', '선미']
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> E
추출된 데이터 ==>  솔라
큐 상태 :  [None, None, '문별', '휘인', '선미']
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> I
입력할 데이터 ==> 태연
큐 상태 :  [None, '문별', '휘인', '선미', '태연']
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> V
확인된 데이터 ==>  문별
큐 상태 :  [None, '문별', '휘인', '선미', '태연']
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나 선택 ==> X
프로그램 종료!

원형 큐

앞서 다룬 큐는 한 줄에 차례대로 데이터가 입력·출력되는 순차 큐(Sequential Queue)이다.
이보다 좀 더 효율적인 원으로 구성된 원형 큐(Circular Queue, 환형 큐)를 사용할 수 있다.
- 실제로 큐를 구현할 때는 순차 큐보다 원형 큐를 더 많이 사용한다.
원형 큐는 처음과 끝이 연결된 구조로, 순차 큐처럼 배열로 구현하되 큐의 끝에 다다르면 다시 처음으로 이어지도록 처리하면 된다.
크기가 10만 개인 순차 큐의 앞쪽은 일부 비어 있지만, rear 값이 '큐 크기-1'인 상태를 생각해보자.

데이터를 삽입하는 동작 자체는 문제가 없으나, 데이터를 1개 삽입하려고 1단계에서 무료 99997회 이동해야 한다.
- 이렇게 무리하게 일어나는 작업을 오버헤드(Overhead)라고 하며, 상당히 비효율적이다.
이 순차 큐를 구부려서 끝을 이은 원형 큐는, 앞쪽 일부만 제외하고 데이터가 꽉 찬 상태이더라도 처음과 끝이 이어졌으므로 rear를 다시 처음인 0으로 이동시킨 후, 그 자리에 데이터를 입력하면 간단히 끝난다.
- 순차 큐와 달리 오버헤드가 발생하지 않는다.

원형 큐의 원리

원형 큐 초기화

순차 큐처럼 배열을 사용하되, 순차 큐와 달리 0번 칸 앞쪽이 -1이 아니므로 초깃값을 둘 다 0으로 지정해서 초기화한다.

CircularQueue = [None, None, None, None, None]
front = rear = 0

원형 큐가 빈 경우와 꽉 찬 경우

원형 큐가 비었는지 여부는 순차 큐가 비었는지 여부와 같다.
- 둘 다 front와 rear가 동일하면 비어있다는 의미이다.

if (front값 == rear값) :
    큐가 비었음.

반대로 rear+1과 front가 같은 경우에 원형 큐가 꽉 찬 것으로 처리된다.

if ((rear값+1) % 5 == front값) :
    큐가 꽉 찼음.

순차 큐와 다른 원형 큐의 특징은 전체 크기에서 한 칸을 사용하지 못한다는 것이다.
- 모든 칸을 사용할 경우, front와 rear가 같게 되어 큐가 비어 있다는 의미로 해석될 수 있다.

원형 큐의 데이터 삽입과 추출

원형 큐에서 데이터를 삽입하는 방법은 순차 큐와 큰 차이가 없다.
하지만, 마지막 칸 다음은 다시 0이므로 rear의 다음 칸을 계산하려면 rear+1 값을 큐 크기로 나눈 나머지 값으로 처리한다.

if (큐가 꽉 찼음) :
    return
rear = (rear+1) % 큐크기
queue[rear] = item

원형 큐에서 데이터를 추출하는 방법도 순차 큐와 큰 차이가 없다.
하지만, 마지막 칸 다음은 다시 0이므로 front 다음 칸을 계산하려면 front+1 값을 큐 크기로 나눈 나머지 값으로 처리한다.

if (큐가 비었음) :
    return
front = (front+1) % 큐크기
데이터 = queue[front]
queue[front] = None

프로그램 구현

순차 큐와 비교하여 isQueueFull() 함수가 다르고, 기타 함수에서는 다음 칸을 계산할 때 (현재 위치+1)을 큐 크기로 나누는 것이 다르다.

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("프로그램 종료!")

큐의 크기를 입력하세요 ==> 5
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 화사
큐 상태 :  [None, '화사', None, None, None]
front :  0 , rear :  1
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 솔라
큐 상태 :  [None, '화사', '솔라', None, None]
front :  0 , rear :  2
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 문별
큐 상태 :  [None, '화사', '솔라', '문별', None]
front :  0 , rear :  3
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 휘인
큐 상태 :  [None, '화사', '솔라', '문별', '휘인']
front :  0 , rear :  4
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==>  화사
큐 상태 :  [None, None, '솔라', '문별', '휘인']
front :  1 , rear :  4
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 태연
큐 상태 :  ['태연', None, '솔라', '문별', '휘인']
front :  1 , rear :  0
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> V
확인된 데이터 ==>  솔라
큐 상태 :  ['태연', None, '솔라', '문별', '휘인']
front :  1 , rear :  0
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==>  솔라
큐 상태 :  ['태연', None, None, '문별', '휘인']
front :  2 , rear :  0
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> X
프로그램 종료!

728x90

저작자표시 비영리 변경금지

'Computer Science > 자료구조' 카테고리의 다른 글

[C] 이중 연결 리스트(Doubly Linked List) (0)	2022.07.12
[C] 원형 연결 리스트(Circular Linked List) (0)	2022.07.12
[C] 단순 연결 리스트(Singly Linked List) (0)	2022.07.12
[Python] 스택(Stack) (0)	2022.07.01
[Python] 이진 탐색(Binary Search) (0)	2022.06.29
[Python] 순차 탐색(Sequential Search) (0)	2022.06.29
[Python] 원형 연결 리스트(Circular Linked List) (0)	2022.06.22
[Python] 단순 연결 리스트(Singly Linked List) (0)	2022.06.22

Powered by Tistory, Designed by 👨🏻‍🚀adastra

티스토리툴바