선형 큐

• 구현간단 but 메모리 단편화 문제.

원형 큐

• 메모리 효율적. but 구현 복잡

배열 원형 큐

초기상태 : front = rear = 0

삽입 삭제

enqueue

• rear = (rear+1) % 큐 사이즈
• rear 자리에 삽입

dequeue

• front = (front+1) % 큐 사이즈
• front 자리에 삭제

peek

• (front+1) % 큐 사이즈 반환

display

max = (front< rear) ? rear : rear+ 큐사이즈 
for i = front+1 ~ <=max :
	data[i % 큐사이즈]
    
// rear 가 더 크면 그냥. 작으면 rear + 큐사이즈

연결리스트 큐

• 메모리 단편화 문제 해결. 동적으로 메모리 할당 가능.

공백상태 삽입

• front rear 새로운 노드 p 가리킴

비공백 삽입

• 1. rear -> link =p; 2. rear=p;

노드 두개이상일때 삭제

• 1. p = front; 2. front = p->link;

노드 하나일때 삭제

• 1. front =rear =NULL

enqueue

// isEmpty() 확인 후 비었으면
front = rear = n; (Node* n 임)

// 있으면, 
rear -> setLink(n); // setLink(Node* next) {link = next;}
rear=n;

dequeue

// isEmpty() 확인후 비었으면 
return NULL;

// 있으면, 임시 노드 만들고
Node* temp = front;
front = front->getLink();
if (front == NULL)
rear = NULL;

return temp;

peek

-front 반환

display

for(Node* p = front; p!=NULL; p=p->getLink())
p->display()

덱

배열 덱

addFront()

• data[front] = val; front 는 항상 비어있으니 바로 삽입.
• front = (front-1+ 큐사이즈)%큐사이즈 // front -1

deleteRear()

• int ret = data[rear] //rear 항상 차있으니 바로 데이터 받기.
• rear = (rear-1+큐사이즈) % 큐사이즈; // rear-1

getRear()

• return data[rear]

display

• 기존 원형 큐와 동일. front+1 ~ <=max

이중 연결리스트 덱

Node 코드

insertNext

if (n != nullptr){
  n-> prev =this;
  n-> next =next;
  if( next !=nullptr) 
  next-> prev = n;
}

remove()

• 이전꺼의 다음에 = next;
• 다음꺼의 이전에 = prev;

if(prev != nullptr) prev->next = next; 
if(next != nullptr) next -> prev = prev;
return this;

덱

getEntry

for(i = -1; i<pos; n= n->getNext())
	if(n == nullptr) break;
  return n;

insert

Node2 *prev = getEntry(pos - 1);
if(prev != nullptr)
	prev -> insertNext(n);