자료구조 3강. 큐(Queue)
[자료구조 강좌]
선입선출!
큐(Queue)
큐(Queue)란 자료구조는 앞서 배웠던 스택(Stack) 자료구조와는 달리 선입선출(First In, First Out: FIFO)의 구조를 지니고 있습니다. 한마디로 먼저 들어온 데이터는 먼저 나간다는 소리입니다. 예를 들면, 점심시간에 학생들이 점심을 먹으러 일렬로 줄을 서있다고 가정합시다. 줄을 선 순서대로 차례차례 급식을 받고 빠져나가죠? 이러한 구조를 지닌 자료구조가 바로 큐(Queue)라고 말할 수 있습니다. 오늘은 순환 큐(Circular Queue)와 링크드 큐(Linked Queue)에 대해 알아보기 전에, 기본적으로 짚고 넘어가야 할 사항들이 있습니다.
우리가 리스트(List)에서는 가장 앞에있는 노드를 헤드(Head), 가장 뒤에 있는 노드를 테일(Tail)이라고 했었죠? 이번에 배우게 될 큐(Queue) 에서는 가장 앞에있는 요소를 전단(Front), 가장 뒤에 있는 요소를 후단(Rear)이라고 합니다. 저 위의 그림에선 the가 전단, mat이 후단이라고 말할 수 있습니다. 그리고 큐는 선입선출의 구조이기 때문에, 먼저 들어온게 먼저 나가는 형태를 띈다고 했었죠? 즉, 제거(Dequeue)는 전단에서 이루어지며, 삽입(Enqueue)은 후단에서 이루어집니다. 이해 되시죠?
1. 순환 큐(Circular Queue) 큐가 직선이 아닌 원형으로!
순환 큐(Circular Queue)에 대해 설명하기 전에, 직선 구조를 띈 큐(Queue)의 문제점을 보도록 하겠습니다.
위는 직선 구조를 띈 큐(Queue)의 제거(Dequeue) 연산입니다. 처음에는, 큐에 6개의 요소가 있었으나 전단인 A가 빠져나가면서 뒤에 있던 B, C, D, E, F 요소 모두 앞으로 옮겨가는 상황이 벌어졌습니다. 전단에 있는 요소가 제거될때마다 뒤에 있는 요소가 앞으로 따라와야 한다는 소리입니다. 그러면 1000개의 요소가 있다고 가정했을때, 전단에 있는 요소가 제거되면 999번의 연산을 추가적으로 거치게 됩니다. 즉, 큐의 크기가 커질수록 성능의 저하는 심각한 상황입니다. 이런 문제를 해결하기 위한 방안으로, 순환 큐가 등장했습니다.
순환 큐에서는 시작과 끝이 이어져 있습니다. 마치 더블 링크드 리스트처럼 말입니다. 어떻게 되어있는지 한번 볼까요?
위에 있는 순환 큐를 살펴보시면, 전단이 3, 후단이 10인것을 알 수 있습니다. 참고로 후단이 큐가 꽉차게 되었을때, 전단과 후단이 같아진다면 전단이 후단이 같아지면 큐가 비어있는지, 꽉차있는지 알수가 없습니다. 실제로, 후단은 실제 후단의 다음에 위치하며, 전단과 후단을 구분하기 위해 더미(Dummy) 공간을 만들어 만들어질 배열의 크기는 실제 배열의 크기에 1을 더한 값을 갖습니다. 이러면, 전단과 후단이 같다면 비어있는(Empty) 상태, 후단의 다음 노드가 전단이라면 꽉 찬(Full) 상태라고 말할 수 있습니다. 이제 직접 구현을 해보도록 합시다. 먼저 순환 큐의 노드를 구조체로 표현해보도록 합시다.
typedef struct Node
{
int data; // 데이터 필드
} Node;
위의 Node 구조체를 보시면 멤버가 data 하나 뿐입니다. Node 구조체에 대해서는 따로 설명드리지 않아도 단번에 이해하실것 같네요. 이번엔 CircularClass를 살펴보도록 하겠습니다.
class CircularQueue
{
private:
Node* node; // 노드 배열
int capacity; // 큐의 용량
int front; // 전단의 인덱스
int rear; // 후단의 인덱스
public:
CircularQueue(int capacity)
{
this->capacity = capacity + 1; // 노드 배열의 크기는 실제 용량에서 1을 더한 크기 (더미 공간 때문)
node = new Node[this->capacity]; // Node 구조체 capacity + 1개를 메모리 공간에 할당한다
front = 0; rear = 0; // 전단과 후단의 초기화
}
..
위의 CircularQueue 생성자를 보시면, 위에서 말했듯이 노드 배열의 크기는 실제 용량에서 1을 더한 크기여야 합니다. 이는 더미(Dummy) 공간 때문이며, 더미 공간이 존재하는 이유는 큐가 꽉찼는지, 비어있는지를 구분하기 위한 것입니다. 이번에는 enqueue 함수를 살펴보도록 합시다.
..
void enqueue(int data)
{
int pos; // 데이터가 들어갈 인덱스
// 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면
if (rear == capacity - 1) {
// pos에 rear를 대입하고, rear를 0으로 초기화 시킨다
pos = rear; rear = 0;
} else // 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
pos = rear++; // pos에 rear 값을 들여놓고, rear의 값을 1 증가시킨다
node[pos].data = data; // pos 번째의 노드의 데이터에 data를 대입한다
}
..
위의 삽입 함수를 보시면, 더미 공간을 제외한 큐의 용량과 후단의 인덱스를 비교하는데 만약 서로 같다면 pos에 후단의 인덱스를 대입합니다. 그리고 후단의 인덱스를 0으로 초기화 시킵니다. 여기서 0으로 초기화 시키는 이유는, 큐가 순환하는 큐이기에 계속 이어지기 때문입니다. 그리고 더미(Dummy) 공간에는 데이터가 들어갈 수 없습니다. 반대로, 서로 같지 않다면 그냥 후단의 인덱스를 pos에 대입하고, 후단의 인덱스를 1만큼 증가시킵니다.
..
int dequeue() {
int pos = front; // pos에 전단의 인덱스 대입
// 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면
if (front == capacity - 1) front = 0; // front를 0으로 초기화 시킨다
// 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
else front++; // 전단의 인덱스를 1 증가시킨다
return node[pos].data; // 제외되는 데이터를 반환한다
}
..
위의 제거 함수를 살펴보면, 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같은지 비교합니다. 만약에 같을 경우, 전단의 인덱스를 0으로 초기화 시킵니다. 삽입 함수와 마찬가지로 전단의 인덱스가 더미 공간을 제외한 큐의 용량을 넘어서려고 하면 0으로 초기화 시키고 계속 이어가도록 만들어 주어야 합니다. 반대로, 같지 않다면 그냥 전단의 인덱스를 간단하게 1만 증가시키면 됩니다. 그럼, 전의 전단이었던 노드가 제외되는 셈입니다. 이번엔 getSize 함수를 살펴보도록 합시다.
..
int getSize() {
if (front <= rear) // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작다면
return rear - front; // 후단의 인덱스에서 전단의 인덱스를 뺀값을 반환한다
else // 전단의 인덱스가 후단의 인덱스보다 크다면
return capacity - front + rear; // 용량에서 전단의 인덱스를 뺀 뒤에 후단의 인덱스를 더한 값을 반환한다
}
..
큐의 크기를 가져오는 함수를 살펴보면, 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작은지 비교합니다. 만약 같거나 작을 경우에는, 후단의 인덱스에서 전단의 인덱스를 빼주면 됩니다. 반대로, 전단의 인덱스가 후단의 인덱스보다 크다면 더미 공간을 포함한 큐의 용량에서 전단의 인덱스를 빼고 후단의 인덱스를 더합니다.
만약 위 그림처럼, 전단의 인덱스가 2, 후단의 인덱스가 7이라고 가정합니다. 후단의 인덱스는 실제 후단의 인덱스에 1을 더한 값이므로 요소가 존재하는 위치는 2, 3, 4, 5, 6 입니다. 여기서 후단의 인덱스에서 전단의 인덱스를 빼주면 5가 나오는겁니다. (설명이 조금 애매할지도 몰라서, 이부분에 대해 궁금한 사항이 있으시면 댓글로 달아주세요.) 요번엔, 비어있는지 꽉차있는지 구분을 하기 위한 함수를 구현해보도록 합시다.
..
bool isEmpty() {
return front == rear; // 전단의 인덱스와 후단의 인덱스가 같을 경우 true, 아니면 false
}
bool isFull() {
// 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작을 경우
if (front <= rear)
return (rear - front) == (capacity - 1); // 후단의 인덱스에서 전단의 인덱스를 뺀 뒤의 결과가 더미 공간을 제외한 큐의 용량과 같을 경우
else // 전단의 인덱스가 후단의 인덱스보다 클 경우
return (rear + 1) == front; // 후단의 다음 노드가 전단 노드면 true, 아니면 false
}
..
비어있는 경우를 확인하는 함수는 isEmpty 이고, 이 함수는 전단의 인덱스와 후단의 인덱스가 같으면 큐가 비어있는 것이므로 true를, 아닐 경우에는 false를 반환하도록 했습니다. 다음 꽉차있는 경우를 확인하는 함수인 isFull은 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작을 경우 후단의 인덱스에서 전단의 인덱스를 뺀 값과 더미 공간을 제외한 큐의 용량이 서로 같은지 비교합니다. (더미 공간엔 데이터가 들어가지 않으므로. 참고로 더미 공간은 고정되어 있는게 아니며 계속 움직입니다.) 반대로 전단의 인덱스가 후단의 인덱스보다 크다면 간단히 후단의 다음 노드가 전단 노드인지 확인을 하시면 됩니다. 아래 예를 한번 살펴보도록 합시다.
예>
#include <iostream>
using namespace std;
typedef struct Node
{
int data; // 데이터 필드
} Node;
class CircularQueue
{
private:
Node* node; // 노드 배열
int capacity; // 큐의 용량
int front; // 전단의 인덱스
int rear; // 후단의 인덱스
public:
CircularQueue(int capacity)
{
this->capacity = capacity + 1; // 노드 배열의 크기는 실제 용량에서 1을 더한 크기 (더미 공간 때문)
node = new Node[this->capacity]; // Node 구조체 capacity + 1개를 메모리 공간에 할당한다
front = 0; rear = 0; // 전단과 후단의 초기화
}
~CircularQueue()
{
delete []node; // 노드 배열 소멸
}
void enqueue(int data)
{
int pos; // 데이터가 들어갈 인덱스
// 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면
if (rear == capacity - 1) {
// pos에 rear를 대입하고, rear를 0으로 초기화 시킨다
pos = rear; rear = 0;
} else // 후단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
pos = rear++; // pos에 rear 값을 들여놓고, rear의 값을 1 증가시킨다
node[pos].data = data; // pos 번째의 노드의 데이터에 data를 대입한다
}
int dequeue() {
int pos = front; // pos에 전단의 인덱스 대입
// 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같다면
if (front == capacity - 1) front = 0; // front를 0으로 초기화 시킨다
// 전단의 인덱스와 더미 공간을 제외한 큐의 용량이 같지 않다면
else front++; // 전단의 인덱스를 1 증가시킨다
return node[pos].data; // 제외되는 데이터를 반환한다
}
int getSize() {
if (front <= rear) // 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작다면
return rear - front; // 후단의 인덱스에서 전단의 인덱스를 뺀값을 반환한다
else // 전단의 인덱스가 후단의 인덱스보다 크다면
return capacity - front + rear; // 용량에서 전단의 인덱스를 뺀 뒤에 후단의 인덱스를 더한 값을 반환한다
}
bool isEmpty() {
return front == rear; // 전단의 인덱스와 후단의 인덱스가 같을 경우 true, 아니면 false
}
bool isFull() {
// 전단의 인덱스가 후단의 인덱스와 같거나 그보다 작을 경우
if (front <= rear)
return (rear - front) == (capacity - 1); // 후단의 인덱스에서 전단의 인덱스를 뺀 뒤의 결과가 더미 공간을 제외한 큐의 용량과 같을 경우
else // 전단의 인덱스가 후단의 인덱스보다 클 경우
return (rear + 1) == front; // 후단의 다음 노드가 전단 노드면 true, 아니면 false
}
int getRear() { return rear; }
int getFront() { return front; }
};
int main()
{
CircularQueue cq(10);
int size;
// 데이터의 삽입과 제거
cq.enqueue(10); cq.enqueue(20); cq.enqueue(30);
cq.dequeue(); cq.dequeue(); cq.dequeue();
cq.enqueue(10); cq.enqueue(20); cq.enqueue(30);
cq.enqueue(20); cq.enqueue(20); cq.enqueue(20);
cq.enqueue(20); cq.enqueue(20); cq.enqueue(520);
// 큐의 현재 크기를 얻어옴
size = cq.getSize();
for (int i = 0; i < size; i++)
cout << "빠져나간 데이터: " << cq.dequeue() << ", Front: " << cq.getFront() << ", Rear: " << cq.getRear() << endl;
return 0;
}
결과:
빠져나간 데이터: 10, Front: 3, Rear: 1
빠져나간 데이터: 20, Front: 4, Rear: 1
빠져나간 데이터: 30, Front: 5, Rear: 1
빠져나간 데이터: 20, Front: 6, Rear: 1
빠져나간 데이터: 20, Front: 7, Rear: 1
빠져나간 데이터: 20, Front: 8, Rear: 1
빠져나간 데이터: 20, Front: 9, Rear: 1
빠져나간 데이터: 20, Front: 10, Rear: 1
빠져나간 데이터: 520, Front: 0, Rear: 1
계속하려면 아무 키나 누르십시오 . . .
위의 예의 메인 함수부터 보시면, "데이터 삽입 3번 -> 데이터 제거 3번 -> 데이터 삽입 9번" 이런식으로 되어있는데, 처음 데이터 삽입 3번으로 후단의 인덱스가 3이나 증가합니다. 그 다음 데이터 제거 3번으로 인해 전단의 인덱스도 3이나 증가합니다. 그다음 데이터 삽입 9번으로 인해 후단의 인덱스값이 9나 증가합니다. 그러나 큐의 용량을 초과하므로 큐의 용량에서 후단의 인덱스를 뺍니다. 그럼 후단의 인덱스가 1인데, 그 뒤에 for문으로 큐에 남아있는 데이터를 모두 제거하니 최종적으로 전단과 후단의 인덱스는 1이 되었습니다. 순환 큐는 편리하기 한것 같으나 좀 복잡한 것 같죠? 이번에는 링크드 큐를 한번 살펴보도록 합시다.
2. 링크드 큐(Linked Queue) 원형이 아닌 직선으로!
이번엔 순환 큐(Circular Queue)가 아닌, 링크드 큐(Linked Queue) 입니다. 링크드가 하니 링크드 리스트가 떠오르지 않나요? 비슷합니다. 링크드 큐의 노드에도 그 노드의 다음을 가리키는 주소값을 가지고 있으며, 노드가 전단(Front) -> 후단(Rear) 방향으로 이어져 있습니다. 그래도 전단에서 제거 연산이 이루어 진다는 것과, 후단에서 삽입 연산이 이루어진다는 것은 바뀌지 않습니다. 링크드 큐의 구현은 상당히 간단합니다. 링크드 큐는 삽입 연산때는 후단 노드의 다음 노드에 새로 추가되는 노드를 넣고, 제거 연산때는 전단의 위치를 앞으로 옮기면 됩니다. 한번 그림으로 보도록 합시다.
위의 그림을 보시면, 전단에 있는 노드를 제거했을때 단순히 전단의 위치를 다음 노드로 넘기면 됩니다. 그러곤 그게 끝입니다. 삽입도 이와 비슷합니다. 후단의 nextNode에 새로 추가되는 노드의 주소값을 넣고 새로 추가되는 노드를 후단 노드로 지정하면 됩니다. 참고로, 순환 큐와는 다르게 리스트 큐는 크기에 제한을 받지 않습니다. (크기가 유연함) 링크드 큐의 노드를 구조체로 정의해보도록 합시다.
typedef struct Node {
int data; // 데이터 필드
struct Node* nextNode; // 다음 노드를 가리키는 주소값
} Node;
순환 큐의 노드 구조체에선 데이터 필드밖에 없었지만, 링크드 큐에 와서는 다음 노드를 가리키는 주소값이 포함됩니다. 이번에는 LinkedQueue 클래스의 멤버 변수와 생성자, 소멸자를 살펴보도록 합시다.
class LinkedQueue {
private:
int size; // 큐의 크기
Node* front; // 전단의 주소값
Node* rear; // 후단의 주소값
public:
LinkedQueue()
{
size = 0; // 크기를 0으로 초기화 한다
front = NULL; // 전단의 주소값을 NULL로 초기화 한다
rear = NULL; // 후단의 주소값을 NULL로 초기화 한다
}
~LinkedQueue()
{
while(!isEmpty()) // 큐가 비어있지 않을때까지
{
Node* deq = dequeue(); // 전단에 존재하는 노드를 제거한다
delete deq; // 메모리 공간에서 deq를 해제한다
}
}
..
순환 큐와 비교하여 다른부분만 설명을 드리도록 하겠습니다. 전단의 주소값, 후단의 주소값을 담을 수 있는 노드 구조체의 포인터가 멤버로 선언되었습니다. LinkedQueue의 생성자에선 size와 front, rear의 초기화가 이루어지며 소멸자에서는 큐를 비우기 위해, 큐 내에있는 노드를 모두 제거하고 메모리 공간에서 해제합니다. 이번에는 삽입(Enqueue) 메서드를 살펴보도록 합시다.
..
void enqueue(int data)
{
Node* newNode = new Node(); // 새로 노드를 추가한다
newNode->data = data; // 새로 추가된 노드의 데이터에 매개변수로 받은 데이터의 값을 대입한다
newNode->nextNode = NULL; // 다음 노드를 NULL로 초기화 한다
if (front == NULL) // 전단의 주소값이 NULL 이라면, 즉 처음 추가하는 것이라면
{
front = newNode; rear = newNode; // 전단의 주소값과 후단의 주소값은 새로 추가된 노드의 주소값
} else {
rear->nextNode = newNode; // 후단의 다음 노드를 새로 추가된 노드로 지정한다
rear = newNode; // 새로 추가된 노드를 후단으로 지정한다
}
size++; // 크기를 1 증가시킨다
}
..
위의 삽입 메서드를 살펴보면, 노드를 새로 추가하고 데이터를 집어넣습니다. 그리고 전단의 주소값이 NULL이라면, 큐가 비어있음을 의미하겠죠? 이럴 경우 전단과 후단을 새로 추가된 노드로 지정하시면 됩니다. 만약, 처음 추가하는게 아니라 한개 이상 존재한다면 후단의 다음 노드를 새로 추가된 노드로 지정하고 새로 추가된 노드는 가장 뒤에있는 노드니 후단 노드로 지정합니다. 이번엔 제거(Dequeue) 메서드를 보도록 합시다.
..
Node* dequeue()
{
Node* temp = front; // 전단의 주소값을 temp에 대입한다
if (front->nextNode == NULL) // 전단의 다음 노드가 NULL 인것은 노드가 하나 이하이다
{
rear = NULL; front = NULL; // 전단과 후단의 주소값을 NULL로 초기화한다
} else // 전단의 다음 노드가 존재한다면, 즉 노드가 두개 이상이라면
front = front->nextNode; // 전단의 다음 노드를 전단으로 지정한다
size--; // 크기를 1 감소시킨다
return temp; // 큐에서 제거된 전단의 주소값을 반환한다
}
..
위의 제거 메서드를 살펴보면, 임시 포인터를 하나 만들어서 전단의 주소값을 대입합니다. 그런 다음에 전단의 다음 노드가 NULL이면 노드가 하나 이하인 경우이므로, 후단과 전단에 각각 NULL을 대입하여 아무것도 가리키지 않게 합니다. 만약에, 다음 노드가 NULL이 아니라면 그건 두개 이상의 노드가 큐에 존재하고 있다는 것으로, 전단의 다음 노드를 전단으로 지정하시면 됩니다. 이번엔 getSize 함수와 isEmpty 함수를 보도록 합시다. (isFull 함수는 링크드 큐에선 '꽉찬다'라는 개념이 없기 때문에 제외하겠습니다.)
..
// 큐가 비어있는지 확인을 한다
bool isEmpty() { return front == NULL; } // 전단의 주소값이 NULL이라면, 즉 큐가 비어있다면 true 아닐 경우 false
int getSize() { return size; } // 큐의 크기를 가져온다
..
위의 isEmpty 함수는 전단의 주소값이 NULL일 경우, 즉 큐 내에 노드가 하나라도 없을 경우에는 true가 되며 하나 이상이 존재할 경우에는 false가 됩니다. getSize 함수는 size 변수의 값을 반환합니다. (size 변수는 큐 내에 존재하는 노드의 수를 말합니다) LinkedQueue 클래스는 모두 살펴보았으니, 전체 예제를 한번 살펴보도록 합시다.
예>
#include <iostream>
using namespace std;
typedef struct Node {
int data; // 데이터 필드
struct Node* nextNode; // 다음 노드를 가리키는 주소값
} Node;
class LinkedQueue {
private:
int size; // 큐의 크기
Node* front; // 전단의 주소값
Node* rear; // 후단의 주소값
public:
LinkedQueue()
{
size = 0; // 크기를 0으로 초기화 한다
front = NULL; // 전단의 주소값을 NULL로 초기화 한다
rear = NULL; // 후단의 주소값을 NULL로 초기화 한다
}
~LinkedQueue()
{
while(!isEmpty()) // 큐가 비어있지 않을때까지
{
Node* deq = dequeue(); // 전단에 존재하는 노드를 제거한다
delete deq; // 메모리 공간에서 deq를 해제한다
}
}
void enqueue(int data)
{
Node* newNode = new Node(); // 새로 노드를 추가한다
newNode->data = data; // 새로 추가된 노드의 데이터에 매개변수로 받은 데이터의 값을 대입한다
newNode->nextNode = NULL; // 다음 노드를 NULL로 초기화 한다
if (front == NULL) // 전단의 주소값이 NULL 이라면, 즉 처음 추가하는 것이라면
{
front = newNode; rear = newNode; // 전단의 주소값과 후단의 주소값은 새로 추가된 노드의 주소값
} else {
rear->nextNode = newNode; // 후단의 다음 노드를 새로 추가된 노드로 지정한다
rear = newNode; // 새로 추가된 노드를 후단으로 지정한다
}
size++; // 크기를 1 증가시킨다
}
Node* dequeue()
{
Node* temp = front; // 전단의 주소값을 temp에 대입한다
if (front->nextNode == NULL) // 전단의 다음 노드가 NULL 인것은 노드가 하나뿐이다
{
rear = NULL; front = NULL; // 전단과 후단의 주소값을 NULL로 초기화한다
} else // 전단의 다음 노드가 존재한다면, 즉 노드가 두개 이상이라면
front = front->nextNode; // 전단의 다음 노드를 전단으로 지정한다
size--; // 크기를 1 감소시킨다
return temp; // 큐에서 제거된 전단의 주소값을 반환한다
}
// 큐가 비어있는지 확인을 한다
bool isEmpty() { return front == NULL; } // 전단의 주소값이 NULL이라면, 즉 큐가 비어있다면 true 아닐 경우 false
int getSize() { return size; } // 큐의 크기를 가져온다
};
int main()
{
LinkedQueue lq;
int size;
// 데이터의 삽입과 제거
lq.enqueue(50);
lq.enqueue(60);
lq.dequeue();
lq.enqueue(80);
lq.enqueue(90);
lq.dequeue();
lq.enqueue(89);
// 큐의 크기를 가져온다
size = lq.getSize();
for(int i = 0; i < size; i++)
cout << "빠져나간 데이터: " << lq.dequeue()->data << endl;
return 0;
}
결과:
빠져나간 데이터: 80
빠져나간 데이터: 90
빠져나간 데이터: 89
계속하려면 아무 키나 누르십시오 . . .
위의 예제에서, 메인 함수부터 살펴보면 "데이터 삽입 2번->데이터 제거 1번->데이터 삽입 2번->데이터 제거 1번->데이터 삽입 1번" 순으로 이루어지고 있습니다. 먼저, 50과 60이 큐에 들어오고, 50이 빠져나갑니다. 그런 다음 80과 90이 큐에 들어왔으니 60, 80, 90 이죠? 그 뒤에는 60이 빠져나가고 89가 새로 들어왔으니 80, 90, 89가 되는 것입니다. (순서대로 빠져나감) 링크드 큐를 직접 구현해보니 환형 큐에 비해 구조가 간단하죠? 링크드 큐는 구현이 간단하다는 장점 등이 있으나, 노드를 제거하거나 삽입할때 new, delete 연산을 수행합니다. 반면에 환형 큐는 고성능인 반면에, 구현이 링크드 큐보다 복잡하다는 단점 등이 있습니다.
'알고리즘, 자료구조' 카테고리의 다른 글
| 알고리즘 2-1강. 탐색 알고리즘 - 순차 탐색(Sequential Search) (2) | 2013.05.23 |
|---|---|
| 자료구조 4강. 트리(Tree) (4) | 2013.01.23 |
| 자료구조 2강. 스택(Stack) (8) | 2013.01.09 |
| 자료구조 1강. 리스트(List) (20) | 2013.01.01 |
| 비주얼베이직6 움직임에 관한 수학공식 정리 (4) | 2012.10.03 |