목록자료구조 (13)
Binaryseop
1. 연결 큐 순차 자료구조 방식을 이용한 선형 큐(Linear Queue)와 원형 큐(Circular Queue)는 몇 가지 문제가 있습니다. 첫 째, 사용 크기가 제한되어 큐의 길이를 마음대로 변경할 수 없습니다. 둘 째, 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리 낭비가 있습니다. 이와 같은 문제를 해결하기 위해 연결 자료구조 방식을 이용하여 크기가 제한없는 연결 큐(Linked Queue)를 사용합니다. 2. 연결 큐 알고리즘 연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째 노드를 가리키는 참조변수 front와 마지막 노드를 가리키는 참조변수 rear를 사용합니다. · 연결 큐 생성 createLinkedQueue() front ← null;..
1. 원형 큐 1차원 배열을 사용한 순차 자료구조 방식에서는 큐가 포화 상태가 아닐 경우에만 삽입 연산을 할 수 있었습니다. 하지만 앞에 빈자리가 있음에도 불구하고 rear가 배열의 마지막 인덱스와 값이 같다면 포화 상태로 인식하여 삽입 연산을 수행하지 못하였습니다. 이를 잘못된 포화상태라고 부릅니다. 이런 경우에 큐의 빈자리를 사용하기 위해 저장되어 있는 원소를 배열의 앞부분으로 이동시켜 위치를 조정해 줘도 되지만 이는 큐의 효율성을 떨어트립니다. 따라서 이러한 선형 큐의 잘못된 포화상태 문제를 해결하기 위해 원형 큐를 사용합니다. 원형 큐는 선형 큐와 마찬가지로 1차원 배열로 구현하지만, 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 생각하는 것입니다. 2. 원형 큐 알고리즘 원형 큐에서는 배열..
1. 큐(Queue) 일상생활에서 은행에 들어온 순서대로 번호표를 뽑고 번호표 순서대로 먼저 온 고객부터 처리해 주는 것과 같이 선입선출 형태의 구조를 큐(Queue)라고 부릅니다. 큐는 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한되어 있는 자료구조이지만 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어지는 자료구조입니다. 2. 큐의 특징 1) 데이터가 삽입된 순서대로 삭제되는 선입선출(FIFO, First-In-First-Out) 구조입니다. 2) 한쪽 끝을 front로 정하여 삭제 연산만 수행하도록 하고 다른 쪽 끝은 rear로 정하여 삽입 연산만 수행하도록 제한하여 만든 자료구조입니다. front 원소는 가장 먼저 큐에 들어온 첫 번째 원소이고, 리어 원소는 가장 늦게..
순차 자료구조를 이용한 스택은 배열을 사용하여 구현하기 쉽지만, 물리적으로 크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고 메모리의 낭비가 생길 수 있다는 문제점이 있습니다. 이러한 순차 자료구조 방식의 문제는 연결 자료구조 방식을 이용함으로써 해결할 수 있습니다. 1. 연결 리스트로 구현하는 스택 알고리즘 · 삽입 연산(push) push(lS, x) new ← getNode(); new.data ← x; new.link ← top;// ① top ← new;// ② end push() ① 새로 삽입할 new 노드의 link에 top을 저장하여 이전 노드를 참조하게 합니다. ② top은 새로 삽입된 new 노드를 참조하게 합니다. · 삭제 연산(pop) pop(S) if(top =..