UpWrite

큐 # 큐는 영어로 줄이나 대기 행렬을 의미하는 단어로, 먼저 들어온 데이터가 먼저 빠져나가는 구조의 리스트이다. # 영어로는 '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..

추상 자료형 # 추상 자료형은 '사용자 관점'과 '구현자 관점'에서 생각할 수 있다. # '사용자 관점'에서의 추상 자료형은 '구체적인 기능의 완성과정은 언급하지 않고, 순수하게 어떤 기능이 있는지만 나열한 것'이다. # '구현자 관점'에서의 추상 자료형은 '작업을 수행하기 위한 구체적인 방법과 그 방법을 적용하기 위한 데이터 집합'을 의미한다. # 사용자 관점에서 추상 자료형을 설계할 때는 '일반적인 경우의 작업만 설계한다'는 '일반성(Generality)'의 원칙을 지켜서, '범용성(General Usability)'을 높여야 한다. # 구현자 관점에서 추상 자료형을 구현할 때는 기능이 사용자가 생각한대로 작동할 수 있도록 하는데에 초점을 맞추면 된다. # 이 때, 사용자는 구현자가 내부적으로 어떤식..

1. 배열 # 배열은 크기와 성격이 같은 자료형을 연속된 기억장소에 저장한 것이다. # 배열 구조는 선형 리스트(linear list) 또는 순서 리스트(ordered list)를 표현하는 가장 일반적인 형태이다. # 일반적으로 배열은 배열명(Array name)으로 식별되고, 배열의 요소(원소)는 배열명에 괄호를 붙여 그 안의 첨자(subscript Or index)로 식별한다. # 1차원 배열 (One-dimensional Array Or vector) A는 A(L:U)로 표시할 수 있다. # 이 때, L은 배열 첨자의 하한 값으로 배열의 시작 값을 의미하고, U는 상한 값으로 배열의 마지막 값을 의미한다. # 1차원 배열의 길이는 배열을 구성하는 배열 원소의 개수로 A(L:U)의 길이는 U-L+1이..

1. 자료와 자료구조 # 자료(data)는 현실 세계로부터 단순한 관찰이나 측정을 통해서 수집한 사실(fact)들 또는 값(value)들이다. # 자료는 가공되지 않은 상태를 의미하고, 정보(infomation)는 어떤 기준에 의해 정리되고 기록된 것을 의미한다. # 자료구조(data structure)는 자료 개체(data object)의 집합, 자료 값 사이의 관계 그리고 자료에 적용 가능한 함수 또는 연산 등을 의미한다. # 프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다. # 데이터의 표현은 데이터의 저장을 포함하고, 데어터의 저장을 담당하는 것이 자료구조이다. 2. 자료의 구성 (각각에 대한 설명은 생략) 비트(bit), 바이트(byte), 단어(word), 항목(item..