[코테]20-큐

큐(Queue)

순서가 있는 자료구조.
한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
pop <- [ ] <- push

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

• java의 경우에는 java.util.Queue

  학교 다닐 때 배웠던 자료구조가 새록새록 기억난다..ㅎㅎ 그 때는 C로 구현했었는데 여기선 주로 java를 사용할 예정!

• 큐를 구현.

• 각 연산 O(1)만에 구현해야함.

  1) 배열
  2) 링크드 리스트

  일차원 배열 하나로 구현할 수 있다. 큐에 포함되어 있는 내용은 begin, end이다.
  int queue[10000];
  int begin = 0;
  int end= 0;

  => 배열을 사용할 때 배열의 크기를 정해주어야 함!
  문제를 풀 때는 대부분 그 크기가 문제에 나와있음.

• DFS를 구현할 때 자주 사용함.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int n= sc.nextInt();
		int queue[] = new int[n];
		int begin = 0;
		int end = 0;
		
		for(int i=0;i<=n;i++) {
			String str = sc.next();
			if(str.equals("push")) {
				int num = sc.nextInt();
				queue[end++] = num;
			}else if(str.equals("front")) {
				if(begin == end) {
					System.out.println("존재하지 않음");
				}else {
					System.out.println(queue[begin]);
				}
			}else if(str.equals("back")) {
				if(begin == end) {
					System.out.println("존재하지 않음");
				}else {
					System.out.println(queue[end-1]);
				}
			}else if(str.equals("size")) {
				System.out.println(end-begin);
			}else if(str.equals("empty")) {
				if(begin == end) {
					System.out.println("1");
				}else {
					System.out.println("0");
				}
			}else if(str.equals("pop")) {
				if(begin==end) {
					System.out.println("존재하지 않음");
				}else {
					System.out.println(queue[begin]);
					begin++;
				}
			}
		}
		
	}
} 

=> 아주 기본적인 queue 구현

Deque

양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조.
Double-ended queue의 약자.
push_front : 덱의 앞에 자료를 넣는 연산
push_back : 덱의 뒤에 자료를 넣는 연산
pop_front : 덱의 앞에서 자료를 빼는 연산
pop_back : 덱의 뒤에서 자료를 빼는 연산
front : 덱의 가장 앞에 있는 자료를 보는 연산
back : 덱의 가장 뒤에 있는 자료를 보는 연산

=> JAVA에서는 ArrayDeque가 있어서 사용하면 됨.

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.