이중 연결 리스트 (Doubly Linked List)기존 연결 리스트는 단순히 한 방향으로만 이동할 수 있었다. 양방향에 대한 포인터를 가지는 노드를 사용하면 양방향으로 이동할 수 있는 이중 연결 리스트를 구현할 수 있다.양방향 노드template class BidirectionalNode{ public: BidirectionalNode(T data) { this->data = data; } T data; BidirectionalNode* left = nullptr; BidirectionalNode* right = nullptr;};노드 삽입양쪽 노드에 대한 포인터 처리만 해주면 된다.// 삽입void Insert(Bidir..

연결 리스트의 다항식 표현연결 리스트의 각 노드가 한 개의 항을 표현하게 하면 노드를 이어 붙여 다항식을 표현할 수 있다.Term 구조체각 항을 나타내기 위해 구조체를 사용계수지수Set 함수: 구조체의 값을 설정// 각 항을 나타내는 구조체struct Term{ int coef; // 계수 int exp; // 지수 Term Set(int c, int e) { coef = c; exp = e; return *this; }};연결 리스트단순 연결 리스트를 사용한다. 각 노드는 data(coef, exp)와 next로 구성된다.SinglyLinkedList poly; // 다항식 => data(coef, exp), next로 구성다항식 클래스다..

연결 스택 (Linked Stack)연결 리스트를 사용해 스택을 구현한 것스택에 Push 할 때는 새로운 노드의 포인터를 top을 가리키게 해 스택의 맨 위에 올라오게 한 후, 새로운 노드를 top으로 설정한다.Pop하는 경우 top을 다음 노드로 옮긴 후, 맨 위에 있는 노드를 삭제한다.코드#include "../Node.hpp"#include template class LinkedStack{public: bool IsEmpty() { if (top == nullptr) return true; else return false; } Node* Top() { if (!IsEmpty()) ..

가용 공간 리스트 (Available-Space List)기존 단순 연결 리스트와 원형 리스트에서의 노드를 생성하고 삭제하는데 시간이 소요된다. 만약 삭제된 노드를 다른 장소에 유지한다면 노드를 새로 생성하고 삭제하는 시간을 O(1)로 줄일 수 있다. 이를 구현하기 위해선 삭제된 노드를 연결해놓을 리스트가 필요한데, 이를 가용 공간 리스트라 한다.Node* av = nullptr; // available-space list노드 생성과 삭제가용 공간 리스트가 있다면, 노드의 생성과 삭제에 new와 delete를 사용하지 않고 가용 공간 리스트에서 노드를 가져오는 함수를 사용하면 된다.// 가용 공간 리스트(av)에서 사용할 노드 가져옴// new 키워드로 노드 객체 생성하는 것 대신 사용Node* GetN..

단순 연결 원형 리스트 (Singly Linked Circular List)기존 연결 리스트에서 마지막 노드의 포인터가 첫 번째 노드를 가리키게 하면 된다.원형 리스트의 마지막 노드 검사기존 단순 연결 리스트에서는 마지막 노드를 검사하기 위해 포인터가 nullptr인지 검사하면 됐지만, 원형 리스트에서는 포인터가 head인지 검사하면 된다.원형 리스트의 삽입기본적인 작동 방식은 단순 연결 리스트와 같으나, 다음 경우에는 따로 처리를 해줘야 한다.리스트의 맨 앞에 삽입하는 경우, 마지막 노드의 포인터가 새로 삽입한 노드를 가리키게 한 후 head로 설정만약 맨 마지막 노드를 가리키는 rear가 있는 경우, rear의 포인터가 새 노드를 가리키게 설정해주면 O(1)으로 삽입 가능리스트의 맨 뒤에 삽입하는 경..

연결 표현순차 저장 방법은 임의의 원소에 접근하거나 스택이나 큐에 원소를 삽입하거나 삭제하는 것과 같은 작업에 적합하다.하지만 삽입, 삭제가 자주 일어나는 경우 매우 불리한 구조가 된다. (예를 들어, 배열의 경우 원소 하나를 삭제하면 뒤에 있는 모든 원소를 앞으로 당겨야 함) 연결된(linked) 표현의 특징은 다음과 같음각 원소들이 메모리의 어떤 곳에나 위치할 수 있음 (물리적으로 순차적인 위치에 존재할 필요 없음)각 원소와 함께 그 다음 원소를 가리키는 주소 또는 위치를 저장함 (포인터 또는 링크라 함)연결 리스트는 배열과 비교해 동적 크기 조정이 가능한 것이 장점단순 연결 리스트 (Singly Linked List)단순 연결 리스트 또는 체인의 특징은 다음과 같음정확히 하나의 포인터 필드를 가짐삽..

후위 표기법후위 표기법(postfix notation)을 사용하면 매우 쉽게 수식을 계산할 수 있다. 후위 표기법은 연산자가 피연산자들 뒤에 온다.중위 표기법: A/B-C + D*E - A*C후위 표기법: AB/C-DE*AC*-후위 표기법은 다음과 같은 이유로 계산을 쉽게 만든다.괄호의 필요성이 없어짐연산자 우선순위의 의미가 없어짐왼쪽에서 훑어 나가면서 피연산자가 나오면 스택에 넣고, 연산자가 나오면 적당한 피연산자를 스택에서 꺼내 연산하고 그 결과를 다시 스택에 집어 넣으면 됨수도 코드void Eval(Expression e){ Stack stack; for (int i = 0; i 중위 표현법 -> 후위 표현법 변환연산자를 두 개의 피연산자의 맨 오른쪽으로 옮기면 된다A / B - C +..

개요front에서 원소가 Pop되고, rear에서 원소가 Push되는 순서 리스트선입선출(First In First Out, FIFO)일반적인 선형 큐는 공간이 남는 문제가 있음 => modulo 연산으로 원형 큐 구현(front + 1) % capacity(rear + 1) % capacity선형 큐와 달리 front가 가리키는 곳은 비어있고, front의 한 칸 앞부터 값이 실제로 저장됨 => 원형 큐는 한 칸 버려야 함큐에서 구현할 기능생성자: 큐 capacity 초기화 및 큐 배열 할당소멸자: 큐 배열 삭제IsEmpty: front == rear일 때 공백FrontRearEnqueue: 크기가 부족한 경우 2배로 늘려서 데이터 옮김Dequeue: front를 한 칸 앞으로 옮겨서 삭제한 것처럼 처..