[Java 자료구조] 큐 구현해보기

큐(Queue) 구현해보기

연결 리스트 구현한 MyLinkedList를 활용하여 큐를 구현해본다. 큐의 연산에는 데이터를 rear의 위치에 넣는 enQueue() 메서드와 front 위치의 데이터를 출력하는 deQueue() 메서드가 있다.

 

MyLinkedQueue.java

package ch05;

import ch03.MyLinkedList;
import ch03.MyListNode;

interface Queue{
	public void enQueue(String data);
	public String deQueue();
	public void printQueue();
}

public class MyLinkedQueue extends MyLinkedList implements Queue{
	
	MyListNode front;
	MyListNode rear;
	
	@Override
	public void enQueue(String data) {
		
		MyListNode newNode;
		
		if(isEmpty()) {	// 맨 처음 요소로 들어가는 경우
			newNode = addElement(data);
			front = newNode;
			rear = newNode;
		}
		
		else {
			newNode = addElement(data);
			rear = newNode;
		}
		
		System.out.println(newNode.getData() + " added");
	}

	@Override
	public String deQueue() {
		
		if(isEmpty()) {
			System.out.println("Queue is empty");
			return null;
		}
			String data = front.getData();
			front = front.next;
			
			if( front == null ) {	// 마지막 항목
				rear = null;
		}
		return data;
	}
	
	@Override
	public void printQueue() {
		printAll();
	}
}

 

MyListQueueTest.java

package ch05;

public class MyListQueueTest {

	public static void main(String[] args) {
		
		MyLinkedQueue queue = new MyLinkedQueue();
		queue.enQueue("A");
		queue.enQueue("B");
		queue.enQueue("C");
		
		queue.printAll();
		
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
		
	}

}

 

수행 결과

스택과 달리 입력 순서대로 출력되는 것을 볼 수 있다.

A added
B added
C added
A->B->C
A
B