개발일지/컴퓨터지식
자료구조 Deque
E-room
2022. 9. 28. 16:54
728x90
Deque (Double Ended Queue, 양방향 대기열)
Deque는 Stack과 Queue의 특성들이 혼합된 느낌이다
- Stack : 데이터가 한 방향으로 추가되고 삭제할 수 있음
- Queue : 데이터가 한방향으로 추가되고 다른 방향으로 데이터가 삭제됨
자료구조 스택 Stack
Stack 데이터를 순서대로 쌓는 자료구조 가장 먼저 들어간 데이터가 가장 나중에 나올 수 있다 그림과 같이 길이 막혀 더 이상 진행할 수 없는 경우 분홍색 자동차가 가장 먼저 들어왔지만 뒤 차
e-room.tistory.com
자료구조 큐 Queue
큐는 줄을 서서 기다리다, 대기행렬이라는 뜻이 있다 가장 먼저 들어온 데이터가 먼저 나갈 수 있다 고속도로 톨게이트는 가장 먼저 도착한 자동차가 먼저 통과할 수 있다 분홍색 자동차가 가장
e-room.tistory.com
양방향으로 열려있는 구조로, Queue와 외형적으로 비슷하다
하지만 Deque는 Stack, Queue와 달리 LIFO, FIFO 같은 순서에 얽매이지 않는다
Deque의 특징
1. Stack과 Queue를 모두 사용할 수 있음
- 추가를 제한하는 구조
한쪽에서만 데이터 추가가 가능하고 삭제는 양방향에서 가능하게 구현한다면 아래와 같은 구조가 된다
왼쪽에서 삭제하면 Stack과 같고 오른쪽으로 삭제하면 Queue와 같다
- 삭제를 제한하는 구조
데이터 추가는 양쪽에서 가능하지만, 삭제는 한 방향만 가능하게 구현한다면
왼쪽에서 데이터를 추가하면 Stack과 같고 오른쪽에서 추가하면 Queue와 같아진다
2. 양방향 끝에서 데이터 추가, 삭제가 용이함
3. 양방향 끝이 아닌 임의의 인덱스값으로 추가 삭제가 불가능
- 양쪽 끝을 제외한 인덱스 정보를 갖고 있지 않다
728x90