Algorithm | 자료구조 : Queue & Deque

Queue?

 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

Queue의 구조

 

Queue Method

· add() : 리스트의 끝 부분에 새로운 요소를 추가한다.

· remove() : 리스트의 첫 번째 항목을 제거한다.

· peek() : 큐에서 가장 위에 있는 항목을 반환한다.

· isEmpty() : 큐가 비어 있을 때에 true를 반환한다.

 

Queue Code(JAVA)

import java.util.ArrayList;
import java.util.List;

class MyQueue {
  private List<Object> que = new ArrayList<Object>();

  public void add(Object item) {
    que.add(item);
  }

  public Object remove() {
    int length = que.size();
    if(length == 0) {
      return null;
    }
    
    return que.remove(0);
  }

  public Object peek() {
    int length = que.size();
    if(length == 0) {
      return null;
    }

    return que.get(length - 1);
  }
  
  public boolean isEmpty() {
    if(que.size() == 0) {
      return true;
    }

    return false;
  }

}

Queue Library (JAVA)

 클래스로 구현된 스택과는 달리 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다. 이러한 Queue 인터페이스를 상속받는 하위 인터페이스는 Deque<E>, BlockingDeque<E>, BlockingQueue<E>, TransferQueue<E>가 있다. 이 중 Deque 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는데 가장 많이 사용된다.

 

Deque<Integer> qu = new ArrayDeque<Integer>();

 

Deque?

 덱(deque)은 Double-ended Queue의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조의 한 형태이다. 두 개의 포인터를 사용하여 양쪽에서 삽입과 삭제를 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

 

Deque의 구조

Deque Method

· push_front() : 맨 앞에 새로운 요소를 삽입한다.

· push_back() : 맨 뒤에 새로운 요소를 삽입한다.

· pop_front() : 맨 앞에 요소를 제거한다.

· pop_back() : 맨 뒤에 요소를 제거한다.

· front() : 맨 앞에 있는 요소를 반환한다.

· back() : 맨 뒤의 있는 요소를 반환한다.

· isEmpty() : 덱이 비었으면 true를 반환한다.

---

Reference

· https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html

· http://tcpschool.com/java/java_collectionFramework_stackQueue