UpWrite

대기 손님 시뮬레이션 # 설명 생략(..) 큐 (대기자 목록 때문에 조금 수정) #pragma once template struct node { T data; node* next; }; template class QueueList { node* pFront; node* pRear; node* pCursor; int iCount; public: int Add(T data); int Remove(); T Peek(); int Count(); //대기 목록 보여주기용 void ResetCursor(); node* Next(); public: QueueList(); virtual ~QueueList(); }; template QueueList::QueueList() { pFront = nullptr; pRear..

스택을 이용해서 문자열 뒤집기 # 입력받은 문자열의 길이를 확인할 수 있으므로 배열 기반 스택을 사용했다. #include "stack_array.h" #include #include #if defined(UNICODE) || defined(_UNICODE) #define tcout std::wcout #define tcin std::wcin #else #define tcout std::cout #define tcin std::cin #endif int main() { TCHAR str[256] = { 0, }; tcout str; int strLen = _tcslen(str); StackArray rStr(strLen); for (int i = 0; i < strLen; i++) { rStr.Push(..

원형큐 # 일반적인 큐가 시작과 끝이 있는 선분의 형태라면 원형큐는 시작과 끝을 이어 고리형태를 이루게 한 구조이다. 배열 기반 큐의 문제점 # 배열 기반의 큐를 선형큐로 만들면 문제가 되는 것이 두가지 있다. # 첫째는 front를 항상 0번 인덱스로 유지하기 위해서는 Remove때마다 데이터를 이동시켜야 한다는 것이다. # 이를 해결하기 위해서는 Remove시에 front의 인덱스를 다음 인덱스로 이동시켜야만 한다. # 두번째 문제는 Add와 Remove를 반복할 시 Front와 Rear의 위치가 배열의 뒷부분으로 이동되어 앞부분에 공간이 있음에도 오버플로우가 발생한다는 것이다. 배열 기반 큐의 문제 해결 방법 # 배열 기반의 큐에서 이를 해결하는 방법은 두가지다. # 하나는 오버플로우가 발생했을 때..

큐 # 큐는 영어로 줄이나 대기 행렬을 의미하는 단어로, 먼저 들어온 데이터가 먼저 빠져나가는 구조의 리스트이다. # 영어로는 'FIFO(First In First Out)' 혹은 'LILO(Last In Last Out)' 구조의 자료구조로 불린다. # 입구와 출구가 각각 있는 구조라고 생각하면 이해하기 편하다. (이때 입구로 나가거나, 출구로 들어오는건 불가능하다고 가정한다.) # 일반적으로 줄의 출구 즉 큐의 맨 앞을 Front, 줄의 입구 즉 큐의 맨 끝을 Rear라고 한다. # 일반적으로 큐에 데이터를 넣는 행위를 Enqueue 혹은 Add, 큐에서 데이터를 빼는 행위를 Dequeue 혹은 Remove라고 한다. # 큐도 배열이나 연결 리스트를 이용해서 구현할 수 있다. # 하지만 큐를 배열로 ..

연결 리스트 기반 스택 # 스택을 연결 리스트를 이용해서 구현하면 스택의 크기를 신경쓰지 않아도 된다는 장점이 있다. # 연결 리스트 기반의 스택은 pTop(=pHead) 포인터가 가리키는 노드를 바꿔주는 것으로 구현이 가능하다. # push가 되면 새로운 노드를 리스트의 맨 앞에 연결한 뒤 pTop을 새로운 노드를 가리키게 한다. # Pop이 되면 pTop의 노드를 삭제하고 pTop이 그 다음 노드를 가리키게 한다. STL의 스택 # STL에서는 선형 구조의 컨테이너를 통해 스택 구조를 이용할 수 있다. (배열 기반도 가능하고, 연결 리스트 기반도 가능하다는 뜻) 연결 리스트 기반 스택의 ADT 1. 스택에 데이터를 넣는다. (Push) 2. 스택에서 데이터를 뺀다. (Pop) 3. 스택 맨 위의 데이..

스택 # 스택이란 먼저 들어온 자료가 마지막에 나오고, 마지막에 들어간 자료가 가장 먼저 나오는 구조를 가진 일종의 리스트이다. # 영어로는 'FILO(First In Last Out)', 'LIFO(Last In First Out)' 구조의 자료구조라고 불린다. # 현실의 쌓여있는 책더미나 동전 지갑, 한쪽만 뚤려있는 통등을 생각하면 이해하기 편하다. # 일반적으로 스택에 가장 나중에 들어온 데이터의 위치를 Top, 가장 처음에 들어온 데이터의 위치를 Bottom이라 한다. # 일반적으로 스택에 데이터를 넣는 행위를 Push, 데이터를 빼는 행위를 Pop, Top의 데이터를 확인하는 행위를 Peek이라 한다. # 스택이 비어있을 때 데이터를 빼려고 하면 Underflow가 발생하고, 스택이 가득 차있을..

이중 원형 연결 리스트 # 이중 원형 연결 리스트는 마지막 노드가 첫번째 노드를 가리키고, 첫번째 노드도 마지막 노드를 가리키게 함으로 원형 구조를 이루게 한 이중 연결 리스트다. # 그러므로 순회시 따로 끝을 지정하지 않는한 무한 루프를 돌게 된다. # 앞에 두개는 처음이나 끝에 도달했는데도 계속 prev나 next를 호출하면 각각 첫 노드나 끝 노드를 계속 반환하도록 했었다. # 앞에 두개에서는 Head포인터와 Tail포인터 두개를 사용했으나 Head포인터 하나로 두 위치를 모두 표시할 수 있다. (Head의 prev가 Tail임으로) # 연결 리스트의 특성상 특정 위치의 노드를 찾기 위해서는 각각의 노드를 거쳐가야 하므로 최악의 경우 size만큼의 노드를 확인해야한다. # 하지만 이중 원형 연결 리..

이중 연결 리스트 # 이중 연결 리스트에서는 이전 노드가 다음 노드의 포인터를, 다음 노드는 이전 노드의 포인터를 가지고 있다. # 그러므로 시작에서만이 아니라 앞에서뿐만 아니라 뒤에서부터도 순회가 가능하다. # 삽입, 삭제 위치에 따른 분류는 이후에 다룰 '스택', '큐', '덱'으로 이루어지므로 이에 자세한 고민은 안했다. # STL에서는 list가 이 구조이다. (즉, 실제로 사용하게 되는건 STL의 ) 단일 연결 리스트의 ADT 1. 원하는 위치에 노드를 추가할 수 있다. 2. 원하는 위치의 노드를 삭제할 수 있다. 3. 원하는 위치의 노드의 값을 수정할 수 있다. 4. 리스트 전체를 양방향으로 순회할 수 있다. 5. 리스트의 전체 노드수를 확인할 수 있다. 6. 리스트가 비어있는 경우는 사용자가..

연결 리스트 # 연결 리스트는 노드가 '데이터'부분과 다음 노드를 가리키는 '링크'부분으로 이루어진 리스트이다. # C/C++에서는 연결 리스트의 링크 부분을 포인터로 구현하며 그렇기에 선형 리스트와는 달리 연속된 메모리 공간을 필요로 하지 않는다는 장점이 있다. # 연결 리스트는 어떻게 연결하느냐에 따라서 '단일 연결 리스트', '이중 연결 리스트', '원형 연결 리스트'등으로 나뉜다. # (Chunked List)라는 것도 있다는 것 같은데 잘 모르겠으므로 생략한다. # 단일 연결 리스트는 이전 노드가 다음 노드를 가리키는 포인터만 가지고 있는 구조이다. 단일 연결 리스트의 ADT 1. 원하는 위치에 노드를 추가할 수 있다. 2. 원하는 위치의 노드를 삭제할 수 있다. 3. 원하는 위치의 노드의 값을..

선형 리스트 # 원소(atom)는 논리적 레코드의 개념으로 그래프 이론에서 사용하는 노드(node)와 동일한 개념이다. # 리스트(List)는 같은 종류의 자료들을 노드 단위로 구성한 집합으로, 항목(item Or field)의 순서 집합으로 볼 수 있다. # 리스트에는 '선형 리스트'와 '연결 리스트'의 두가지가 있다. # 선형 리스트(Linear list)는 다른 말로 연접 리스트(Dense list) 또는 순서 리스트(Ordered list)라고 하며, 노드를 연속되는 기억 장소에 저장한 리스트다. # 선형 리스트는 각각의 노드의 위치를 색인(index) 번호를 사용하여 표시하므로 포인터가 필요 없다. # 이는 배열을 이용해서 구현하기 때문에 STL의 Vector와 비슷하다. # STL에서는 Lis..