[자료 구조] Queue 개념 설명과 구현

⬛ Queue 개념

 

• 한쪽 방향(Rear)에서는 자료의 삽입이, 다른 한 쪽 방향(Front)에서는 자료의 삭제가 이루어지는 FIFO(First In First Out) 형식의 자료 구조
• Queue의 가장 먼저 들어온 요소를 Front, 가장 늦게 들어온 요소를 Rear라고 부르며 이 두가지 요소에 의해서만 접근이 가능
• Rear에서 이루어지는 삽입 연산을 ‘enQueue’, Front에서 이루어지는 삭제 연산을 ‘deQueue’라고 한다.

⬛ Queue 연산

1. enQueue(int data) : Rear에 데이터를 추가

2. deQueue() : Front에 있는 데이터를 반환 후 삭제

3. peek() : Front에 있는 데이터를 반환 (삭제 x)

⬛ Queue 활용

• 프로세스 스케줄링
• 프린터 출력
• 은행 번호표
• 너비 우선 탐색 알고리즘

⬛ Queue 구현

MyQueue.java

package com.queue;

public class MyQueue {
	private Node front;
	private Node rear;
	private int size = 0;

	private void enQueue(int data) {
		Node new_node = new Node(data);
		if (isEmpty()) {
			front = new_node;
			rear = new_node;
		} else {
			rear.setNext(new_node);
			rear = new_node;
		}
		size++;

	}

	private int deQueue() {
		if (isEmpty()) {
			System.out.print("Stack Underflow ");
			return -1;
		}

		int data = front.getData();
		front = front.getNext();
		if (front == null) {
			rear = null;
		}
		size--;
		return data;
	}

	private int peek() {
		if (isEmpty()) {
			System.out.print("No item ");
			return -1;
		}
		return front.getData();
	}

	private boolean isEmpty() {
		if (size == 0) {
			return true;
		}
		return false;
	}

	private int size() {
		return size;
	}

	@Override
	public String toString() {
		if (isEmpty()) {
			return "Queue is empty";
		}
		String str = "[";
		Node temp = front;
		while (temp.getNext() != null) {
			str += temp.getData();
			str += ", ";
			temp = temp.getNext();
		}
		str += temp.getData();
		return str + "]";
	}

	public static void main(String[] args) {
		MyQueue mq = new MyQueue();

		mq.enQueue(0);
		mq.enQueue(1);
		mq.enQueue(2);
		mq.enQueue(3);
		mq.enQueue(4);
		mq.enQueue(5);
		System.out.println(mq);
		System.out.println(mq.peek());
		System.out.println(mq.deQueue());
		System.out.println(mq.deQueue());
		System.out.println(mq.deQueue());
		System.out.println(mq.deQueue());
		System.out.println(mq.deQueue());
		System.out.println(mq.deQueue());
		System.out.println(mq.size());
		System.out.println(mq);

	}

}

 

Node.java

package com.queue;

public class Node {
	private int data;
	private Node next;

	Node(int data) {
		setData(data);
		setNext(null);
	}

	Node() {
		setNext(null);
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}

}