[CㆍC++로 배우는 자료구조론] 07 큐 연습문제

1.

다.

2.

나.

3.

나.

4.

나.

6.

false 근데 사실 이는 노드도 마찬가지이다.

9. 

가.

A

B D F

C E G I K

J H C

나.

B 

A C G K

D F J H

E I

10.

A G H I

A G E F

A G B D C (또는 A G B C D )

A

B G

C D E H

F I

11.

p = new node;

p->Next = BackPtr->Next;

p->Item = 3;

BackPtr->Next->Next->Next = p;

BackPtr = p;

12.

큐에 삽입할때에 Rear를 증가시키고,

큐에서 제거할때 Front 를 증가하여 제거하기 때문이다.

원형배열과 같이 사용하면 된다.

13.

첫번째 노드의 위치를 1로 가정

가.

void QueueClass::QueueAdd(int Newitem, boolean &Success)

{

if( L.ListIsFull() )

{

cout << "Queue Is FULL" << endl;

Success = false;

}

else

{

L.ListInsert( L.Length()+1, Newitem, Success );

if( Success == false )

return;

Success = true;

}

}

나.

void StackClass::~StackClass()

{

while( !( L.ListIsEmpty) )

{

boolean Suc;

L.ListDelete( L.ListLength(), Suc );

if( Suc == false )

{ 

cout << "Something is Wrong" << endl;

return;

}

else

}

}

16. void queueClass::Return_Front()

{

if( Rear == NULL )

return;           //빈 큐일 경우

else

{

return Rear->Next;        // 큐에 한개 이상의 자료가 있을경우 Rear는 Null값을 가지지 않는다. Rear->Next 가 Null값을 가질 순 있지만.

}

}

17. 배열로 구현한 큐의 경우 삽입시 Rear를, 삭제시 Front를 증가시키는 것으로 구현했다고 가정했을때,

큐가 생성되어서 맨처음삽입이 되어있을 경우 외에는 Front의 인덱스값은 0이 아닐 수 있다.

왜냐하면 한번이라도 삽입, 삭제가 되어 자료가 한개가 남개되면 무조건 Rear와 Front의 값이 증가하기 때문.

18.

가.

queueClass()

{

L.size = 0;

L.Head = NULL;

}    

나.

~queueClass()

{

while( !L.IsEmpty() )

L.Delete( L.length() );

}

다.

bool queueClass::IsEmpty()

{

if ( L.IsEmpty() )

return true;

else

return false;

}

라.

bool queueClass::IsFull()

{

Nptr p = new node;

if( p == NULL )

return true;

else

{

delete p;

return false;

}

}

20.

 H

 T

 0  1  2  3

'a'

 

 H  T

 0  1  2  3

'a' 'b' 

 H     T

 0  1  2  3

'a' 'b' 'c'

//remove 1

     H  T

 0  1  2  3

    'b' 'c' 

//remove 2

        H

   T

 0  1  2  3

        'c' 

        H   T 

 0  1  2    3

        'c'  'd' 

 T      H    

 0  1  2    3

'e'     'c'  'd'

remove 두번 후

 H

 T          

 0  1  2    3

'e'   

21. 

 0   1   2   3   4   5

 A   B  C

 0   1   2   3   4   5

      B  C

 0   1   2   3   4   5

          C

 

//Add(D), Add(E)

 0   1   2   3   4   5

          C   D  E

 0   1   2   3   4   5

               D  E

//Add(A), Add(B)

 0   1   2   3   4   5

 B             D  E   A

 

//Remove() x2

 0   1   2   3   4   5

 B                     A