자바로 짜는 Queue

12 April 2018

Algorithm

지난번의 Stack에 이어 이번엔 Queue를 짜보았다. Queue는 선입선출 구조를 가지고 있으며 Stack을 손에 쥔 닭꼬치에 비유하자면 Queue는 놀이공원 대기줄이다. 선착순으로 먼저온 사람부터 차례차례 빠져 나간다. 물론 새치기는 예외 C언어로 배웠던 시절처럼 배열을 써볼까 했는데, Queue의 최대 크기가 제한되어버리는 데다가 dequeue할때 밀어주기 방식을 해야하기도 하고 뭔가 Java스럽지 않은것 같기도(?)해서 Stack을 구현할때와 유사하게 객체를 참조하는 구조로 짜 보았다. 대신 Queue는 맨 처음 Node와 맨 끝 Node를 특정해야 빼는 작업을 할 수 있으므로 Node 객체에 next 프로퍼티가 추가되었고 Queue 클래스에 frontNode, rearNode가 사용되었다. 뭐, 다 구현하고 나서 보니 연결리스트랑 다를바 없어 보인다.

Queue

Queue 개념도

Queue

발로 그려본 Queue 구조

public class Node
{
	private Object object;	//Data
	private Node prev;	//Previous Node
	private Node next;	//Next Node
	public Node(Object object, Node prev, Node next)
	{
		super();
		this.object = object;
		this.prev = prev;
		this.next = next;
	}
	public Object getObject()
	{
		return object;
	}
	public void setObject(Object object)
	{
		this.object = object;
	}
	public Node getPrev()
	{
		return prev;
	}
	public void setPrev(Node prev)
	{
		this.prev = prev;
	}
	public Node getNext()
	{
		return next;
	}
	public void setNext(Node next)
	{
		this.next = next;
	}
	@Override
	public String toString()
	{
		return "Node [object=" + object + ", prev=" + prev + ", next=" + next
				+ "]";
	}
}

public class Queue
{
	private int count;
	private Node frontNode;
	private Node rearNode;

	/**
	 * Default Constructor
	 * Intilalize parameters
	 */
	public Queue()
	{
		this.frontNode = null;
		this.rearNode = null;
		this.count = 0;
	}
	public boolean isEmpty()
	{
		return frontNode==null;
	}
	public int size()
	{
		return count;
	}
	public void enqueue(Object object)
	{
		if(isEmpty())
		{
			Node newNode = new Node(object, null, null);
			frontNode = newNode;
			rearNode = newNode;
			count++;
		}
		else
		{
			Node newNode = new Node(object, rearNode, null);
			if(size() == 1)
				frontNode.setNext(newNode);
			rearNode.setNext(newNode);
			rearNode = newNode;
			count++;
		}
		System.out.println("enqueue : "+object.toString()+" size : "+count);
	}
	public void dequeue()
	{
		if(isEmpty()) throw new NoSuchElementException("Queue is empty");
		else
		{
			count--;
			System.out.println("dequeue : "+frontNode.getObject().toString()+" size : "+count);
			Node newNode = frontNode.getNext();
			frontNode = newNode;
		}
	}
}

이 Queue에서 하는 일은 다음과 같다

  • isEmpty() : frontNode가 null일 경우 Empty
  • size() : Queue의 크기를 정수형으로 반환한다
  • enqueue(Object) : Queue에 데이터를 삽입한다. 삽입하는 방향은 구조에서 봤듯이 Rear쪽으로 들어간다
  • dequeue() : Queue에 데이터를 배출한다. 배출하는 방향은 Front

결과

public class Main
{
	public static void main(String[] args)
	{
		Queue queue = new Queue();
		queue.enqueue("A");
		queue.enqueue("B");
		queue.enqueue("C");
		queue.dequeue();
		queue.dequeue();
		queue.enqueue("D");
		queue.dequeue();
		queue.dequeue();
		queue.dequeue();
	}
}

enqueue : A size : 1
enqueue : B size : 2
enqueue : C size : 3
dequeue : A size : 2
dequeue : B size : 1
enqueue : D size : 2
dequeue : C size : 1
dequeue : D size : 0
Exception in thread "main" java.util.NoSuchElementException: Queue is empty
	at github.bobos.queue.Queue.dequeue(Queue.java:53)
	at github.bobos.queue.Main.main(Main.java:16)