큐(Queue)

큐(queue)의 구조

먼저 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First Out)구조로 되어있다.

front에서 요소를 꺼내고, rear에서 요소를 삽입하는 구조이다.

 

큐는 Array와 LinkedList로 구현할 수 있다.

 

Array로 구현 하기

 class ArrayQueue {
    int MAX = 5;
    int front;
    int rear;
    int [] queue;

    public ArrayQueue() {
        front = rear = 0;
        queue = new int[MAX];
    }

    public void push(int value) {
        if((rear == MAX-1)) {
            System.out.println("Queue is Full");
        }
        queue[rear++] = value;
    }
    public int pop() {
        if(front == rear) {
            System.out.println("Queue is Empty");
        }
        return queue[front++];
    }
    public int peek() {
        if(front == rear) {
            System.out.println("Queue is Empty");
            return -1;
        }
        return queue[front];
    }
}

 

 

LinkedList로 구현하기

1. 노드 클래스 구현

class QueueNode {
    int value;
    QueueNode queueNode;
    public QueueNode(int value) {
        this.value = value;
        queueNode = null;
    }
    public int getValue() {
        return value;
    }
    public QueueNode getNextNode() {
        return queueNode;
    }
    public void setNextNode(QueueNode queueNode) {
        this.queueNode = queueNode;
    }
}

 

2. Queue 클래스 구현

 class LinkedListQueue {
    QueueNode front, rear;

    public LinkedListQueue() {
        front = rear = null;
    }
    
     public boolean queueisEmpty() {...}	// 큐가 비었는지 확인하는 메서드
     public void push(int value) {...}		// 큐에 요소를 삽입하는 메서드
     public QueueNode pop() {...}			// 큐의 요소를 출력하는 메서드    
}

 

3. 큐가 비었는지 확인하는 메서드 구현

 public boolean queueisEmpty() {
    if (front == null && rear == null) {
        return true;
    } else {
        return false;
    }
}

 

4. 삽입 메서드 구현

public void push(int value) {
	QueueNode queueNode = new QueueNode(value);
    if (queueisEmpty()) {
        front = rear = queueNode;
    } else {
        front.setNextNode(queueNode);
        front = queueNode;
    }
}

 

5. 출력 메서드 구현

 public QueueNode pop() {
    if (queueisEmpty()) {
        System.out.println("Queue is Empty");
        return null;
    } else {
        QueueNode popNode = rear;
        rear = rear.getNextNode();
        return popNode;
    }
}