큐 기본 구현

큐 기본구조

 

큐 삽입 (add)

//add at the rear
public void enqueue(T newElem) {
	// TODO Auto-generated method stub
	LLNode<T> newNode = new LLNode<>(newElem, null);
	if (rear == null)  //Boundary Case: Empty인 경우 rear.getNextN는 null이므로 아래의 statement를 수행할 필요가 없다
		front = newNode;
	else
		rear.setNextN(newNode);
	rear = newNode;
	size++;
}

 

 

큐 삭제 (poll)

/*poll(remove) at the front*/
@Override
public T dequeue() {

	if (rear == null) throw new IllegalStateException("Queue is Empty");
	T answer = front.getElem();
	front = front.getNextN();
	if (front == null)
		rear = null;
	size --;
	
	return answer;
}

 

 

전체코드

1. 노드

/**LinkedListQueue를 구현할 때, 각각의 "노드"를 나타내는 타입이 필요할 것임.
 * 1) 노드를 구성하는 필드 + 2) getter, setter*/
public class LLNode<T> {
	private LLNode<T> nextN;
	private T elem;
	
	public LLNode() { // 비어있는 노드
		// TODO Auto-generated constructor stub
		this(null, null);
	}
	public LLNode(T e, LLNode<T> n) {
		// TODO Auto-generated constructor stub
		elem = e;
		nextN = n;
	}
	
	public LLNode<T> getNextN() {
		return nextN;
	}
	public T getElem() {
		return elem;
	}
	public void setNextN(LLNode<T> newNext) {
		nextN = newNext;
	}
	public void setElem(T newElem) {
		elem = newElem;
	}
}

 

2. 큐

public class LinkedListQueue<T> {

	/*Field*/
	private LLNode<T> front;
	private LLNode<T> rear;
	private int size = 0;
	
	/*Default Constructor (Empty Queue)*/
	public LinkedListQueue() {
		front = null;
		rear = null;
	}
	/*add at the rear*/
	public void add(T newElem) {
		LLNode<T> newNode = new LLNode<>(newElem, null);
		if (rear == null)  //Boundary Case: Empty인 경우 rear.getNextN는 null이므로 아래의 statement를 수행할 필요가 없다
			front = newNode;
		else
			rear.setNextN(newNode);
		rear = newNode;
		size++;
	}

	/*poll(remove) at the front*/
	public T remove() {
		// TODO Auto-generated method stub
		if (rear == null) throw new IllegalStateException("Queue is Empty");
		T answer = front.getElem();
		front = front.getNextN();
		if (front == null)
			rear = null;
		size --;
		
		return answer;
	}

	public T peek() {
		return front.getElem();
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return (rear==null);
	}

}