목록ComputerScience/DataStructure (12)
Nagie's DevStory
아래의 코드는 C++로 구현된 환형 큐(Circular Queue)다. 일반 큐와 유사하지만 고정된 크기의 버퍼를 사용해 데이터를 순환하면서 자료를 저장하는 구조를 띠고 있으며 구현에 사용되는 std::vector 대신 일반적인 C 스타일 배열을 사용할 수도 있었지만, STL이 제공하는 편의성 때문에 C 스타일 배열을 사용하지 않았다. #pragma once #include template class CircularQueue { private: std::vector buffer; int front; // 큐의 시작 인덱스 int rear; // 큐의 끝 인덱스 int capacity; public: CircularQueue(int size) { capacity = size; buffer.resize(si..
아래의 코드는 C++로 구현된 큐(Queue)다. 가변 배열과 연결 리스트로 각각 구현되어 있으며 큐는 FIFO(First-In-First-Out) 원칙을 따르는 컨테이너 어댑터이기에 내부에서 사용하는 자료구조는 C++ STL에서 제공하는 std::vector와 std::list 컨테이너를 사용해 구현했다. std::vector(가변 배열)로 구현된 큐 #pragma once #include template class queue { private: std::vector vecQueue; public: void push(const T& data) { vecQueue.push_back(data); } void pop() { vecQueue.pop_back(); } bool isEmpty() const { r..
아래의 코드는 C++로 구현된 스택(Stack)이다. 가변 배열과 연결 리스트로 각각 구현되어 있으며 큐는 LIFO(Last-In-First-Out) 원칙을 따르는 컨테이너 어댑터이기에 내부에서 사용하는 자료구조는 C++ STL에서 제공하는 std::vector와 std::list 컨테이너를 사용해 구현했다. std::vector(가변배열)로 구현된 스택 #pragma once #include template class stack { private : std::vector vecStack; public : void push(const T& data) { vecStack.push_back(data); } void pop() { if (vecStack.empty()){ return; } vecStack.po..
아래의 코드는 C++로 구현된 이중 연결 리스트다. C++ STL의 이터레이터를 흉내 내서 구현했으며 단방향 연결 리스트와는 다르게, 이전노드에 대한 접근이 자유롭다. #pragma once template struct Node { T data; Node* prev; Node* next; }; template class list { private: Node* header; Node* trailer; int nSize; public: class iterator { //STL의 이터레이터와 같은 역할 private: Node* nodePtr; public: iterator() : nodePtr(nullptr) {} iterator(Node* p) : nodePtr(p) {} T& operator*() { /..
아래의 코드는 C++로 구현된 단방향 연결 리스트다. 구현된 기능은 노드 추가와 노드 삭제 그리고 노드를 역방향으로 뒤집는 기능이며 헤더 파일에 인라인 형태로 작성했다. #pragma once #include template struct Node { T data; Node* next; }; template class fwd_list { private : Node* nodeHead; int nSize; public : fwd_list() { nodeHead = nullptr; nSize = 0; } ~fwd_list() { while (!isEmpty()) { pop(); } } void push(const T& data) { Node* newNode = new Node{ data, nullptr }; i..