큐의 구조와 특징
큐(Queue)란?
줄 서는 것처럼 순서대로 처리되는 자료구조
그림과 같이 앞(front)과 뒤(rear)가 있고 먼저 들어온 데이터가 먼저 나가는 First In First Out(FIFO)(선입선출)을 따르게됩니다.
큐에 데이터를 추가하는 것을 Enqueue, 데이터를 삭제하는 것을 Dequeue라고 표현합니다.
앞인 front에서는 삭제 연산만 수행하고 뒤인 rear에서는 삽입 연산만 수행하는 특징을 갖고 있습니다.
큐의 관련 메서드
| 메서드 | 메서드의 기능 | 시간복잡도 |
| add(Object obj) | queue에 데이터 obj값을 넣는다. queue가 가득 찼을 경우 에러 반환 () |
O(1) |
| offer(Object obj) | queue에 데이터 obj값을 넣는다. queue가 가득 찼을 경우 false 반환 queue에 데이터를 넣었을 경우 true 반환 |
O(1) |
| remove() | queue에 가장 먼저 넣었던 데이터를 제거한다. queue에 아무것도 없을 경우 에러 반환 |
O(1) |
| poll() | queue에 가장 먼저 넣었던 데이터를 제거한다. queue에 아무것도 없을 경우 null 반환 |
O(1) |
| element() | queue에 가장 먼저 넣었던 데이터를 조회한다. queue에 아무것도 없을 경우 에러 반환 |
O(n) |
| peek() | queue에서 가장 먼저 넣었던 데이터 조회한다. queue에 아무것도 없을 경우 null 반환 |
O(n) |
-> 시간복잡도는 사실 queue를 어떤 datastruct를 쓰느냐에 따라 달라진다. 이건 간단하게 적어놓은 것이므로 데이터 구조에 따라 확인을 다시 해봐야한다.
큐의 삽입
큐의 삭제
큐의 조회
poll()전에 peek()으로 먼저 들어온 데이터를 조회하면 3이 출력되고,
poll()후에 peek()으로 먼저 들어온 데이터를 조회하면 1이 출력된다.
큐의 구현 : 배열, 연결리스트
마찬가지로 배열과 연결리스트를 이용합니다.
참고할 만한 문제 :
https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
https://school.programmers.co.kr/learn/courses/30/lessons/42586
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'자료구조 & 알고리즘 > 선형 자료구조' 카테고리의 다른 글
| [자료 구조] 연결리스트(LinkedList) in java (2) | 2023.06.16 |
|---|---|
| [자료 구조] 배열 (Array) in java (0) | 2023.06.14 |
| [자료 구조] 스택 (Stack) in java (0) | 2023.06.12 |
