큐 (Queue)

  • 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조

  • 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 한다.

  • 큐의 주요 메소드

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

        큐를 직접 구현하는 경우

  • 배열을 이용하여 구현 가능

    • 시작하는 index인 begin, 마지막 index인 end가 필요하다.
    • push 연산은 end번째 index에 자료를 넣는 것을 의미한다.
      • queue[end++] = 자료;
    • pop 연산은 begin 인덱스에 있는 값을 리턴하고 begin 인덱스를 하나 증가시키면 된다.
      • return queue[begin++];
    • size 연산은 end에서 begin을 빼면 된다.
      • return end - begin;
    • isEmpty 연산은 end == begin인지 체크하면 된다.

      큐의 예제

  • 조세퍼스 문제 boj.kr/1158

    • 1번부터 N번까지 N명의 사람들이 원을 이루면서 앉아있고, 양의 정수 M(<=N)이 주어진다.

    • 순서대로 M번째 사람을 제거한다.

    • 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속한다.

    • 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

    • 원에서 사람들이 제거되는 순서를 (N,M) - 조세퍼스 순열이라고 한다.

      • 아이디어 1

        • 큐를 이용한 문제 해결

          1. 지나친 사람은 언젠가 다시 만나야 한다.
          2. 매 3번째 사람은 제거되며 다신 만날 일이 없다.
          3. 큐의 처음에서 사람을 만날 때 마다 다시 만날 가정을 하고 맨 끝으로 넣으면 된다.
          • 구현

            import java.io.BufferedReader;
            import java.io.IOException;
            import java.io.InputStreamReader;
            import java.util.Queue;
            import java.util.StringTokenizer;
            import java.util.concurrent.ArrayBlockingQueue;
            
            public class Main{
              public static void main(String args[]) throws IOException {
                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                  StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                  int n = Integer.parseInt(st.nextToken());
                  int m = Integer.parseInt(st.nextToken());
                  Queue<Integer> in_q = new ArrayBlockingQueue<>(n);
            
                  for(int i=1; i<=n; i++)
                      in_q.add(i);
            
                  StringBuffer sb = new StringBuffer();
            
                  while(!in_q.isEmpty())
                      for(int i=0; i<m; i++)
                          if(!(i==(m-1)))
                              in_q.add(in_q.poll());
                          else
                              sb.append(in_q.poll() + ", ");
            
                  System.out.println("<" + sb.toString().substring(0, sb.length()-2) + ">");
              }
            }
        • ArrayList를 이용한 문제 해결

          1. 한 사람을 제거하고 난 뒤에 지나친 사람을 만나야 한다는 특성을 이용
            1. 1 Mod(%) 연산을 이용하여 해당 특성을 구현 가능하다.
          2. ArrayList로 인덱스의 처음 위치부터 이동 위치를 기록한다.
          3. m-1만큼 이동하고 해당 원소를 삭제한다.
          4. size가 전부 줄어들 때까지 반복한다.
          • 구현

            import java.io.BufferedReader;
            import java.io.IOException;
            import java.io.InputStreamReader;
            import java.util.*;
            
            public class Main{
              public static void main(String args[]) throws IOException {
                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                  StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                  int n = Integer.parseInt(st.nextToken());
                  int m = Integer.parseInt(st.nextToken());
                  List<Integer> ll = new ArrayList<>();
            
                  for(int i=1; i<=n; i++)
                      ll.add(i);
            
                  StringBuffer sb = new StringBuffer();
                  sb.append("<");
                  int cursor = 0;
            
                  while(!ll.isEmpty()) {
                      cursor = (cursor + (m-1)) % n;
            
                      if(ll.size() != 1)
                          sb.append(ll.get(cursor) + ", ");
                      else
                          sb.append(ll.get(cursor) + ">");
            
                      ll.remove(cursor);
                      n--;
                  }
            
                  System.out.println(sb.toString());
              }
            }

덱 (Deque)

  • Double-ended queue의 약자
  • 양쪽 끝에서 자료를 넣고 양쪽 끝에서 자료를 뺄 수 있는 구조
  • 주요 메소드
    • push_front
      • 덱의 앞에 자료를 넣는 연산
    • push_back
      • 덱의 뒤에 자료를 넣는 연산
    • pop_front
      • 덱의 앞에서 자료를 빼는 연산
    • pop_back
      • 덱의 뒤에서 자료를 빼는 연산
    • front
      • 덱의 가장 앞에 있는 자료를 보는 연산
    • back
      • 덱의 가장 뒤에 있는 자료를 보는 연산

문자열

  • 아스키코드 (ASC II)
    • 문자 인코딩 방법
    • 대표적인 아스키 코드
      • '0', 48
      • 'A', 65
      • 'a', 97
      • NULL, 0
    • 숫자가 저장되어 있는데, 출력만 글자로 해주는 것으로 이해하면 편하다.
  • 예제 문제
    • boj.kr/2743