큐(Queue) / 덱(Deque)

1.  큐(Queue)

한쪽 끝에서만 자료를 넣고, 다른한쪽 끝에서만 뺄수있는 자료구조
FIFO(First In Firtst Out) 선입선출 형식이다.

 

<이미지 출처 : https://blog.naver.com/coolten/140057846054>

 

일차원 배열 하나로 구현가능하다.

int queue[1000];
int begin = 0;
int end = 0;
//begin ~ end-1 까지 포함

 

큐도 라이브러리가 제공되고 있다. 

-> 각 O(1) 의 시간복잡도는 갖는다

 

- C++

    push    큐에 자료넣는 연산 
    pop     큐에서 자료를 빼는 연산 
    front    가장 앞에 있는 자료를 보는 연산 
    back    가장 뒤에 있는 자료는 보는 연산 
    empty  큐가 비어있는지 아닌지 확인 
    size     큐에 저장되어있는 자료의 개수 알아보기

 

- Java

   add()       큐에 자료넣는 연산  

   remove()  큐에서 자료를 빼는 연산  

   peek()     가장 앞에 있는 자료를 보는 연산   

   isEmpty() 큐가 비어있는지 아닌지 확인 

   size()      큐에 저장되어있는 자료의 개수 알아보기

 

void push(int data){
	queue[end] = data;
	ent += 1;
}

void pop(int data){
	queue[begin] = data;
	begin -= 1;
}

void empty() {
	if (start == end) return true;
	else return false;
}

int size() {
	return end-begin
}

 

•  조세퍼스 순열

              1번부터 N번까지 N명의 사람들이 둘러앉아있다.

              원을따라 순서대로 M 명씩 제거한다. 

              이과정을 N명의 사람이 제거될때까지 반복한다.

               ex) N = 7, M = 3일때

 

(큐로 안풀어도 되는문제이고 별로 중요하지 않다ㅎ)

큐는 BFS에서 정말 중요한 역활을 하기때문에 다음글에 자세히 다루어보겠다.

 

 

2.  덱 (Deque)

양 끝에서 자료를 넣고, 양 끝에서 자료를 뺄 수 있는 구조

Double Ended Qieir의 약자이다.

덱은 정말 중요한 자료구조이다. 왜냐하면 연산에 따라 스택이 될 수 있고, 큐가 될 수도 있다.

덱을 구현하였다면 스택과 큐를 모두 구현하였다고 보아도 된다.

덱 (Deque)

 

 

덱의 성질만 사용하여 푸는 문제는 거의 없다.

덱 또한 BFS에서 정말 중요한 역활을 하기 때문에 다음글에서 자세히 다루어보겠다.

 

 

 

---

 

<참고>

백준사이트

gorani95.tistory.com/150