-
자료구조 - 7 | 큐컴퓨터 공학/자료구조 2023. 1. 25. 21:15
큐
이전 포스트에서 알아본 자료구조인 스택은 가장 나중에 삽입한 원소를 가장 먼저 삭제하는 후입 선출 구조(LIFO; Last-In-First-Out)를 가졌다. 반면 이번에 알아볼 자료구조인 큐는 가장 먼저 삽입한 원소를 가장 먼저 삭제하는 선입 선출 구조(FIFO; First-In-First-Out)를 가진다.
따라서 큐 역시 스택과 비슷하게 삽입과 삭제의 위치가 제한되어 있는 리스트의 형식이다. 다만 비교적 구현이 간단했던 스택에 비해, 큐의 경우 삽입하는 부분과 삭제하는 부분의 위치가 서로 달라 구현에 약간의 복잡함이 있을 수 있다.
큐의 연산
큐도 스택처럼 삽입과 삭제 연산을 가진다.
스택에서는 push와 pop이라고 불렀지만, 큐에서는 삽입을 enQueue, 삭제를 deQueue라고 부른다.
순차 자료구조를 이용한 큐의 구현
큐를 구현하기 위한 가장 간단한 방법은 순차 자료구조인 1차원 배열을 이용하는 것이다.
그리고 front와 rear변수를 이용해 각각 저장된 첫 번째 원소 직전의 인덱스와 마지막 원소의 인덱스를 저장한다.
최초 순차 큐 생성
최초로 크기가 n인 큐를 생성하기 위해서는 크기가 n인 1차원 배열을 생성해야 한다.
그리고 방금 막 생성한 큐에는 어떠한 데이터도 존재하지 않기 때문에, 큐가 비어있다는 것을 표현하기 위해 front와 rear변수를 -1로 초기화한다.
크기가 8인 1차원 배열을 생성하고, front와 rear변수를 -1로 초기화하여 순차 큐를 생성 front변수는 가장 처음의 원소의 인덱스를 나타내는 것이 아니다. 첫 원소 직전의 인덱스를 나타내는 것이므로, 최초 큐를 생성하였을 때 첫 번째 인덱스인 0보다 하나 작은 -1로 초기화되는 것이다.
rear변수는 가장 마지막 원소의 인덱스를 나타낸다. 하지만 처음 큐를 생성한 경우에는 어떠한 값도 저장되어 있지 않기 때문에 rear변수를 -1로 초기화한다.
삽입 연산
순차 큐의 삽입 연산은 rear의 값을 이용해 동작한다. 큐의 선입 선출 구조를 1차원 배열로 구현하기 위해서는 새로운 데이터를 기존의 데이터 가장 마지막 위치에 삽입시켜야 하기 때문이다.
따라서 삽입 연산은 먼저 기존의 rear값을 하나 증가시켜 삽입할 자리를 준비한 다음, 증가한 rear값에 해당하는 Q[rear]에 새로운 데이터를 저장하는 방식으로 진행된다.
큐에 저장된 데이터 중 가장 마지막 데이터의 인덱스를 가리키고 있는 rear 
rear의 값을 하나 증가시켜 삽입할 자리를 준비한 다음, 준비된 자리인 Q[rear]에 새 데이터를 저장 삭제 연산
순차 큐의 삭제 연산은 front의 값을 이용해 동작한다. 큐의 동작 특성상 가장 먼저 삽입한 값을 삭제해야 하는데, 순차 큐에서 가장 먼저 삽입한 값은 front변수를 이용해 알 수 있기 때문이다.
따라서 삭제 연산은 기존의 front값을 하나 증가시켜 삭제할 자리를 준비한다. 기존 front값은 가장 첫 원소 직전을 가리키는데, 여기서 값을 하나 증가시켰다는 것은 이제 front값이 가장 첫 원소를 가리킨다는 뜻이다. 이러한 상태가 되었다면 Q[front]의 값을 삭제하여 반환할 수 있다.
초기 상태인 -1값을 그대로 가지고 있는 front변수 
-1이었던 front값을 하나 증가시켜 0으로 만들고, Q[front]의 값을 삭제 및 반환 
같은 방식으로 두 번째로 저장된 값도 한번 더 삭제 큐의 상태 표현
지금까지 1차원 배열을 이용하여 순차 큐를 생성하고, 삽입, 삭제 연산을 진행하는 과정을 살펴보았다.
처음 순차 큐를 생성할 때에는 크기에 맞는 1차원 배열을 생성하고, front와 rear변수를 -1로 초기화하였다.
삽입 연산을 수행할 때에는 rear의 값을 하나씩 늘렸고, 삭제 연산을 수행할 때에는 front의 값을 하나씩 늘렸다.
즉, front와 rear의 값을 통해 현재 큐의 상태를 표현할 수 있다. 이를 표로 정리하면 다음과 같다.
초기 상태 공백 상태 포화 상태 front = rear = -1 front = rear rear = n - 1 (n은 배열의 크기) 삭제를 계속 진행하다가 front의 값이 rear의 값과 같아지게 되면, 더 이상 삭제할 원소가 큐에 남아있지 않은 공백 상태인 것을 알 수 있다. 반대로 삽입을 계속 진행하다가 rear의 값이 1차원 배열의 마지막 인덱스인 n - 1의 값과 같아지게 되면, 더 이상 새로운 값을 큐에 삽입할 수 없는 포화 상태가 된다.
이를 이용해 위의 삽입과 삭제 연산에서 front와 rear의 값을 이용해 미리 삽입과 삭제가 가능한 상태인지 파악하는 것이 중요하다.
삽입의 경우 rear = n - 1인지를 확인하여, 만약 포화 상태라면 더 이상 삽입할 수 없으므로 삽입 연산을 중단해야 한다.
삭제의 경우 front = rear인지를 확인하여, 이미 비어있는 큐라면 삭제할 원소가 없으므로 삭제 연산을 중단해야 한다.
순차 큐의 잘못된 포화상태 인식
순차 큐에서 삽입과 삭제를 반복하는 경우 실제 1차원 배열이 포화상태가 아님에도 포화상태로 인식되는 문제가 생길 수 있다. 아래와 같은 경우를 생각해 보자.
Q[7]에만 데이터가 저장된 상태 
삽입과 삭제를 계속 반복하여 front와 rear가 더 이상 증가할 수 없는 순간에 도달함 실제로 위의 1차원 배열에는 아무런 값이 저장되어 있지 않다. 하지만 큐의 상태를 결정하는 front와 rear가 모두 더 이상 증가할 수 없는 순간까지 도달하여, 프로그램이 해당 큐에는 더 이상 값을 저장할 수 없다고 인식할 것이다.
결국 큐를 위해 생성된 1차원 배열만큼의 메모리는 더 이상 어디에도 사용되지 못한 채로 낭비될 것이고, 생성되었던 큐는 더 이상 삽입과 삭제를 진행할 수 없는 망가진 상태가 되어버릴 것이다. 자료를 저장하기 위한 큐가 건전지 마냥 다 써버리면 더 이상 사용할 수 없는 상태가 된다는 것은 잘못된 일이다.
따라서 이러한 순차 큐의 문제를 해결하기 위해 두 가지의 방법을 사용할 수 있다.
가장 간단한 해결방법은 삭제 연산을 진행할 때마다 front값을 증가시키는 대신, 저장된 원소들을 모두 한 칸씩 앞으로 이동시키는 방법이다. 하지만 이는 삽입과 삭제가 비효율적인 순차 자료구조의 문제점을 그대로 가져오는 셈이 된다. 그렇기 때문에 큐를 효율적으로 사용할 수 없게 된다.
이러한 이유로 1차원 배열을 사용하면서 원소의 이동 없이 잘못된 포화상태를 해결할 수 있는 방법인 원형 큐에 대해 알아보려고 한다.
원형 큐
원형 큐는 1차원 배열을 사용하지만, 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하고 사용하는 방식을 말한다. 순차 큐의 잘못된 포화상태 인식은 front와 rear가 배열의 끝까지 이동하여 더 이상 이동할 곳이 없어서 발생하는 일이다. 하지만 배열의 처음과 끝을 논리적으로 연결하여 원형 상태로 만든다면, 기존의 끝까지 이동한 front와 rear도 무한히 돌면서 이동할 수 있을 것이다.
원형 큐의 구조
원형 큐는 기존의 1차원 배열을 사용하는 순차 큐에서 처음과 끝을 논리적으로 연결하기만 한 방식이므로, 기존의 순차 큐와 작동방식이 크게 다르지 않다. 단지 처음과 끝을 논리적으로 연결하는 과정만 추가해 주면 된다.
뭔가 처음과 끝을 연결한다는 개념이 어렵고 복잡하게 느껴질 수 있지만, 의외로 굉장히 간단하게 구현할 수 있다.
바로 나머지 연산자인 mod를 이용하는 것이다. 대부분의 프로그래밍 언어에서 %로 표현되는 바로 그 연산자이다.
크기가 8인 1차원 배열을 이용해서 순차 큐를 생성했다고 가정하자. 이 경우 가장 마지막 인덱스는 7일 것이다. 따라서 rear가 7에 도달한 경우 더 이상 값을 삽입할 수 없다. Q[8]은 1차원 배열의 메모리 범위를 벗어나기 때문이다.
하지만 이때 8을 0으로, 9를 1로, 10을 2로 바꿔준다면 어떨까? 그렇다면 마지막 인덱스인 7의 다음이 8이 아니라, 가장 처음인 0으로 다시 돌아오게 될 것이다. 즉, 논리적으로 처음과 끝이 연결된 것이다.
이를 위해 나머지 연산을 이용한다. 8 mod 8은 0이고, 9 mod 8은 1이고, 10 mod 8은 2이다. 대충 감이 오지 않는가?
큐의 크기를 n이라고 했을 때, 기존의 인덱스 값에 mod n연산을 하여 간단하게 처음과 끝을 연결할 수 있다.
원형 큐의 삽입, 삭제 연산
위의 개념을 이용해 순차 큐와 원형 큐의 삽입과 삭제 연산 위치를 비교해 보면 다음과 같다.
종류 삽입 위치 삭제 위치 순차 큐 rear = rear + 1 front = front + 1 원형 큐 rear = (rear + 1) mod n front = (front + 1) mod n 기존의 삽입과 삭제 연산인, rear 또는 front를 하나 증가시킨 다음 해당 자리에 값을 삽입하거나 삭제하는 방식은 크게 다르지 않다. 다만 원형 큐의 경우에는 증가 연산 이후에 나머지 연산(mod)을 추가로 하여, 인덱스가 최대 값을 넘어가는 경우 다시 처음으로 돌아오게끔 조정해 준다.
원형 큐의 상태 표현
원형 큐가 기존의 순차 큐와 다른 점이 하나 더 있는데, 바로 front와 rear의 초기 상태가 -1이 아니라 0이라는 점이다.
이를 고려해서 원형 큐에서의 상태 표현을 알아보면 다음과 같다.
초기 상태 공백 상태 포화 상태 front = rear = 0 front = rear front = (rear + 1) mod n 공백 상태는 삭제 연산이 계속 진행되어 front가 rear지점까지 도달한 상태를 말하기 때문에, 원형 큐에서나 순차 큐에서나 동일하게 front = rear를 통해 확인할 수 있다.
반면 포화 상태는 좀 다르다. 기존의 순차 큐에서는 rear가 마지막 인덱스까지 도달했는지를 통해 확인했는데, 원형 큐에서는 무한히 돌기 때문에 사실상 끝이 존재하지 않는다. 따라서 rear값이 계속 이동하다가 한 바퀴를 돌아서 front까지 도달했는지를 확인하는 방식으로 포화 상태를 확인해야 한다.
문제는 한 바퀴를 돌아 rear가 front까지 도달한 경우 포화 상태로 인식되어야 하지만, front = rear이므로 공백 상태로 잘못 인식될 수 있다. 따라서 원형 큐에서는 공백 상태와 포화 상태를 서로 구분하기 위해 front에 해당하는 자리는 항상 비워두는 방식을 사용한다.
즉, rear가 front까지 완전히 이동하기 전에, front의 앞에 위치만 하면 포화 상태로 생각하자는 것이다. 이렇게 하면 n의 크기를 가지는 1차원 배열을 사용했지만, 실질적인 데이터는 n - 1개밖에 저장하지 못할 것이다. 하지만 비어있는 칸을 이용해 공백 상태와 포화 상태를 구분할 수 있게 된다.
연결 자료구조를 이용한 큐의 구현
이번에는 순차 자료구조가 아닌 연결 자료구조를 이용하여 큐를 구현해 보도록 한다.
순차 자료구조인 1차원 배열을 이용해 순차 큐를 생성했을 때에는 빠르고 간단하게 구현하기에는 좋았지만, 잘못된 포화상태 인식 등과 같은 문제가 있었다. 따라서 원형 큐라는 다소 독특한 방식을 사용해야 했고, 이를 사용한다 하더라도 순차 자료구조 특성상 미리 큐의 크기를 제한해야 한다는 점은 변하지 않는다.
하지만 연결 자료구조를 이용한다면 메모리가 허용하는 한 무한하게 자료를 저장할 수 있으며, 동시에 포화상태가 존재하지도 않는 것이니 잘못된 포화상태 인식과 같은 문제가 일어나지도 않는다는 장점이 있다.
연결 큐의 구조
연결 자료구조의 가장 기본적인 형태인 단순 연결 리스트를 이용한 연결 큐의 경우 연결 리스트의 각 노드가 큐의 원소가 된다. 각 노드는 메모리 상에 서로 물리적으로 연결되어 있지 않아도 되고, 단순히 링크 필드로 인해 논리적으로만 서로 순서를 가지고 연결된 상태이다.
단순 연결 리스트를 이용한 큐의 구조 여기까지만 보면 이전에 살펴본 단순 연결 리스트와 전혀 다를 바가 없다. 하지만 연결 큐의 경우 앞서 설명한 순차 큐와 동일하게 front와 rear라는 변수를 가진다. 순차 큐에서는 해당 변수들이 배열의 인덱스를 나타냈지만, 이번 연결 큐에서는 해당 변수들이 마치 각 노드의 링크 필드처럼 노드 자체를 가리킨다. C언어를 기준으로 하자면 포인터 변수와 같은 것이다.
최초로 연결 큐를 생성할 때 front와 rear변수는 각각 null로 초기화된다. 또한 아무런 노드가 없는 경우에도 front와 rear가 null이므로, 초기 상태와 공백 상태 모두 front = rear = null로 표현할 수 있다.
초기 상태 공백 상태 포화 상태 front = rear = null front = rear = null 무한히 저장할 수 있음 추가로 순차 큐에서는 front가 가장 앞의 원소 직전을 나타내었다. 그래서 다소 헷갈릴 수 있었는데, 연결 큐에서 사용하는 front는 가장 첫 번째 노드 그 자체를 의미한다.
또한 단순 연결 리스트를 생성할 때, 그 리스트 자체를 가리키는 리스트 포인터는 항상 리스트의 가장 첫 노드를 가리키고 있는데, 이를 front처럼 사용할 수 있다. 따라서 굳이 front라는 변수를 사용할 필요는 없다고 보지만, 순차 큐와 비슷하게 설명함과 동시에 좀 더 알아보기 쉽도록 하기 위해 이번 포스트에서는 front 변수를 정석적으로 사용하도록 한다.
삽입 연산
연결 큐의 삽입 연산은 현재 큐가 공백 상태인지 아닌지에 따라 약간 달라진다. 하지만 기본적인 동작 원리는 항상 마지막에 노드를 삽입한다는 것을 제외한다면, 단순 연결 리스트의 삽입 연산과 같다.
아래는 연결 큐의 삽입 연산의 과정을 나타낸 것이다.
- 새로운 노드를 생성한다.
- 새로운 노드의 데이터 필드에 저장할 값을 저장한다.
- 새로운 노드의 링크 필드에 NULL을 저장한다.
- 현재 큐가 공백 상태인지를 확인한다.
- 공백 상태인 경우
- NULL을 가리키던 front와 rear가 새로 생성한 노드를 가리키도록 한다.
- 공백 상태가 아닌 경우
- rear가 가리키던 노드의 링크 필드가 새로 생성한 노드를 가리키도록 한다.
- rear가 새로 생성한 노드를 가리키도록 한다.
공백 상태일 때 새로운 노드를 삽입 
공백 상태가 아닐 때 새로운 노드를 삽입 삭제 연산
연결 큐의 삭제 연산 역시 기본적인 원리는 항상 가장 첫 노드만을 삭제한다는 것을 제외한다면, 단순 연결 리스트의 삭제 연산과 거의 동일하다.
아래는 연결 큐의 삭제 연산의 과정을 나타낸 것이다.
- 현재 큐가 공백 상태라면 이후의 연산을 진행하지 않고 바로 삭제 연산을 중지한다.
- 가장 첫 노드인 front가 가리키는 노드의 메모리 주소를 임시로 저장한다.
- front가 가리키는 노드를 기존 front가 가리키는 노드의 링크 필드가 가리키는 노드로 변경한다. (front가 삭제할 노드 다음 노드를 가리키도록 함)
- 임시로 저장해 둔 노드를 삭제 및 반환하여 메모리 공간을 비움
- 만약 이번 삭제로 인해 공백 큐가 되는 경우, rear를 NULL로 설정
연결 큐의 삭제 연산
데크(Deque; Double-ended Queue)
마지막으로 큐를 약간 변형한 형태인 데크에 대해 알아보고자 한다.
데크는 큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조로, 큐의 양쪽 끝에서 삽입과 삭제 연산이 가능한 자료구조이다.
양쪽 끝에서 삽입과 삭제 연산이 모두 가능하다는 특징 때문에 데크 하나만 잘 만들어 두면, 이를 스택으로도 사용할 수 있고, 큐로도 사용할 수 있다는 장점이 있다.
데크의 구조 이러한 데크는 지금까지 스택과 큐를 구현했던 것과 동일하게 순차 자료구조로도 구현할 수 있고, 연결 자료구조로도 구현할 수 있다. 하지만 한쪽에서만 삽입과 삭제가 일어나던 스택과 큐와는 달리 양쪽 방향에서 삽입과 삭제 연산이 수행되기 때문에, 전체적인 자료의 크기 변화와 저장된 원소의 순서 변화가 많이 일어난다.
따라서 순차 자료구조를 이용하는 것은 굉장히 비효율적이라고 볼 수 있고, 대신 양방향으로 연산이 가능한 이중 연결 리스트를 주로 사용하여 데크를 구현한다.
이중 연결 리스트를 사용하여 구현한 데크 데크 역시 연산이 직접적으로 일어날 가장 앞 노드와 가장 뒷 노드를 front와 rear변수를 이용해 관리한다.
직접적으로 삽입과 삭제 연산을 구현하는 것은 앞서 연결 큐에서 충분히 설명했기 때문에 이번 데크에서는 생략하도록 하겠다. 기본적인 연산 개념은 완전히 동일하기 때문이다.
- 새로운 노드를 생성한다.