[伯俊-JAVA]/BOJ 10845解題

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

質問する

整数を格納するキューを実装し、入力としてのコマンドを処理するプログラムを作成してください.
命令は全部で6条ある.
Push X:整数Xをキューに入れる演算.
pop:キューから先頭の整数を削除し、出力します.キューに整数がない場合は、-1が出力されます.
size:出力キューの整数の個数.
キューが空の場合、1または0が出力されます.
front:出力キューの一番前の整数.キューに整数がない場合は、-1が出力されます.
back:出力キューの一番後ろの整数.キューに整数がない場合は、-1が出力されます.

入力

1行目に与えられるコマンド数N(1≦N≦10000).2行目からN行目までそれぞれ1つのコマンドがあります.与えられた整数は1以上であり、100000以下である.問題にない命令はない.

しゅつりょく

出力するコマンドが発行されるたびに、各行に1つのコマンドが出力されます.

コード#コード#

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;

            }
        }
    }
}

リファレンス

Javaでは,キューはLinkedListを用いて実現されるキューであり,配列実装を用いたキューに比べて最も大衆化され,実現も容易である.(少なくとも筆者はそう思っている…)
何らかの理由で、アレイ内のキューは内部にオブジェクト[]配列を含み、アレイ内の要素の数に応じて容積(アレイサイズ)を減少または増大させる必要がある.キューを線形キューとして表すと、要素が後方に傾くため、これらの問題を効果的に克服し、サブプロトタイプとして表すことができます.この実装には考慮すべき要素が多く、少し複雑です.
ただし、配列ではなく接続リストを使用すると、上記の欠点は解決されます.各データはノード(node)オブジェクトに含まれており、ノード間は相互に接続されているため、配列のように要素の数に応じて増やしたり減らしたりする必要はなく、挿入や削除時にリンクを切断したり接続したりするだけなので、管理面でも便利です.
ソース:https://st-lab.tistory.com/184