[JAVA/자료구조] DEQUE 데크 (양방향 큐)

Deque

• Queue와 Stack의 성질을 둘다 가지고 있다.
• Stack : push / pop / peek - 제일 늦게 들어간 것이 제일 먼저 나온다.
• Queue : offer / poll / peek - 제일 먼저 들어간 것이 제일 먼저 나온다.
• Deque : offerFirst, offerLast 등 : 양방향

---

Deque의 특징

Deque는 흔히 Stack과 Queue의 특징을 둘 다 갖고 있다고 한다.

 

Queue는 선입선출의 구조를 가지고있다.

Deque에서 offerLast로 값을 넣고, pollFirst로 값을 꺼내면 뒤(왼쪽)로 값을 넣고, 앞(오른쪽)에서 꺼내는 Queue와 같다.

또한, offerFirst로 값을 넣고, pollLast로 값을 꺼내면 위와 반대로 앞으로 값을 넣고, 뒤에서 꺼내는 Queue와 같다.

 

Stack은 후입 선출의 구조를 가지고 있다.

offerLast, pollLast만 사용하면 뒤에서 값을 넣는 Stack를 구조를, offerFirst,pollFirst만 사용하면 앞으로 값을 넣는 Stack의 구조와 같아진다.

 

이 두가지 특성을 혼합하여 사용하여 Queue, Stack으로 해결하기 어려운 문제를 해결할 수  있다.

---

변수 선언

Deque<Integer> deque = new LinkedList<>();

---

데이터 처리

offerFirst() / offerLast() 

각각 앞, 뒤에 값을 넣는다.

deque.offerFirst(1);//[1]
deque.offerFirst(2);//[2,1]
deque.offerFirst(3);//[3,2,1]
deque.offerFirst(4);//[4,3,2,1]
deque.offerLast(5);//[4,3,2,1,5]
deque.offerLast(6);//[4,3,2,1,5,6]

pollFirst() / pollLast() 

각각 앞, 뒤의 값을 꺼냄

//[4,3,2,1,5,6]
deque.pollFirst();// 4 반환, [3,2,1,5,6]
deque.pollLast();// 6 반환, [3,2,1,5]
deque.pollFirst();// 3 반환, [2,1,5]
deque.pollLast();// 5 반환, [2,1]

peekFirst() / peekLast()

각각 다음에 꺼낼 앞, 뒤의 값을 조회

//[4,3,2,1,5,6]
deque.peekFirst(); //4 반환 , [4,3,2,1,5,6](그대로)
deque.peekLast(); //6 반환 , [4,3,2,1,5,6](그대로)
deque.peekFirst(); //4 반환 , [4,3,2,1,5,6](그대로)
deque.peekLast(); //6 반환 , [4,3,2,1,5,6](그대로)