제3장 자료구조

1. 제3장 자료구조
   1. 3.7 큐
   2. 문서에 대하여

3.7 큐

설명

3.7.1 순차자료구조 방식을 이용한 큐의 예

public class ArrayQueue {
	private int front;
	private int rear;
	private int arrayQueueSize;
	private String arrayQueueList[];
	
	public ArrayQueue(int arrayQueueSize){
		this.front	= -1;
		this.rear	= -1;	
		this.arrayQueueList = new String[arrayQueueSize];
		this.arrayQueueSize = arrayQueueSize;
	}
	
	public boolean isFull() {
		return (rear == arrayQueueSize -1 );
	}
	
	public boolean isEmpty(){
		return (front == rear);
	}

	public void enQueue(String s){
		
		if(isFull())
			System.out.println("길이 " + arrayQueueSize +" 로 생성된 큐가 가득찼습니다");
		else{
			arrayQueueList[++rear] = s;		 
			System.out.println("enQueue : " + s + " 가 저장 되었습니다.");
		}
	}
	
	
	public void deQueue() {
		if(isEmpty())
			System.out.println("길이 " + arrayQueueSize +" 로 생성된 큐가 비었습니다.");
		else{
			arrayQueueList[++front] = "";
			System.out.println("deQueue 돠었습니다.");
		}
	}
	
	public void print() {
		while( isEmpty()) {
			System.out.println("arrayQueueList["+ front +"] = " + arrayQueueList[front]);
			++front;
		}
	}
}


public class ArrayQueueMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		ArrayQueue aq = new ArrayQueue(10);
		
		for(int i=1; i<=15; i++)
			aq.enQueue(""+i);

	
		for(int i=1; i<=15; i++)
			aq.deQueue();	
	}
}

3.7.2 순차자료 방식의 단순 큐 개선 환형큐

public class CircleArrayQueue {

	private int front;
	private int rear;
	private int queueSize;
	private String circleArrayQueueList[];
	
	public CircleArrayQueue(int queueSize) {
		// TODO Auto-generated constructor stub
		this.front	= 0;
		this.rear	= 0;		
		this.queueSize = queueSize;
		circleArrayQueueList = new String[queueSize];
	}
	
	public boolean isEmpty() {
		return (front == rear);		
	}
	
	public boolean isFull() {
		return ((rear + 1) % this.queueSize) == front;		
	}
	
	public void enQueue(String s) {
		
		if(isFull())
			System.out.println("사이즈가 " + this.queueSize + "인 큐가 가득 찼습니다.");
		else{
			rear = (rear + 1) % this.queueSize;
			circleArrayQueueList[rear] = s;
			System.out.println("circleArrayQueueList 에 " + s + "가 저장되었습니다.");
		}			
	}
	
	public String deQueue() {
		String rtnVal = "";
		
		if(isEmpty())
			rtnVal = "큐가 비었습니다.";
		else{
			front =((front + 1) % this.queueSize);
			rtnVal = circleArrayQueueList[front];
		}
		return rtnVal;
	}
}



class CircleArrayQueueMain {
	public static void main(String[] args) {
		
		CircleArrayQueue caq =  new CircleArrayQueue(10);
		
		for(int i=1; i<=15; i++)
			caq.enQueue(""+i);
		
		for(int i=1; i<=15; i++)
			System.out.println(caq.deQueue());
	}
}

3.7.3 연결자료구조 방식을 이용한 큐의 예

public class QueueNode {

	public String data = null;
	public QueueNode link =  null;
	
	public QueueNode(){
		this.data = null;
		this.link = null;
	}
	
	public QueueNode(String data) {
		this.data =  data;
	}
}


public class LinkedListQueue {
	private QueueNode head = null;
	private QueueNode tail = null;
	int length = 0;
	
	public boolean isEmpty(){
		boolean rtnVal = false;
		if(this.length < 1) rtnVal = true;
		return rtnVal;
	}

	public void push(String data) {
		QueueNode newQueueNode = new QueueNode(data);
		System.out.println(data + "가 큐에 저장되었습니다.");
		
		if(isEmpty()) {
			this.head = newQueueNode;
		}else{
			this.tail.link = newQueueNode;
		}
		
		this.tail = newQueueNode;
		this.length++;
	}
	
	public String pop() {
		String rtnVal = "";
		
		if (isEmpty()) {
			rtnVal = "큐가 비었습니다.";
		}else{
			QueueNode tmpNode =  this.head;
			rtnVal = tmpNode.data + " 가 큐에서 출력되었습니다.";
			
			if (this.length == 1) {
				this.head = null;
				this.tail = null;
			}else{
				this.head = tmpNode.link;
				tmpNode.link = null;
			}
			this.length--;
		}
		
		return rtnVal;
	}
}


public class LinkedListQueueMain {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		LinkedListQueue llq = new LinkedListQueue();
//		lls.pop();
		
		for(int i=1 ; i < 10; i ++){
			llq.push(" " + i);
		}
		
		while (llq.length > 0) {
			System.out.println(llq.pop());

		}
		
		for(int i=1 ; i < 10; i ++){
			System.out.println(llq.pop());
		}
		
	}
}

3.7.4 연결자료구조 방식을 이용한 큐의 예(2)

큐와 비슷하지만 노드에 2개의 링크가 존재 하며 큐의 양쪽끝 모두 에서 입력삭제가 가능한 자료구조 (DECK) 구현

public class DoubleLinkedListDeck {
	private DQueueNode front;
	private DQueueNode rear;
	private int length;
	
	public DoubleLinkedListDeck() {
		this.front = null;
		this.rear = null;
		this.length = 0;		
	}

	public boolean isEmpty() {
		return this.front == null;
	}
	
	public int getLength() {
		return length;
	}
	
	public void insertFront(String data) {
		DQueueNode newNode = new DQueueNode(data);
		if (isEmpty()) {
			this.front = newNode;
			this.rear = newNode;
			newNode.nextNode = null;
			newNode.prevNode = null;
		}else{
			this.front.prevNode = newNode;
			newNode.nextNode = this.front;
			newNode.prevNode = null;
			this.front = newNode;
		}
		
		System.out.println("DECK 에 insertFront()로 \" " + data + " \" 가 입력되었습니다.");
	}
	
	public String deleteFront(){
		String rtnVal="";
		
		if (isEmpty()) 
			rtnVal = "DoubleLinkedListDeck 이 비었습니다";
		else{
			rtnVal = this.front.data + " 가 DoubleLinkedListDeck 에서 deleteFront() 로 삭제되었습니다.";
			if(this.front.nextNode == null){
				this.front = null;
				this.rear = null;
			}else{
				this.front.nextNode.prevNode = null;
				this.front = front.nextNode;				
				// this.front = front.nextNode;
				// this.front.prev = null;
			}
		}
		return rtnVal;
	}
	
	public void insertRear(String data) {
		DQueueNode newNode = new DQueueNode(data);
		if (isEmpty()) {
			this.front = newNode;
			this.rear = newNode;
			newNode.nextNode = null;
			newNode.prevNode = null;
		}else{
			this.rear.nextNode = newNode;
			newNode.nextNode = null;
			newNode.prevNode = this.rear;
			this.rear = newNode;
		}
	}
	
	public String deleteRear(){
		String rtnVal = "";
		if (isEmpty()) 
			rtnVal = "DoubleLinkedListDeck 이 비었습니다";
		else{
			rtnVal = this.rear.data + " 가 DoubleLinkedListDeck 에서 deleteRear() 로 삭제되었습니다.";
			if (this.rear.prevNode == null) {
				this.front = null;
				this.rear = null;				
			}else{
				this.rear.prevNode.nextNode = null;
				this.rear = rear.prevNode;				
			}
		}		
		return rtnVal;
	}
	
}



public class DoubleLinkedListDeckMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		DoubleLinkedListDeck dlld = new DoubleLinkedListDeck();
		dlld.deleteFront();
		dlld.deleteRear();
		
		for(int i=1; i < 10; i++){
			dlld.insertFront(" " + i);
		}

		for(int i=1; i < 15; i++){
			//System.out.println(dlld.deleteRear());
			System.out.println(dlld.deleteFront());
		}
	}

}

문서에 대하여

• 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
• 최초작성자 : 허용운
• 최초작성일 : 2009년 2월 25일
• 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
• 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^