TIL

자료구조 타입 중 큐의 대해 공부했다.

큐(queue)

먼저 들어온 데이터가 먼저 나가는 구조의 데이터 타입.
선입선출(FIFO: First-In First-Out)이라고 한다.

삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)라고 한다.

백준 18258번: 큐 2

https://www.acmicpc.net/problem/18258

큐를 구현하는 간단한 문제다.
배열을 이용해 구현했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int size;
	static int[] que;
	static int front;
	static int rear;
	
	public static void push(int item) {
		que[rear++]=item;	
	}
	
	public static int size() {
		return rear-front;
	}
	
	public static int pop() {
		if(empty()==1) {
			return -1;
		}else {
			int value= que[front++];
			return value;
		}
		
	}
	
	public static int empty() {
		if(front==rear) {
			return 1;
		}else {
			return 0;
			
		}
	}
	
	public static int front() {
		if(empty()==1) {
			return -1;
        }
        return que[front];
	}
	
	public static int back() {
		if(empty()==1) {
			return -1;
        }
       	return que[rear-1];
	}
	

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		size =front=rear=0;
		que= new int[2000000];
		
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			switch (str) {
			case "push":
				int item = Integer.parseInt(st.nextToken());
				push(item);
				break;
			case "pop":
				bw.write(pop()+"\n");
				break;
			case "front":
				bw.write(front()+"\n");
				break;
			case "back":
				bw.write(back()+"\n");
				break;
			case "empty":
				bw.write(empty()+"\n");
				break;
			case "size":
				bw.write(size()+"\n");
				break;
			}
		}
		bw.flush();
		bw.close();
		br.close();
		
	}
}

잘 모르겠어서 다른 사람 코드를 조금 참고했다 (...)
이런 구현 문제는 덜컥 겁을 먹고 마는듯.
내일은 연결 리스트로 구현해보겠다.

위와 같이 1차원 배열로 구현한 큐를 '선형 큐'라고 한다.
이러한 선형 큐는 이해하기는 쉽지만, 문제점이 있다.
front와 rear가 점점 증가하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지를 못한다. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야한다.
(이러한 방식의 코드를 백준 문제에 사용하면 시간 초과가 난다.)
그렇기 때문에 원형 큐를 사용해야한다.

원형 큐 구현은 내일..