Te JAVA (2) - 자료구조 구현 (Queue)

1. LinkedList 구현 (ListNode, add(), remove(), contains())
2. Stack 구현 (int 배열, push(), pop())
3. Stack 구현 (ListNode, push(), pop())
4. Queue구현 (int배열, ListNode 이용)

 

2주차 실습의 1~3 내용은 이전 블로그에 존재한다.

https://abbiddo.tistory.com/95

Te JAVA (2) - 자료구조 구현 (LinkedList)

https://abbiddo.tistory.com/96

Te JAVA (2) - 자료구조 구현 (Stack)

 

---

 

4. Queue 구현 (Array)

Queue 정의

• 먼저 집어 넣은 데이터가 먼저 나오는 FIFO 구조로 저장하는 자료구조다.

 

기본 정의

• 큐의 크기를 나타내는 size, 배열의 앞 부분을 나타내는 front, 배열의 뒷 부분을 저장하는 back, 데이터들을 저장하는 int 배열 value을 선언한다.
• 생성자에서는 크기를 입력받아 배열의 크기와, 배열, front, back을 초기화한다.

public class QueueArray {

    private int front;  // 배열의 앞 부분, 제거할 데이터
    private int back;   // 배열의 뒷 부분, 최근 추가한 데이터
    private int size;
    private int[] value;

    public QueueArray(int size){
        front = -1;
        back = -1;
        this.size = size;
        value = new int[size];
    }

 

push 메소드

    void push(int data){
        if (back == size - 1) { return; }
        value[++back] = data;
    }

 

pop 메소드

    int pop(){
        if (front == back) { return Integer.MIN_VALUE; }
        return value[++front];
    }

 

print 메소드

    void print(){
        for (int i = front + 1; i <= back; i++){
            System.out.print(value[i] + " - ");
        }
    }

 

---

 

2 - 1. Queue Test

push Test

    @Test
    void push() {
        QueueArray queue = new QueueArray(3);

        queue.push(10);
        queue.push(20);
        queue.push(30);

        queue.print();
        // 10 - 20 - 30 -

    }

 

pop Test

    @Test
    void pop() {
        QueueArray queue = new QueueArray(3);

        queue.push(10);
        queue.push(20);
        queue.push(30);

        queue.pop();

        queue.print();
        // 20 - 30 -

    }

 

---

 

3 - 3. Queue 구현 (ListNode)

기본 정의

• 링크드 리스트의 처음을 나타내는 head 노드를 저장할 변수를 선언한다.

public class QueueListNode {

    private ListNode head;

 

push 메소드

• stack에서 push 하는 것과 동일하다.

    void push(int data){

        ListNode add = new ListNode(data);

        if (head == null){
            head = add;
            return;
        }

        ListNode cur = head;
        while (cur.getNext() != null){
            cur = cur.getNext();
        }

        cur.setNext(add);
    }

 

pop 메소드

    int pop(){

        if (head == null) { return Integer.MIN_VALUE; }

        int data = head.getValue();
        head = head.getNext();

        return data;
    }

 

print 메소드

    void print(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.getValue() + " - ");
            cur = cur.getNext();
        }
    }

 

---

 

3 - 4. Queue Test

push Test

    @Test
    void push() {

        QueueListNode queue = new QueueListNode();

        queue.push(10);
        queue.push(20);
        queue.push(30);

        queue.print();
        // 10 - 20 - 30 -

    }

 

pop Test

    @Test
    void pop() {

        QueueListNode queue = new QueueListNode();

        queue.push(10);
        queue.push(20);
        queue.push(30);

        queue.pop();

        queue.print();
        // 20 - 30 -

    }