Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

1. 큐 2

18258번

큐의 개념을 익히고 실습하는 문제. 연산 당 시간 복잡도가 O(1)이어야 한다는 점에 유의하세요.

이번 문제는 큐를 구현하는 문제입니다.
큐(Queue)를 구현해보는 문제입니다. 큐는 스택의 반대 개념으로, 리스트의 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽에서 이루어지는 형태입니다. 큐는 선입 선출인, FIFO(First in First out) 구조로 먼저 들어간 데이터가 먼저 나오는 구조입니다.
시간 제한을 주의해야 합니다..!

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	static int[] q = new int[2000000];	
	static int size = 0;	
	static int front = 0;
	static int back = 0;	
	static StringBuilder sb = new StringBuilder();
    
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
        
		int N = Integer.parseInt(br.readLine());		
 
		while(N-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			
			switch(st.nextToken()){
				case "push": push(Integer.parseInt(st.nextToken())); break;
				case "pop" : pop(); break;
				case "size" : size(); break;
				case "empty" : empty(); break;
				case "front" : front(); break;
				case "back" : back(); break;			
			}
		}
		System.out.println(sb);
	}
	
	static void push(int n) {
		q[back] = n;
		back++;
		size++;
	}
	
	static void pop() {
		if(size == 0) {
			sb.append(-1).append('\n');
		}
		else {
			sb.append(q[front]).append('\n');	// 맨 앞 원소 출력 
			size--;
			front++;	// front가 가리키는 위치 1 증가 
		}
	}
	
	static void size() {	// 큐에 들어있는 정수의 개수 
		sb.append(size).append('\n');
	}
	
	static void empty() {    // 큐가 비어있으면 1 or 0
		if(size == 0) {
			sb.append(1).append('\n');
		}
		else sb.append(0).append('\n');
	}
	
	static void front() {
		if(size == 0) { 
			sb.append(-1).append('\n');
		}
		else {
			sb.append(q[front]).append('\n');	 // 맨 앞 원소 출력 
		}
	}
	
	static void back() {
		if(size == 0) {
			sb.append(-1).append('\n');
		}
		else {
			sb.append(q[back - 1]).append('\n');	// 맨 뒤 원소 출력 
		}
	} 
}

• Python

import sys 
from collections import deque 
N = int(sys.stdin.readline()) 
que = deque() 

def push(que, x): 
    que.append(x) 
    
def pop(que): 
    if(not que): 
        return -1 
    else: 
        return que.popleft() 
    
def size(): 
    return len(que) 

def empty(): 
    if(not que): 
        return 1 
    else: 
        return 0 
    
def front(): 
    if(not que): 
        return -1 
    else: 
        return que[0] 
    
def back(): 
    if(not que): 
        return -1 
    else: 
        return que[-1] 
    
for i in range(N): 
    s = sys.stdin.readline().split() 
    if (s[0] == "push"): 
        push(que, s[1]) 
    elif(s[0] == "pop"): 
        print(pop(que)) 
    elif(s[0] == "size"): 
        print(size()) 
    elif(s[0] == "empty"): 
        print(empty()) 
    elif(s[0] == "front"): 
        print(front()) 
    elif(s[0] == "back"): 
        print(back())