보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.

Presentation on theme: "보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라."— Presentation transcript:

1 보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
큐의 연산, is_empty(q), is_full(q), enqueue(q, item), dequeue(q)에 대한 알고리즘을 각각 작성하라. 여기서 q는 큐이고, item은 데이터 항목이다. 다음의 큐 연산을 수행하는 main() 함수를 작성하고, 여러분이 구현한 큐가 올바르게 동작하는지를 테스트 및 검증하라. enqueue(q, 1) enqueue(q, 2) enqueue(q, 3) print(dequeue(q)) enqueue(q,4) enqueue(q,5) enqueue(q,6)

2 Sol - #1 void enqueue(q, item) push(stk1, item) END enqueue
element dequeue(q) if is_empty(stk2) then while !is_empty(stk1) do push(stk2, pop(stk1)); repeat end if if !is_empty(stk2) then return pop(stk2); END dequeue

3 보고서 #7 (2) 원형 큐에서는 공백 상태와 포화 상태를 구분하기 위하여 필수적으로 하나의 빈 공간이 필요하다. 그러나 하나의 변수, lastOp를 큐에 추가하여 모든 공간을 사용할 수 있다. lastOp의 변수는 가장 최근에 큐에 행해진 연산을 기억한다. 최근에 행해진 연산이 삽입 연산이었다면 큐는 공백 상태가 아닐 것이다. 즉, lastOp의 변수를 이용하여 front == rear 일 때, 공백상태와 포화상태를 구분할 수 있다. 마찬가지로, 최근에 행해진 연산이 삭제 연산이었다면 큐는 포화상태가 아닐 것이다. 큐의 연산, is_empty(q), is_full(q), enqueue(q, item), dequeue(q)에 대한 알고리즘을 각각 작성하라. 여기서 q는 큐이고, item은 데이터 항목이다. 크기가 5인 원형 큐를 정의하고, 앞의 문제에서 제시한 일련의 큐 연산을 수행하는 main() 함수를 작성하고, 여러분이 구현한 큐가 올바르게 동작하는지를 테스트 및 검증하라.

4 Sol - #2 // IN, OUT 상수 도입 // IN은 삽입 연산, OUT은 삭제 연산 의미
is_empty(q) if front = rear and lastOP = OUT then return true; else return false; end if end is_empty is_full(q) if front = rear and lastOP = IN then end is_full enqueue (q, item) …. lastOP <- IN // 삽입 연산 수행 end enqueue dequeue (q) lastOP <- OUT // 삭제 연산 수행 end dequeuer