https://www.acmicpc.net/problem/10845
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
코드
Array 버전
// Array 버전
public class ArrayQueue {
static int Queue[];
static int rear;
static void init(){
rear=-1;
}
static int empty(){
if(rear==-1)
return 1;
return 0;
}
static void push(int data){
rear++;
Queue[rear]=data;
//System.out.println(data);
}
static int pop(){
int tmp=Queue[0];
if(rear<0)
return -1;
for(int i=0;i<rear;i++){
Queue[i]=Queue[i+1];
}
rear--;
return tmp;
}
static int size(){
if(rear<0)
return 0;
return rear+1;
}
static int front(){
if(empty()==1)
return -1;
return Queue[0];
}
static int back(){
if(empty()==1 || rear == -1)
return -1;
return Queue[rear];
}
public static void main(String args[]){
init();
int N;
Scanner sc = new Scanner(System.in);
N=sc.nextInt();
Queue= new int[N];
//push(1);
for(int i=0; i<N;i++){
String s;
s=sc.next();
if(s.equals("push")){
int t=sc.nextInt();
push(t);
}
else if(s.equals("pop")){
System.out.println(pop());
}
else if(s.equals("empty")){
System.out.println(empty());
}
else if(s.equals("size")){
System.out.println(size());
}
else if(s.equals("front")){
System.out.println(front());
}
else if(s.equals("back")){
System.out.println(back());
}
}
}
}LinkedList 버전
// LinkedList 버전
class Node { // Node
private int val = 0;
private Node next = null;
public Node(int val) {
this.val = val;
}
public void setVal(int val) {
this.val = val;
}
public void setNext(Node next) {
this.next = next;
}
public int getVal() {
return this.val;
}
public Node getNext() {
return this.next;
}
}
class Queue {
private Node head = null;
public Queue() {
this.head = null;
}
public void push(int val) {
if (this.head == null) { // 큐에 데이터가 없으면
this.head = new Node(val); // node 생성
} else {
Node node = new Node(val);
Node FirstNode = this.head;
while (this.head.getNext() != null) { // 연결노드가 있는지 확인
// -> 다음 노드에 이어 붙이기 위한 용도
this.head = this.head.getNext();
}
this.head.setNext(node); // 입력값 이어 붙이기
this.head = FirstNode;
}
}
public int pop() { // Queue는 선입선출 구조로 맨 앞 데이터를 빼주면 pop
if (this.head == null) {
return -1;
} else {
int n = this.head.getVal(); // 처음 노드의 데이터 저장
this.head = this.head.getNext(); // 헤더에 다음 노드를 저장하여 처음 노드로 변환
return n; // 데이터 return
}
}
public int front() { // Queue의 맨앞 value 출력
if (this.head == null) {
return -1;
} else {
return this.head.getVal();
}
}
public int back(int pushN) { // Queue의 맨뒤 value 출력
// if (this.head.getNext() == null) { // 다음 노드가 없을 때 = 맨뒤
if (empty() == 1) {
return -1;
} else {
return pushN;
}
}
public int empty(){
if(this.head == null)
return 1;
return 0;
}
public int size() { // 큐의 크기 측정
int cnt = 0;
if (this.head == null) {
return cnt;
} else {
Node FirstNode = this.head;
while (this.head.getNext() != null) {
this.head = this.head.getNext();
cnt++;
}
this.head = FirstNode;
return cnt + 1;
}
}
}
public class LinkedListQueue {
public static void main(String args[]) {
Queue q = new Queue();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int pushN = 0;
while( n-- > 0 ) {
String str = sc.next();
switch (str) {
case "push":
pushN = sc.nextInt();
q.push(pushN);
break;
case "pop":
System.out.println(q.pop());
break;
case "empty":
System.out.println(q.empty());
break;
case "size":
System.out.println(q.size());
break;
case "front":
System.out.println(q.front());
break;
case "back":
System.out.println(q.back(pushN));
break;
}
}
}
}Quque 클래스 버전
### Quque 클래스 버전
public class Queue_20220124 {
public static void main(String[] args) throws Exception {
Queue<Integer> q = new LinkedList<Integer>();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int pushN = 0;
while( n-- > 0 ) {
String str = sc.next();
switch(str) {
case "push":
pushN = sc.nextInt();
q.add(pushN);
break;
case "front":
System.out.println( q.isEmpty()?-1:q.peek() );
break;
case "back":
System.out.println( q.isEmpty()?-1:pushN);
break;
case "empty":
System.out.println( q.isEmpty()?1:0);
break;
case "pop":
System.out.println( q.isEmpty()?-1:q.poll());
break;
case "size":
System.out.println( q.size());
break;
}
}
}
}참고
자바에서는 큐의 경우 LinkedList로 구현한 큐가 쓰이는 만큼 가장 대중적이고, 배열로 구현하는 큐에 비해 쉽다. (적어도 필자는 그렇게 생각한다..)
이유가 뭔가하면 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고있고, 요소가 배열에 들어있는 양에 따라 용적(배열 크기)을 줄이거나 늘려주어야 하고, 큐를 선형적인 큐로 구현했을 경우 요소들이 뒤로 쏠리기 때문에 이러한 문제를 효율적으로 극복하고자 원형 형태로 구현하는데 이 구현이 고려해야 할 점도 많고 조금 복잡하다.
하지만 배열 대신 연결리스트로 구현하게 될 경우 위와같은 단점들이 해결된다. 각 데이터들을 노드(node) 객체에 담고 노드 간 서로 연결해주기 때문에 배열처럼 요소 개수에 따라 늘려주거나 줄여줄 필요도 없고 삽입, 삭제 때는 연결 된 링크만 끊어주거나 이어주면 되기 때문에 관리면에서도 편하다.
