[ENG][자료구조]Queue 이론과 예제

Overview

큐의 구조는 스택과 다르게 '선입선출'의 구조를 가지고 있습니다.

스택은 막힌 박스와 같아 먼저 들어온 것이 가장 나중에 나가는 구조지만, 큐는 먼저 들어온 것이 먼저 나가는 구조입니다. 좋은 예로 은행에 있는 번호표가 있습니다. 은행에 방문하여 먼저 온 사람이 먼저 업무를 봐야 합니다. 은행에서는 번호표를 나눠줍니다. 먼저 온 손님은 늦게 온 손님보다 먼저 서비스를 받게 하기 위해서죠. 이러한 은행의 번호표의 체계가 큐(Queue)입니다. 

  - enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부

  - dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제

  - peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인

  - front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호

  - rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호

 

Usecase

  - 은행 줄 서기

 

Structure

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

 

Code Example

package com.data.structure;

public class MyQueue {
	final int MAX_N = 1000;

	int front;
	int rear;
	int queue[] = new int[MAX_N];

	void init() {
		front = 0;
		rear = 0;
	}

	boolean queueIsEmpty() {
		return (front == rear);
	}

	boolean queueIsFull() {
		if ((front + 1) % MAX_N == rear) {
			return true;
		} else {
			return false;
		}
	}

	boolean enqueue(int value) {
		if (queueIsFull()) {
			System.out.print("queue is full!");
			return false;
		}
		queue[front] = value;
		front++;
		if (front == MAX_N) {
			front = 0;
		}

		return true;
	}

	Integer dequeue() {
		if (queueIsEmpty()) {
			System.out.print("queue is empty!");
			return null;
		}

		Integer value = new Integer(queue[rear]);

		rear++;
		if (rear >= MAX_N) {
			rear = 0;
		}
		return value;
	}

	public static void main(String arg[]) throws Exception {
		MyQueue myQueue = new MyQueue();

		int N = 10;

		myQueue.init();

		for (int i = 0; i < N; i++) {
			myQueue.enqueue(i);
		}

		while (!myQueue.queueIsEmpty()) {
			Integer value = myQueue.dequeue();
			if (value != null) {
				System.out.print(value.intValue() + " ");
			}
		}
		System.out.println();
	}
}

 

Console Result

0 1 2 3 4 5 6 7 8 9

 

Conclusion

N/A