[묘공단] 코딩 테스트 합격자 되기 3주차

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다.

 

 

1. 큐

1) 개념

큐는 줄을 서다 라는 뜻을 가지고 있다

선입 선출 즉, 먼저 들어간 데이터가 먼저 나오는 자료구조 이다

 

- FIFO

- 삽입하는 연산은 Enqueue, 꺼내는 연산을 Dequeue 라고 한다

- 큐의 동작방식은 작업 대기열, 이벤트 처리 등등 많이 활용한다

 

2) 과정

 

1. 빈 큐 하나 선언

Queue<Integer> queue = new LinkedList()<>;

 

2. 데이터 삽입 

queue.add(3);
queue.add(2);
queue.add(4);
queue.add(1);

 

-삽입을 하면 3부터 순서대로 삽입을 한다.

- 위 코드 처럼 순서는 3, 2, 4, 1 이 되겠다

 

3. 데이터 삭제

queue.poll();

 

- 위 코드 처럼 poll() 메서드를 하면 3이 삭제가 된다

 

3) 큐의 ADT 정의 및 동작 원리

 

 

 

동작 과정

 

add(3) 연산 수행 할 때

 

1. isFull()로 큐가 가득 차 있는지 확인

2. isFull()이 false 이면 rear을 +1 하여 rear가 가리키는 위치에 data[0] 에 3을 추가한다

3. isFull()이 true 이면 데이터를 add() 하지 않는다

 

 

4) 사용하기

 

- 일반적인 코딩 테스트에서 LinkedList 보다는 ArrayDeque를 더 많이 사용하므로 구현체를 ArrayDeque를 사용하겠다

//큐를 구현한 ArrayDeque 객체 생성
Queue<Integer> queue = new ArrayDque<>();

//큐에 데이터 추가
queue.add(1);
queue.add(2);
queue.add(3);

//큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.poll();
System.out.println(first); //1

//큐에 데이터 추가
queue.add(4);
queue.add(5);

//큐의 맨 앞 데이터를 제거하면서 반환
first = queue.poll();
System.out.println(first) //2

 

- Deque를 큐처럼 활용하기

ArrayDeque<Intger> = new ArraryDeque<>();

//큐에 데이터 추가
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);

//큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.pollFirst();
System.out.println(first); //1

//큐에 데이터 추가
queue.addLast(3);
queue.addLast(4);

//큐의 맨 앞 데이터를 제거하면서 반환
first = queue.pollFirst();
System.out.println(first); //2

 

 

- 또 Deque를 push() 와 pop()만으로 스택 처럼 활용할 수 있다

 

 

정리를 하자면 Deque는 큐, 스택을 둘다 활용할 수 있다

 

 

 

 

 

출처

 

https://goldenrabbit.co.kr/product/javapass/

[되기] 코딩 테스트 합격자 되기(자바 편) - 골든래빗