데크(Deque)

데크(Deque)

• 양쪽에서 삽입과 삭제가 모두 가능한 자료구조
• Deque : Doubly-ended Queue
• Stack과 Queue를 합친 형

데크 기본 구조

• 데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조

• 일부 기능을 제한하여 용도에 맞게 변형 가능

• add/ remove는 Exception을 발생시키지만, offer/poll은 false와null을 return한다.

입력제한 데크(Scroll)

• 한 쪽의 입력을 제한한 데크

출력제한 데크(Shelf)

• 한 쪽의 출력을 제한한 데크

데크 선언/할당

Deque deque = new ArrayDeque();

배열의 원 큐/데크

int[] arr;
int front = 0 ;
int rear = 0 ;

// 데이터 추가 및 삭제 시 배열의 front, rear움직임


// 배열의 front--> 이동 시
// queue의 poll / deque의 removeFirst
this.front = (this.front + 1) % this.arr.length;

// 배열의 rear--> 이동 시
// queue의 add / deque의 addLast
this.rear = (this.rear + 1) % this.arr.length;

// 배열의 front <-- 이동 시
// deque의 addFirst
this.front = (this.front - 1 + this.arr.length) % this.arr.length;

// 배열의 rear <-- 이동 시
// deque의 removeLast
this.rear = (this.rear - 1 + this.arr.length) % this.arr.lenght;

//배열 출력
int start = (this.start + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for(int i = start; i != end; i = (i+1) % this.arr.length){
		System.out.print(arr[i] + " ");
	}
System.out.println();

기본 연산