본문 바로가기
알고리즘/자료구조_알고리즘

[자료구조] 07. 큐 (Queue) & 덱 (Dequeue)

by ㅣlㅣl 2022. 8. 29.

사담 공간

 

스택과 비슷하면서도 다른 자료구조인 큐에 대해 알아보자

 

키워드

 

#큐 #선입선출 #FIFO #덱 

 

1. 큐 개념

 

큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 구조(FIFO)로 되어있다.

 

 

큐의 핵심개념인 "선입선출(FIFO)"에 대해서 알아보자.

 

이전 포스팅에서 다룬 스택의 개념을 복습하며 비교하면 더 좋을 듯하다!
https://ll2ll.tistory.com/9
 

[자료구조] 06. 스택

사담 공간 드디어 고오급 자료구조에 입문하게 된다..!! 그래도 스택이랑 큐까지는 할만했던 것 같은데 트리부터가...허허 알고리즘 전까지는 최대한 개강 전에 끝내보자 ㅠㅠ 키워드 #스택 #후

ll2ll.tistory.com

 

 

FIFO (First In First Out), 선입선출

역시 해석 그대로 "제일 먼저 들어온 데이터가 제일 먼저 나간다" 라는 뜻이다. 

 

 

사람이 줄을 서서 기다리는 것으로 생각하면 보다 이해하기 쉬울 것이다!

 

[그림 1] 어제 갔던 야시장 줄..

 

 

좀 더 구조화시킨 그림으로 살펴보자.

[그림 2] 큐 개념 그림

 

 

그림2와 같이 스택의 삽입은 큐 뒤쪽(rear)에서, 삭제는 큐 앞(front)에서 이뤄진다!

 

 

 

2. 큐 ADT & 구현

큐 메서드 ADT

일반 메서드

  • void initialize() : 초기 큐 생성

 

주요 스택 메서드

  • void enqueue(e) : 큐 뒤에 원소 삽입
  • element dequeue() : 큐 앞에서 원소를 삭제해서 반환

 

보조 스택 메서드

  • element front() : 큐 앞에 있는 원소 반환
  • integer size() : 큐에 저장된 원소의 수를 반환
  • boolean isEmpty() : 큐가 비어있는지 여부를 반환
  • boolean isFull() : 큐가 가득 차있는지 여부를 반환

 

예외

  • emptyQueueException() : 비어 있는 큐에 대해 삭제 또는 front()를 수행 시도할 때
  • fullQueueException() : 만원 큐에 대해 삽입을 수행 시도할 때

 

큐 구현

배열에 기초한 경우

  • 크기 N의 배열을 원형으로 사용 -> 선형배열을 사용하면 비효율적임

f, r 인덱스가 계속 왼쪽 -> 오른쪽으로 이동하므로 선형구조보다 환형구조를 사용하는 것이 저장 공간을 늘릴 수 있는 방법이다.

 

[그림 3] 원형 큐

 

만약 삭제/삽입을 반복해서 f, r의 인덱스가 7을 넘어가더라도 다시 인덱스를 0으로 되돌려 계속 사용할 수 있다.

 

[그림 4] f, r이 회전한 상태

 

이를 구현할 배열로 나타내면 다음 그림과 같다.

 

 

[그림 5] 원형 큐를 배열 형태로 표현

 

 

 

  • 변수 f = front 원소의 인덱스, 변수 r = rear 원소의 인덱스

 

원형배열에서의 빈 큐 VS 만원 큐 차이

 

 

위에서 살펴본 원형배열로 구현할 경우 빈 큐와 만원 큐의 구별이 힘들어진다 (f, r이 돌아가면서 순서가 바뀔 수 있기 때문)

 

r이 증가하면서 데이터를 하나씩 채워나갈 때, 배열 큐는 다음과 같이 구성된다

 

[그림 6] 빈 큐와 만원 큐의 f, r 인덱스가 동일

 

[그림 7] f, r이 회전한 경우도 마찬가지

 

 

 

빈 큐와 만원 큐를 구별하기 위해서는 원소를 하나 비워두면 된다!

역시나 그림으로 살펴보자.

 

[그림 8] 빈 큐와 만원 큐의 f, r 인덱스 위치 다름
[그림 9] 마찬가지

 

빈 큐 : f, r이 같은 위치에 존재

만원 큐 :

1) 회전되어 있지 않은 경우 (f < r)

r - f = N - 1

 

2) 회전되어 있는 경우 (f > r)

r - f = -1

 

 

일반 메서드

  • void initialize() : 초기 큐 생성
Alg initialize()
    // input : queue Q, size N, front f, rear r
    // output : an empty queue Q

    f = 0
    r = 0
    return

 

 

주요 스택 메서드

  • void enqueue(e) : 큐 뒤에 원소 삽입 -> rear 이동
Alg enqueue(e)
    // input queue Q, size N, front f, rear r, element e
    // output none
    if (isFull())
        fullQueueException()
    r = (r+1) % N
    Q[r] = e
    return

 

  • element dequeue() : 큐 앞에서 원소를 삭제해서 반환
Alg dequeue()
    // input queue Q, size N, front f, rear r
    // output element

    if (isEmpty())
        emptyQueueException()
    e = Q[f]
    f = (f+1) % N
    return e

 

 

보조 스택 메서드

  • element front() : 큐 앞에 있는 원소 반환
Alg front()
    if (isEmpty())
        emptyQueueException()
    return Q[f]

 

  • integer size() : 큐에 저장된 원소의 수를 반환
Alg size()
    return (N - f + r + 1) % N

 

  • boolean isEmpty() : 큐가 비어있는지 여부를 반환
  • boolean isFull() : 큐가 가득 차있는지 여부를 반환
Alg isEmpty()
    // input : queue Q, front f, rear r
    if f = r
        return true
    else
        return false

Alg isFull()
    // input : queue Q, size N, front f, rear r
    if (r+1) % N = f
        return true
    else
        return false

 

 

<파이썬 구현>

더보기

 

# queue_arr.py

from asyncio.windows_events import NULL

class queue:
    def __init__(self, N):
        self.arr = [0] * N
        self.N = N
        self.f = 0
        self.r = 0
    
    def isEmpty(self):
        if self.f == self.r:
            return True
        else:
            return False
    
    def isFull(self):
        if (self.r + 1) % self.N == self.f:
            return True
        else:
            return False
    
    def enqueue(self, e):
        if (self.isFull()):
            print("fullQueueException")
            print(e, "not enqueued")
        else:
            self.r = (self.r+1) % self.N
            self.arr[self.r] = e
        return
    
    def dequeue(self):
        if (self.isEmpty()):
            print("emptyQueueException")
            return NULL
        e = self.arr[(self.f+1) % self.N]
        self.f = (self.f+1) % self.N
        return e
    
    def size(self):
        return (self.N - self.f + self.r) % self.N

    def front(self):
        if (self.isEmpty()):
            print("emptyQueueException")
            return NULL
        else:
            return self.arr[self.f+1]​

 

# queue.py

from queue_arr import queue

Q = queue(8)

print('isEmpty?:', Q.isEmpty())
Q.enqueue('a')
Q.enqueue('b')
Q.enqueue('c')
print('f :', Q.front(), 'size :', Q.size())
Q.dequeue()
print('f :', Q.front(), 'size :', Q.size())
Q.enqueue('d')
Q.enqueue('e')
Q.enqueue('f')
Q.enqueue('g')
Q.enqueue('h')
Q.enqueue('i')
print('isFull?:', Q.isFull())
print('f :', Q.front(), 'size :', Q.size())

Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()

print('isEmpty?:', Q.isEmpty())

 

<실행 과정>

[그림 10] 실행 과정

 

<실행 결과>

 

[그림 11] 실행 결과

 

 

 

 

 

연결리스트에 기초한 경우

삽입과 삭제가 특정 위치에서만 수행되므로 단일연결리스트를 사용해 큐를 구현할 수 있다.

f, r이 시작 시 첫 노드를 가리키게 하고 노드가 추가될 때마다 r, 삭제될 때마다 f가 가리키는 노드를 변경한다.

 

[그림 12] 연결리스트

 

나머지 개념은 위의 <배열에 기초한 경우>와 동일하다.

 

 

 

 

일반 메서드

  • void initialize() : 초기 큐 생성
Alg initialize()
    // input : front f, rear r
    // output : empty queue with front f, rear r
    f, r = NULL
    return

 

 

주요 스택 메서드

  • void enqueue(e) : 큐 뒤에 원소 삽입
Alg enqueue(e)
    // input front f, rear r, element e
    // output none
    p = getnode()
    p.elem = e
    p.next = NULL

    if (isEmpty())
        f, r = p
    else
        r.next = p
        r = p
    return

 

  • element dequeue() : 큐 앞에서 원소를 삭제해서 반환
Alg dequeue()
    // input front f, rear r
    // output element
    if (isEmpty())
        emptyQueueException()
    e = f.elem
    p = f
    f = f.next
    if (f = NULL)
        r = NULL
    putnode(p)
    return e

 

 

보조 스택 메서드

  • element front() : 큐 앞에 있는 원소 반환
Alg front()
    // input : front f
    // output : element
    if(isEmpty())
    	emptyQueueException()
    return f.next.element
  • integer size() : 큐에 저장된 원소의 수를 반환
Alg size()
    // input : queue Q, front f, rear r
    // output : integer
    p = f
    cnt = 0
    while p != r:
        cnt += 1
        p = p.next
    return cnt + 1

 

  • boolean isEmpty() : 큐가 비어있는지 여부를 반환
Alg isEmpty()
    // input front f, rear r
    // output boolean
    if f = NULL
        return true
    else
        return false
  • boolean isFull() : 큐가 가득 차있는지 여부를 반환

-> 동적할당이므로 isFull() 메서드는 필요하지 않다!

 

 

<파이썬 구현>

 

더보기

 

 

# queue_linked_list.py

from asyncio.windows_events import NULL

class node():
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class queue:
    def __init__(self):
        self.f = NULL
        self.r = NULL
    
    def isEmpty(self):
        if self.f == NULL:
            return True
        else:
            return False
    
    def enqueue(self, e):
        p = node(e, NULL)
        
        # 큐에 첫 노드 삽입
        if (self.isEmpty()):
            self.f = p
            self.r = p
        else:
            self.r.next = p
            self.r = p
        return
    
    def dequeue(self):
        if (self.isEmpty()):
            print("emptyQueueException")
            return NULL
            
        e = self.f.data
        self.f = self.f.next
        # 큐에 노드 한개도 안 남는 경우
        if self.f == NULL:
            self.r = NULL
        return e

    def front(self):
        if self.isEmpty() == True:
            print("emptyQueueException")
            return NULL

        return self.f.next.element

    def size(self):
        p = self.f
        cnt = 0
        while p != self.r:
            cnt += 1
            p = p.next
        return cnt + 1

 

# queue.py

from queue_arr import queue

Q = queue(8)

print('isEmpty?:', Q.isEmpty())
Q.enqueue('a')
Q.enqueue('b')
Q.enqueue('c')
print('f :', Q.front(), 'size :', Q.size())
Q.dequeue()
print('f :', Q.front(), 'size :', Q.size())
Q.enqueue('d')
Q.enqueue('e')
Q.enqueue('f')
Q.enqueue('g')
Q.enqueue('h')
print('f :', Q.front(), 'size :', Q.size())

Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()

print('isEmpty?:', Q.isEmpty())

 

<실행 과정>

[그림 13] 실행 과정

 

 

<실행 결과> 

[그림 14] 실행 결과

 

 

 

 

성능

큐의 원소 개수가 n이라 할 때

  • 기억장소 사용 : O(n)
  • 각 작업의 실행시간 : O(1)

 

 

 

3. 덱 개념

 

덱 (Dequeue) 은 양쪽 끝에서 삽입 / 삭제가 모두 가능한 자료구조의 형태이다

 

스택과 큐는 한쪽 끝에서만 삽입 / 삭제가 가능한 것과 대조적이다.

큐와 마찬가지로 덱의 맨 앞과 맨 끝을 가리키는 front / rear가 존재하고 양쪽 모두에서 삽입과 삭제가 이루어진다.

 

[그림 15] 덱 개념 그림

 

4. 덱 ADT & 구현

일반 메서드

  • void initialize() : 덱 생성 및 초기화

 

주요 메서드

  • void push(e) : front 위치에 원소를 삽입
  • element pop() : front 위치의 원소를 삭제하여 반환
  • void inject(e) : rear 위치에 원소를 삽입
  • element eject() : rear 위치의 원소를 삭제하여 반환

 

보조 메서드

  • element front() : front 위치의 원소를 반환
  • element rear() : rear 위치의 원소를 반환
  • integer size() : 덱에 저장된 원소의 수를 반환
  • boolean isEmpty() : 덱이 비어있는지 여부를 반환

 

예외

  • emptyDequeException() : 비어있는 덱으로부터 삭제를 시도할 경우
  • fullDequeException() : 만원인 덱으로부터 삽입을 시도할 경우

 

 

덱 구현

배열에 기초한 덱

  • 크기 N의 배열을 원형으로 사용 -> 선형배열을 사용하면 비효율적임

f, r 인덱스가 계속 왼쪽 -> 오른쪽으로 이동하므로 선형구조보다 환형구조를 사용하는 것이 저장 공간을 늘릴 수 있는 방법이다.

 

큐의 경우와 마찬가지로 만원 덱과 빈 덱을 구별하기 위해 배열 한 칸을 비워두고 채운다.

 

 

<파이썬 구현>

 

더보기

 

# dequeue_arr.py

from asyncio.windows_events import NULL


class dequeue:
    def __init__(self, N):
        self.arr = [0] * N
        self.N = N
        self.f = 0
        self.r = 0
    
    # front 위치의 원소 추가
    def push(self, e):
        if (self.isFull()):
            print("fullDequeueException")
            print(e, "not pushed")
        else:
            self.arr[self.f] = e
            self.f = (self.f - 1) % self.N
            
        return
    
    # front 위치의 원소 삭제 후 반환
    def pop(self):
        if (self.isEmpty()):
            print("emptyDequeueException")
            return NULL
        e = self.arr[(self.f+1) % self.N]
        self.f = (self.f+1) % self.N
        return e

    # 배열 맨 뒤에 원소 추가
    def inject(self, e):
        if (self.isFull()):
            print("fullDequeueException")
            print(e, "not injected")
        else:
            self.r = (self.r+1) % self.N
            self.arr[self.r] = e
        return
    
    # 배열 맨 뒤의 원소 삭제 및 반환
    def eject(self):
        if (self.isEmpty()):
            print("emptyDequeueException")
            return NULL
        e = self.arr[(self.r-1) % self.N]
        self.r = (self.r-1) % self.N
        return e
    
    def front(self):
        if (self.isEmpty()):
            print("emptyDequeueException")
            return NULL
        else:
            return self.arr[self.f+1]

    def rear(self):
        if (self.isEmpty()):
            print("emptyDequeueException")
            return NULL
        else:
            return self.arr[self.r]

    def size(self):
        return (self.N - self.f + self.r) % self.N

    def isEmpty(self):
        if self.f == self.r:
            return True
        else:
            return False
    
    def isFull(self):
        if (self.r + 1) % self.N == self.f:
            return True
        else:
            return False

 

# dequeue.py

from dequeue_arr import dequeue

Deq = dequeue(8)

Deq.inject('a')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.eject()
Deq.eject()

Deq.inject('a')
Deq.inject('b')
Deq.inject('c')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.pop()
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.pop()
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.push('b')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.eject()
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.push('c')
Deq.push('d')
Deq.push('e')
Deq.push('f')
Deq.push('g')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.inject('h')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.inject('i')

 

<실행 과정>

 

[그림 16] 실행 과정 - 1
[그림 17] 실행 과정 - 2
[그림 18] 실행 과정 - 3

 

<실행 결과>

 

[그림 19] 실행 결과

 

 

 

 

연결리스트에 기초한 덱

큐와는 다르게 앞/뒤 모두에서 삭제해야 하므로 이중연결리스트를 사용해서 덱을 구현할 수 있다.

 

 

[그림 20] 연결리스트 덱 개념

 

<파이썬 구현>

더보기

 

# dequeue_linked_list.py

from asyncio.windows_events import NULL

class node():
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next

class dequeue:
    def __init__(self):
        self.f = NULL
        self.r = NULL
    
    def isEmpty(self):
        if self.f == NULL:
            return True
        else:
            return False
    

    # front 위치의 원소 추가
    def push(self, e):
        p = node(e, NULL, NULL)

        # 큐에 첫 노드 삽입
        if (self.isEmpty()):
            self.f = p
            self.r = p
        else:
            p.next = self.f
            p.prev = NULL
            (self.f).prev = p
            self.f = p
        return
    
    # front 위치의 원소 삭제 후 반환
    def pop(self):
        if (self.isEmpty()):
            print("emptyQueueException")
            return NULL
        
        p = self.f
        e = p.data
        self.f = p.next

        # 큐에 노드 한개도 안 남는 경우
        if self.f == NULL:
            self.f = NULL
            self.r = NULL
        return e

    # rear 위치의 원소 추가
    def inject(self, e):
        p = node(e, NULL, NULL)

        # 큐에 첫 노드 삽입
        if (self.isEmpty()):
            self.f = p
            self.r = p
        else:
            self.r.next = p
            p.prev = self.r
            self.r = p
        return
    
    # rear 위치의 원소 삭제 후 반환
    def eject(self):
        if (self.isEmpty()):
            print("emptyDequeueException")
            return NULL
        
        p = self.r
        e = p.data
        self.r = p.prev

        # 큐에 노드 한개도 안 남는 경우
        if self.r == NULL:
            self.f = NULL
            self.r = NULL
        return e
    
    def front(self):
        if self.isEmpty() == True:
            print("emptyQueueException")
            return NULL

        return self.f.data
    
    def rear(self):
        return self.r.data

    def size(self):
        p = self.f
        cnt = 0
        while p != self.r:
            cnt += 1
            p = p.next
        return cnt + 1

 

# dequeue.py

from dequeue_linked_list import dequeue

Deq = dequeue()

Deq.inject('a')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.eject()
Deq.eject()

Deq.inject('a')
Deq.inject('b')
Deq.inject('c')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.pop()
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.pop()
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
print('####')
Deq.push('b')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())
Deq.eject()
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.push('c')
Deq.push('d')
Deq.push('e')
Deq.push('f')
Deq.push('g')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

Deq.inject('h')
print('front :', Deq.front(), 'rear : ', Deq.rear(), 'size :', Deq.size())

 

 

<실행 과정>

[그림 21] 실행 과정 - 1
[그림 22] 실행 과정 - 2
[그림 23] 실행 과정 - 3

 

<실행 결과>

 

[그림 24] 실행 결과

 

 

 

 

 

'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글

[자료구조] 09. 그래프 - 개념과 표현방식  (0) 2023.01.03
[자료구조] 08. 트리  (0) 2022.08.29
[자료구조] 06. 스택 (Stack)  (0) 2022.08.25
[자료구조] 05. 집합  (0) 2022.08.25
[자료구조] 04(2). 연결리스트 확장 및 응용  (0) 2022.08.20

관련글

티스토리툴바