C++에서 연결 목록을 사용한 스택 데이터 구조
이 기사에서는 C++에서 연결 목록을 사용하여 스택 데이터 구조를 구현하는 방법을 설명합니다.
C++에서 단일 연결 목록을 사용하여 스택 데이터 구조 구현
스택은 프로그램에서 자주 사용되는 추상 데이터 구조이며 가장 친숙한 사용 사례는 프로그램 스택 메모리입니다.
이 추상 데이터 유형에는 푸시 및 팝이라는 두 가지 핵심 작업이 있습니다. 전자는 다른 요소 위에 요소 삽입을 수행하고 후자는 스택에서 가장 최근 요소를 제거합니다.
스택은 LIFO(라스트 인, 퍼스트 아웃) 데이터 구조로 분류됩니다. 스택은 다른 방법으로 구현할 수 있지만 이 기사에서는 단일 연결 목록에서 스택을 구성합니다.
스택은 수정이 발생하는 최상위 요소만 추적하면 됩니다. 그렇지 않으면 본질적으로 고정 용량이 있거나 없을 수 있는 순차적인 데이터 모음입니다. 후자는 프로그래머가 내리는 설계 결정에 따라 다릅니다.
다음 코드 조각은 사전 정의된 용량 제한 없이 확장할 수 있는 스택을 구현합니다. 먼저 단일 연결 목록의 노드를 정의하고 typedef를 ListNode로 정의합니다. 그런 다음 Stack 클래스를 선언하고 목록의 맨 위를 추적하기 위해 단 하나의 데이터 멤버만 포함합니다.
이 예에서는 push 및 printNode 기능만 구현합니다. push 멤버 함수는 목록의 맨 위에 모든 새 요소를 추가한다는 점을 제외하고 단일 연결 목록의 삽입 작업과 유사하게 작동합니다.
Stack 클래스에는 첫 번째 요소를 초기화하는 생성자가 있지만 이 잘못된 디자인 선택은 이 소개 기사의 예제 코드를 단순화하기 위한 것일 뿐입니다.
반면 printNodes 멤버 함수는 스택 데이터 유형의 필수 함수는 아니지만 데모를 더 쉽게 만듭니다. 구현이 의도한 대로 작동하는지 확인하는 데 도움이 됩니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void printNodes();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
이전 코드에는 스택 데이터 구조가 제대로 작동하는 데 필요한 pop 작업이 없습니다. 우리는 무한 스택을 구현하고 예제의 단순성에만 신경을 쓰기 때문에 메모리 할당은 주문형으로 관리됩니다. 모든 pop 작업은 delete를 호출하여 맨 위에 있는 이전 요소가 보유한 메모리를 해제합니다. 실제 시나리오에서는 더 나은 성능을 위해 스택의 용량을 제한하거나 일부 메모리를 미리 할당하는 것을 선호해야 합니다.
마지막으로 개체가 범위를 벗어난 후에 개체를 해제하는 소멸자가 있어야 합니다. 소멸자 함수는 스택의 끝을 나타내는 nullptr이 발견될 때까지 top 요소에서 반복합니다.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class Stack {
public:
explicit Stack(string data) {
top = new ListNode;
top->data = std::move(data);
top->next = nullptr;
};
ListNode *push(string data);
void pop();
void printNodes();
~Stack();
private:
ListNode *top = nullptr;
};
ListNode *Stack::push(string data) {
auto new_node = new ListNode;
new_node->data = std::move(data);
new_node->next = top;
top = new_node;
return top;
}
void Stack::pop() {
auto tmp = top->next;
delete top;
top = tmp;
}
Stack::~Stack() {
struct ListNode *tmp = nullptr;
while (top) {
tmp = top->next;
delete top;
top = tmp;
}
}
void Stack::printNodes() {
auto count = 0;
auto tmp = top;
while (tmp) {
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
}
int main() {
vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};
Stack s1("Xenial");
for (const auto &item : data_set) {
s1.push(item);
}
s1.printNodes();
cout << "/ ------------------------------ / " << endl;
s1.pop();
s1.pop();
s1.printNodes();
return EXIT_SUCCESS;
}
node 0 - data: Raring
node 1 - data: Saucy
node 2 - data: Quantal
node 3 - data: Precise
node 4 - data: Xenial
/ ------------------------------ /
node 0 - data: Quantal
node 1 - data: Precise
node 2 - data: Xenial
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