이진트리의 레벨 순회 레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법입니다. 중위, 후위, 전위 순회가 스택을 사용했던 것에 비해 레벨 순회는 선입선출 기반의 큐를 사용하는 순회 법입니다. 위의 이진트리를 레벨 순회해보겠습니다. "만나는 노드를 꺼내서 출력하고 서브트리를 왼쪽부터 큐에 넣는다" 만 기억하면 됩니다. 먼저 루트를 방문하여 +를 큐에 넣습니다. 큐 : | + | +를 꺼내서 출력하고 서브트리인 *와 /를 큐에 넣습니다. 큐 : | * | / | *를 꺼내서 출력하고 서브트리인 A와 B를 큐에 넣습니다. 큐 : | / | A | B | /를 꺼내서 출력하고 서브트리인 C와 D를 큐에 넣습니다. 큐 : | A | B | C | D | A를 꺼내서 출력하고 큐에 넣을 서브트리는 없습니다. ..

덱 Deque(Double-ended-queue) 덱(deque)은 double-ended queue의 줄임말로써 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐입니다. 덱에 사용되는 Abstract Data Type ▪ create() ::= 덱을 생성한다. ▪ init(dq) ::= 덱을 초기화한다. ▪ is_empty(dq) ::= 덱이 공백상태인지를 검사한다. ▪ is_full(dq) ::= 덱이 포화상태인지를 검사한다. ▪ add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. ▪ add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. ▪ delete_front(dq) ::= 덱..

큐 Queue 나중에 들어온 데이터가 먼저 나가는 스택 자료구조와 달리 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 선입선출(FIFO: First-In First-Out) 큐를 사용하는 방식에는 선형 큐, 원형 큐, 덱이 있습니다. 선형 큐 배열을 선형으로 사용하여 구현된 큐이며, 삽입을 계속하기 위해서는 요소들을 이동시켜야 합니다. 데이터를 넣을때마다 번거로움이 있다는 문제점이 있는 방식입니다. 또한 인덱스를 감소하지는 않고 증가만 하면서 사용하는 방식이기에, 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없기 때문에 비효율적인 부분이 있습니다. #include #include #define MAX_QUEUE_SIZE 5 typedef int element; typedef..