과제4-스택, 큐, 덱...

1. 덱은 스택의 기능과 큐의 기능을 모두 합니다. 그렇다면 왜 덱을 쓰지 않고 스택과 큐를 쓸까요?

ANS: 스택은 last in first out, 후입선출 구조로 가장 마지막에 들어간 데이터가 가장 먼저 나오며 삽입, 삭제가 동일한 곳에서 일어난다는 특징이 있다. top을 스택에 데이터(요소)를 넣는 인덱스라 하면, top=-1로 시작한다면,

삽입: 데이터 요소를 삽입할때마다 top+1을 하게 된다.

삭제:데이터 요소를 삭제할때마다 top-1을 하게 된다.

 

한편, 큐는 first in first out, 선입선출 구조로 가장 먼저 들어간 데이터가 가장 먼저 나오며 삽입과 삭제가 다른 곳에서 일어난다.(흔히 배열로 구현한 선형 큐에서는 앞을 front, 뒤를 rear인덱스로 삼는다)

삽입: 요소를 뒤에서 삽입하므로 rear=rear+1

삭제: 요소를 앞에서 삭제하므로 front=front+1로 위치 인덱스를 바꾸고 데이터 삭제함

 

덱(double ended queue)의 특징: 큐의 front, rear에서 모두 삽입 삭제 연산이 가능한 큐를 의미. 상당히 스택이나 큐에 비해 삽입, 삭제의 자유도는 높지만 여전히 중간 인덱스 위치에 요소를 삽입하거나 삭제하는 것을 허용하지 않고 자료의 순서가 복잡하게 바뀔 수도 있어서 순서(인덱스 등)이 정말 중요한 자료형이 있어야 한다면 덱보다는 스택이나 큐를 사용하는 편이다.

 

2. (연습문제6)큐에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 될까요? 

ANS: 원형큐에서의 삽입 알고리즘, 원형큐에서의 삭제 알고리즘을 살펴보면,

enqueue(x)

rear ← (rear+1) mod MAX_QUEUE_SIZE; //index

data[rear] ← x;

 

dequeue()

front ← (front+1) mod MAX_QUEUE_SIZE; //index

return data[front];

따라서 rear나 front에서 mod계산을 각각 수행한 후,data[rear]나 data[front]에 그 값을 대입하므로 O(1) 시간 복잡도 함수라고 할 수 있을 것 같다.