자료구조
큐
누룽지맛치킨
2023. 2. 2. 16:08
큐
- 입구와 출구가 각각 하나씩 있는 자료구조
- FIFO(First In First Out)
큐 연산
- enQueue : 큐의 가장 마지막 아이템 뒤에 새로운 아이템을 추가한다.
- deQueue : 큐의 맨앞에 있는 아이템을 빼면서 반환한다.
- isEmpty : 큐가 비어있는지 확인한다.
- isFull : 큐가 꽉 찾는지 확인한다.
큐 구현(배열 사용)
public class Queue{
int queue[] = new int[10];
int front = 0;
int rear = 0;
public void enQueue(int item){
if(isFull()){
System.out.println("큐가 꽉 차있습니다.");
return;
}
queue[rear] = item;
rear = (rear + 1)%10;
}
public int deQueue(){
if(isEmpty()){
System.out.println("큐가 비었습니다.");
return -1;
}
int temp = queue[front];
front = (front + 1)%10;
return temp;
}
public boolean isEmpty(){
return (front==rear);
}
public boolean isFull() {
return (front==(rear+1)%10);
}
}예시
- 백준 18258번 큐2
https://www.acmicpc.net/problem/18258
1) 문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
2) 코드
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int queue[] = new int[N];
int front =0;
int rear = 0;
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
String input = st.nextToken();
if(input.equals("empty")) {
if(front==rear) {
sb.append(1).append("\n");
}
else {
sb.append(0).append("\n");
}
}
else if(input.equals("size")) {
sb.append(rear-front).append("\n");
}
else if(input.equals("front")) {
if(front==rear) {
sb.append(-1).append("\n");
}
else {
sb.append(queue[front]).append("\n");
}
}
else if(input.equals("back")){
if(front==rear) {
sb.append(-1).append("\n");
}
else {
sb.append(queue[rear-1]).append("\n");
}
}
else if(input.equals("pop")) {
if(front==rear) {
sb.append(-1).append("\n");
}
else {
sb.append(queue[front]).append("\n");
front = front +1;
}
}
else if(input.equals("push")) {
int item = Integer.parseInt(st.nextToken());
queue[rear] = item;
rear = rear+1;
}
}
System.out.print(sb);
}
}