본문 바로가기
카테고리 없음

큐(Queue)와 데크(Deque)에 대해서

by kangs' tong 2023. 10. 27.

큐 (Queue)

큐는 데이터를 선입선출 (FIFO: First-In-First-Out) 구조로 관리하는 자료구조입니다. 여러 개의 데이터를 저장할 수 있고, 가장 먼저 저장된 데이터가 가장 먼저 꺼내지게 됩니다. 큐는 일상 생활에서 줄을 서서 기다리는 모습과 유사합니다.

큐의 주요 연산

  1. enqueue: 큐에 데이터를 추가하는 연산입니다. 새로운 데이터는 큐의 맨 뒤에 위치하게 됩니다.
  2. dequeue: 큐에서 데이터를 제거하고 반환하는 연산입니다. 가장 먼저 저장된 데이터가 제거되어 나옵니다.
  3. peek: 큐의 맨 앞에 위치한 데이터를 반환하는 연산입니다. 큐에서 제거하지는 않습니다.

큐의 구현 방법

큐는 배열(Array)이나 연결리스트(Linked List)를 활용하여 구현할 수 있습니다. 배열을 사용한 경우, 크기가 제한된 큐를 만들 수 있지만, 큐의 크기에 따라 배열의 크기를 동적으로 변경해야 하는 불편함이 있습니다. 연결리스트를 사용한 경우, 크기가 제한되지 않으며 동적으로 크기를 관리할 수 있습니다.

데크 (Deque)

데크는 데이터를 양방향에서 삽입과 삭제가 모두 가능한 큐의 한 종류입니다. 데크는 큐와 스택을 합친 형태로 생각할 수 있습니다. 먼저 들어온 데이터를 먼저 꺼내는 것은 큐와 같지만, 양쪽 끝에서 삽입과 삭제가 모두 가능합니다.

데크의 주요 연산

  1. insertFront: 데크의 앞쪽에 데이터를 추가하는 연산입니다.
  2. insertRear: 데크의 뒤쪽에 데이터를 추가하는 연산입니다.
  3. deleteFront: 데크의 앞쪽에서 데이터를 제거하고 반환하는 연산입니다.
  4. deleteRear: 데크의 뒤쪽에서 데이터를 제거하고 반환하는 연산입니다.
  5. peekFront: 데크의 앞쪽에 위치한 데이터를 반환하는 연산입니다. 제거하지는 않습니다.
  6. peekRear: 데크의 뒤쪽에 위치한 데이터를 반환하는 연산입니다. 제거하지는 않습니다.

데크의 구현 방법

데크는 동적 배열을 사용하여 구현할 수 있습니다. 배열의 앞쪽과 뒤쪽에 포인터를 설정하여 데이터를 삽입하고 삭제하는 연산을 수행합니다.

정리

큐는 선입선출 (FIFO) 구조로 데이터를 관리하는 자료구조이고, enqueue, dequeue, peek 연산을 지원합니다. 큐는 배열 또는 연결리스트를 사용하여 구현할 수 있습니다.

데크는 양방향에서 삽입과 삭제가 가능한 큐로, insertFront, insertRear, deleteFront, deleteRear, peekFront, peekRear 연산을 지원합니다. 데크는 동적 배열을 사용하여 구현할 수 있습니다. Both queues and deques are important data structures in computer science and have various applications in solving problems efficiently.

댓글