C++에서 연결 목록을 사용하여 대기열 데이터 구조 구현
이 기사에서는 C++에서 연결 목록을 사용하여 큐 데이터 구조를 구현하는 방법을 설명합니다.
C++에서 단일 연결 목록을 사용하여 대기열 데이터 구조 구현
큐는 FIFO(선입 선출) 방식으로 요소를 관리하는 데이터 구조이므로 처음 추가된 요소가 큐에서 가장 먼저 제거됩니다.
일반적으로 큐 데이터 구조에 대한 삽입 및 제거 작업을 각각 enqueue 및 dequeue라고 합니다. 추상 큐는 다양한 방법과 데이터 구조를 사용하여 구현할 수 있습니다. 일반적으로 새 요소가 추가되는 쪽을 프론트라고 하고 요소가 제거되는 쪽을 대기열의 뒤쪽이라고 합니다.
다음 예제에서는 데이터 개체를 저장하는 노드와 다음 노드에 대한 포인터로 구성된 단일 연결 목록을 사용하여 대기열을 구현합니다. 이 경우 단순성을 위해 단일 string 개체로 데이터 개체를 나타내기로 선택했지만 가장 최적의 노드 구조를 설계하는 것은 프로그래머에게 달려 있습니다.
다음으로 front, back 및 size의 세 가지 데이터 멤버를 포함하는 Queue라는 class를 정의할 수 있습니다. 전자는 자명하지만 후자는 큐의 현재 요소 수를 나타냅니다. 대기열 데이터 구조의 두 가지 주요 변형은 무제한 및 제한이 있으며, 전자는 사용 가능한 메모리가 생길 때까지 요소를 추가할 수 있습니다. 반면에 bounded queue는 고정된 수의 요소만 저장하도록 설계되었습니다.
이 기사에서 우리는 무한한 대기열을 설계하지만 독자는 주어진 코드 샘플에서 약간의 수정으로 제한된 대기열을 직관적으로 개발할 수 있습니다. 처음부터 무한 큐를 구현하기 때문에 큐가 커짐에 따라 동적 메모리 할당을 관리해야 합니다. 따라서 enQueue 및 deQueue 멤버 함수에는 new 및 delete 연산자가 포함됩니다. 대기열의 이 구현은 효율적인 구현을 위한 것이 아니라 일반적으로 이 데이터 구조의 기본 작동 메커니즘을 보여줍니다.
Queue에는 두 개의 생성자가 있습니다. 그 중 하나는 string 값의 initializer_list를 사용하고 enQueue 함수를 여러 번 호출하여 Queue 개체를 구성합니다. 각 enQueue 호출은 size 멤버를 증가시키며, 필요한 경우 클래스 사용자는 getSize 함수를 사용하여 해당 값을 검색할 수 있습니다. 또한 주어진 Queue 객체의 내용을 검사하기 위해 도우미 함수 printNode를 구현했습니다. 이 함수는 실제 시나리오에서 정의할 필요가 없지만 테스트 및 디버깅에 유용할 수 있습니다.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
q1.enQueue("Xenial");
q1.enQueue("Bionic");
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
출력:
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
queue size = 4
/ ------------------------------ /
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Xenial
node 5 - data: Bionic
queue size = 6
이전 Queue 클래스에는 소멸자 구현과 대기열에서 요소를 제거하는 기능이 없습니다. 이 두 가지는 다음 코드 조각에 정의되어 있으며 해당 드라이버 코드는 프로그램의 main 기능에 포함되어 있습니다.
deQueue 함수는 구현에 특정한 string 값을 반환하도록 설계되었습니다. 결과적으로 이 함수는 대기열이 비어 있음을 나타내기 위해 빈 문자열을 반환하며 반환 값을 확인할 책임은 사용자에게 있습니다. 한편 소멸자 함수는 개체가 범위를 벗어나기 전에 할당된 모든 메모리가 해제되도록 합니다.
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Queue {
public:
explicit Queue() {
back = front = nullptr;
size = 0;
};
Queue(std::initializer_list<string> list);
ListNode *enQueue(string data);
string deQueue();
void printNodes();
size_t getSize() const;
~Queue();
private:
ListNode *front;
ListNode *back;
size_t size;
};
Queue::Queue(std::initializer_list<string> list) {
front = back = nullptr;
size = 0;
for (const auto &item : list) {
enQueue(item);
}
}
ListNode *Queue::enQueue(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = nullptr;
if (front == nullptr) {
front = back = new_node;
size++;
return new_node;
}
back->next = new_node;
back = back->next;
size++;
return new_node;
}
string Queue::deQueue() {
if (front == nullptr)
return "";
else {
auto tmp = front->next;
auto data = front->data;
delete front;
front = tmp;
size--;
return data;
}
}
Queue::~Queue() {
struct ListNode *tmp = nullptr;
while (front) {
tmp = front->next;
delete front;
front = tmp;
}
}
void Queue::printNodes() {
auto count = 0;
auto tmp = front;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
size_t Queue::getSize() const { return size; }
int main() {
Queue q1 = {"Precise", "Quantal", "Saucy", "Raring"};
auto ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
cout << "queue size = " << q1.getSize() << endl;
cout << "/ ------------------------------ / " << endl;
while (!q1.deQueue().empty())
;
cout << "queue size = " << q1.getSize() << endl;
ret = q1.deQueue();
if (!ret.empty())
cout << ret << endl;
else
cout << "Queue is empty!" << endl;
for (int i = 0; i < 100; ++i) {
q1.enQueue("hello");
}
q1.printNodes();
cout << "queue size = " << q1.getSize() << endl;
return EXIT_SUCCESS;
}
Precise
queue size = 3
/ ------------------------------ /
queue size = 0
Queue is empty!
queue size = 100
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook