[자료구조] 선형 큐(LinearQueue)

Queue란?

● 선입선출(First-In-Fast-Out - FIFO)

● 순서가 보장된 처리 (사용자가 몰린 서버)

Queue의 주요 동작

●  push(), offer(), add()

● pop(), poll()

● peek()

선형 큐 (LinearQueue)

1. 우선 Queue 구현에 사용할 IQueue 인터페이스를 생성

package queue;

public interface IQueue<T> {
    void offer(T data);
    T poll();
    T peek();
    int size();
    void clear();
    boolean isEmpty();
}

 

2. IQueue를 구현할 MyLinkedQueue클래스를 생성 후 메서드를 생성

package queue;

public class MyLinkedQueue<T> implements IQueue<T> {

    @Override
    public void offer(T data) {

    }

    @Override
    public T poll() {
        return null;
    }

    @Override
    public T peek() {
        return null;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public boolean isEmpty() {
        return false;
    }
}

 

3. Queue 구현에 사용할 Node를 생성

private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

 

4. 멤버변수 설정 및 생성자 생성

private Node head;
    public Node tail;
    private int size;

    public MyLinkedQueue() {
        this.size = 0;
        this.head = new Node(null); // dummy node
        this.tail = this.head;
    }

 

5. Queue에 데이터를 넣어주는 offer함수 예제

@Override
    public void offer(T data) { // queue에 데이터를 넣는 연산
        Node node = new Node(data);
        this.tail.next = node;
        this.tail = this.tail.next;
        this.size++;
    }

 

6. Queue에서 데이터를 가져오는 poll함수 예제

@Override
    public T poll() { // queue에서 데이터를 빼오는 연산
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        Node node = this.head.next;
        this.head.next = node.next;
        node.next = null;
        this.size--;

        if (this.head.next == null) {
            this.tail = this.head;
        }

        return node.data;
    }

 

7. Queue의 데이터를 확인만 진행하는 peek함수 예제

@Override
    public T peek() {  // queue에서 데이터를 빼지는 않고 그대로 둔 상태에서 가장 앞에 데이터가 무엇인지 확인하는 연산
        if (this.isEmpty()) {
            throw  new IllegalStateException();
        }
        return this.head.next.data;
    }

 

8. Queue의 size를 확인하는 size함수 예제

@Override
    public int size() {
        return this.size;
    }

 

전체 코드

package queue;

public class MyLinkedQueue<T> implements IQueue<T> {

    private Node head;
    public Node tail;
    private int size;

    public MyLinkedQueue() {
        this.size = 0;
        this.head = new Node(null); // dummy node
        this.tail = this.head;
    }

    @Override
    public void offer(T data) { // queue에 데이터를 넣는 연산
        Node node = new Node(data);
        this.tail.next = node;
        this.tail = this.tail.next;
        this.size++;
    }

    @Override
    public T poll() { // queue에서 데이터를 빼오는 연산
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        Node node = this.head.next;
        this.head.next = node.next;
        node.next = null;
        this.size--;

        if (this.head.next == null) {
            this.tail = this.head;
        }

        return node.data;
    }

    @Override
    public T peek() {  // queue에서 데이터를 빼지는 않고 그대로 둔 상태에서 가장 앞에 데이터가 무엇인지 확인하는 연산
        if (this.isEmpty()) {
            throw  new IllegalStateException();
        }
        return this.head.next.data;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public void clear() {
        this.head.next = null;
        this.tail = head;
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;
    }

    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}