[코딩테스트] 큐

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

큐(Queue)

• 순서가 있는 자료구조, 한쪽의 끝에서만 넣을 수 있고(push) 다른 한쪽 끝에서만 뺄 수 있음(pop)

• 먼저 넣은 게 가장 먼저 나오기 때문에 First In First Out(FIFO)라고 함

  push : 큐에 자료를 넣는 연산
  pop : 큐에서 자료를 빼는 연산
  front : 큐의 가장 앞에 있는 자료를 보는 연산
  back : 큐의 가장 뒤에 있는 자료를 보는 연산
  empty : 큐가 비어있는지 아닌지를 알아보는 연산
  size : 큐에 저장되어 있는 자료의 개수를 알아보는 연산

• Java의 경우 java.util.Quene
• 각 연산을 복잡도 O(1)만에 구현해야 한다.
  • 배열
  • 링크드 리스트
• 일차원 배열 하나로 구현 가능, begin / end 변수를 사용해서. begin - (end-1)까지가 큐에 들어있는 자료임.

package practice;

import java.util.Scanner;

public class Main {
	static int[] queue;
	static int begin;
	static int end;
	public static void main(String[] args) {
		queue = new int[10000];
		begin = 0;
		end = 0;
	}

	public void push(int data) {
		queue[end] = data;
		end += 1;
	}

	public void pop(int data) {
		queue[begin] = 0;
		begin += 1;
	}

	public boolean empty() {
		if (begin==end) return true;
		else return false;
	}

	public int size() {
		return end-begin;
	}

	public int front() {
		return queue[begin];
	}

	public int back() {
		return queue[end];
	}
}

• 큐 구현 문제 10845번
• pop을 한다고 실제 데이터를 지우면 안 됨. java의 경우 ArrayList로 큐를 절대 구현하면 안 된다. pop연산의 경우 0번째를 지워버리면 모든 값들이 앞으로 한 칸씩 이동함. 그럼 O(N)이 걸리게 되어서 안됨!
• 따라서 큐를 직접 구현할 땐 배열이나 링크드리스트를 이용해서 하자. 배열의 경우엔 배열 크기를 정해줘야 한다. 크기는 문제에 나와있으니 그 값을 써주면 된다.
• 문제 푸는 게 아니라 공간 효율적인 큐를 구현해야 한다면 링크드리스트로 구현. 그게 아니라면 언어에 있는걸 활용.
• 큐를 가장 많이 활용하는 알고리즘은 그래프 알고리즘 중 bfs이다.

덱(Deque)

• 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조
• Double-ended queue

  push_front : 덱의 앞에 자료를 넣는 연산
  push_back : 덱의 뒤에 자료를 빼는 연산
  pop_front : 덱의 앞에서 자료를 빼는 연산
  pop_back : 덱의 뒤에서 자료를 빼는 연산
  front : 덱의 가장 앞에 있는 자료를 보는 연산
  back : 덱의 가장 뒤에 있는 자료를 보는 연산

• Java ArrayDeque 라이브러리
• 10866번 (https://www.acmicpc.net/problem/10866) -> 강의에선 라이브러리를 활용해서 풀었는데 직접 구현해보고 코드를 업데이트 할 예정임