[자료구조] Queue(큐)

iacid123·2020년 4월 30일
0
post-thumbnail

Queue(큐)의 개념

  • 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식
  • Stack(스택)과 반대되는 개념
  • 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

Queue(큐)의 종류

  1. 선형(큐)
    • 크기 제한
    • 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮김
  2. 원형(큐)
    • 선형 큐의 문제점을 보완
    • front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식

Queue(큐)의 메소드

배열을 이용한 큐

  • getSize() : 큐의 크기를 반환
  • isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
  • isFull() : 큐가 가득 차있으면 true, 그렇지 않으면 false 반환
  • enqueue() : ((rear+1) % size)번째 인덱스에 데이터 추가
  • dequeue() : ((front+1) % size)번째 인덱스의 데이터 반환
  • toString() : 큐의 모든 데이터를 반환
  • clear() : 큐의 모든 데이터를 삭제

연결리스트를 이용한 큐

  • isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
  • enqueue() : 큐가 비어있으면 새로운 노드를 front와 rear로 선언, 비어있지 않으면 새로운 노드를 rear 노드의 next로 선언한 후 새로운 노드를 rear로 선언
  • dequeue() : front 노드의 데이터 반환 후 front 노드의 next를 front 노드로 선언
  • toString() : 큐의 모든 데이터를 반환
  • clear() : 큐의 모든 데이터를 삭제

배열을 이용한 (원형)큐

ArrayQueue.java

package array.queue;

public class ArrayQueue {
	private final int DEFAULT_SIZE = 100000;
	private int front = 0;
	private int rear = 0;
	private Object [] data;
	
	public ArrayQueue() {
		data = new Object [DEFAULT_SIZE];
	}
	
	public ArrayQueue(int size) {
		if(size > 0) {
			data = new Object [size+1];
		} else {
			throw new ArrayIndexOutOfBoundsException();
		}
	}
	
	public int getSize() {
		return this.data.length;
	}
	
	public boolean isEmpty() {
		return rear == front;
	}
	
	public boolean isFull() {
		return rear+1 % getSize() == front;
	}
	
	public void enqueue(Object input) {
		if(isFull()) {
			throw new ArrayIndexOutOfBoundsException();
		} else {
			data[++rear % getSize()] = input;
		}
	}
	
	public Object dequeue() {
		if(isEmpty()) {
			throw new NullPointerException();
		} else {
			return data[++front % getSize()];
		}
	}
	
	public String toString() {
		String str = new String("[ ");
		
		if(isEmpty()) {
			return str + "]";
		} else {
			for (int i = front+1; i != (rear+1) % getSize(); i = (i+1) % getSize()) {
				str += data[i] + " ";
			}
			return str + "]";
		}
	}
	
	public void clear() {
		for (int i = front+1; i != (rear+1) % getSize(); i = (i+1) % getSize()) {
			data[i] = null;
		}
		front = 0;
		rear = 0;
	}
}

연결리스트를 이용한 큐

LinkedListQueue.java

package linkedlist.queue;

public class LinkedListQueue {
	private QueueNode front = null;
	private QueueNode rear = null;
	
	private class QueueNode {
		private Object data;
		private QueueNode next;
		
		public QueueNode(Object input) {
			data = input;
			next = null;
		}
		
		public Object getData() {
			return this.data;
		}
	}
	
	public boolean isEmpty() {
		return front == null;
	}
	
	public void enqueue(Object input) {
		QueueNode newNode = new QueueNode(input);
		if(isEmpty()) {
			front = newNode;
			rear = newNode;
		} else {
			rear.next = newNode;
			rear = newNode;
		}
	}
	
	public Object dequeue() {
		if(isEmpty()) {
			throw new NullPointerException();
		} else {
			Object dequeueData = front.data;
			front = front.next;
			return dequeueData;
		}
	}
	
	public String toString() {
		String str = new String("[");
		if(isEmpty()) {
			return str + "]";
		} else {
			QueueNode tmp = front;
			
			while(tmp.next != null) {
				str += tmp.getData() +", ";
				tmp = tmp.next;
			}
			return str + tmp.getData() + "]";
		}
	}
	
	public void clear() {
		front = null;
		rear = null;
	}
}

참고

0개의 댓글