[CS 자료구조] 큐에 대한 내용

큐

• 선입선출(FIFO)
• 처음에 들어온 데이터가 처음에 나간다.

 

배열에서의 큐

class ArrayQueue {
	private int front;
	private int rear;
	private int queueSize;
	private char itemArray[];
	
	public ArrayQueue(int queueSize){
		front = -1;
		rear = -1;
		this.queueSize = queueSize;
		itemArray = new char[this.queueSize];
	}
	
	public boolean isEmpty(){
		return (front == rear);
	}
	
	public boolean isFull(){
		return (rear == this.queueSize-1);
	}
	
	public void enQueue(char item){
		
		if(isEmpty()) {
			front = -1;
			rear = -1;
		}
		
		if(isFull()){
			System.out.println("Inserting fail! Array Queue is full!!");
		}
		else{ 			
			itemArray[++rear] = item;
			System.out.println("Inserted Item : " + item);
		}
	}
	
	public char deQueue(){
		
		if(isEmpty()) {
			System.out.println("Deleting fail! Array Queue is empty!!");
			return 0;
		}
		else{ 
			return itemArray[++front];	
		}
				
	}
	
	public void printQueue(){
		if(isEmpty())
			System.out.printf("Array Queue is empty!! %n %n");
		else{
			System.out.printf("Array Queue>> ");
			for(int i=front+1; i<=rear; i++)
				System.out.printf("%c ", itemArray[i]);
			System.out.println();System.out.println();
		}
	}

}

public class Main{
	public static void main(String args[]){
		int queueSize = 3;
		char deletedItem;
		ArrayQueue Q = new ArrayQueue(queueSize);
		
		Q.enQueue('A'); // Inserted Item : A
		Q.printQueue(); // Array Queue>> A 
		
		Q.enQueue('B'); // Inserted Item : B
		Q.printQueue(); // Array Queue>> A B 
		
		deletedItem = Q.deQueue();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem); // deleted Item : A
		}
		Q.printQueue(); // Array Queue>> B 
		
		Q.enQueue('C'); // Inserted Item : C
		Q.printQueue(); // Array Queue>> B C 
		
		deletedItem = Q.deQueue();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem); // deleted Item : B
		}
		Q.printQueue(); // Array Queue>> C 

		deletedItem = Q.deQueue();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem); // deleted Item : C
		}
		Q.printQueue(); // Array Queue is empty!! 
		
		deletedItem = Q.deQueue(); // Deleting fail! Array Queue is empty!!
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem);
		}
		Q.printQueue();	// Array Queue is empty!! 
	}
}

 

 

리스트에서의 큐

interface Queue{
	boolean isEmpty();
	void enQueue(char item);
	char deQueue();
	void delete();
	char peek();
}

class QNode{
	char data;
	QNode link;
}

class LinkedQueue implements Queue{
	QNode front;
	QNode rear;
		
	public LinkedQueue(){
		front = null;
		rear = null;		
	}
	
	public boolean isEmpty(){
		return (front == null);
	}
	
	public void enQueue(char item){
		QNode newNode = new QNode();
		newNode.data = item;
		newNode.link = null;
		if(isEmpty()){
			front = newNode;
			rear = newNode;
		}
		else {
			rear.link = newNode;
			rear = newNode;			
		}
		System.out.println("Inserted Item : " + item);
	}
	
	public char deQueue(){
		if(isEmpty()) {
			System.out.println("Deleting fail! Linked Queue is empty!!");
			return 0;
		}
		else{ 
			char item = front.data;
			front = front.link;
			if(front == null)
				rear = null;
			return item;
		}				
	}
	
	public void delete(){
		if(isEmpty()){
			System.out.println("Deleting fail! Linked Queue is empty!!");			
		}
		else {
			front = front.link;
			if(front == null)
				rear = null;
		}
	}
	
	public char peek(){
		if(isEmpty()){
			System.out.println("Peeking fail! Linked Queue is empty!!");
			return 0;
		}
		else 
			return front.data;		
	}
	
	public void printQueue(){
		if(isEmpty())
			System.out.printf("Linked Queue is empty!! %n %n");
		else{
			QNode temp = front;
			System.out.printf("Linked Queue>> ");
			while(temp != null){
				System.out.printf("%c ", temp.data);
				temp = temp.link;
			}
			System.out.println();System.out.println();
		}
	}
}

public class Main{
	public static void main(String args[]){		
		char deletedItem;
		LinkedQueue LQ = new LinkedQueue();
		
		LQ.enQueue('A'); // Inserted Item : A
		LQ.printQueue(); // Linked Queue>> A 
		
		LQ.enQueue('B'); // Inserted Item : B
		LQ.printQueue(); // Linked Queue>> A B 
		
		deletedItem = LQ.deQueue();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem); // deleted Item : A
		}
		LQ.printQueue(); // Linked Queue>> B 
		
		LQ.enQueue('C'); // Inserted Item : C
		LQ.printQueue(); // Linked Queue>> B C 
		
		deletedItem = LQ.deQueue();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem); // deleted Item : B
	    }
		LQ.printQueue(); // Linked Queue>> C 

		deletedItem = LQ.deQueue();
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem); // deleted Item : C
		}
		LQ.printQueue(); // Linked Queue is empty!! 
		
		deletedItem = LQ.deQueue(); // Deleting fail! Linked Queue is empty!!
		if(deletedItem != 0) {
			System.out.println("deleted Item : " + deletedItem);
		}
		LQ.printQueue(); // Linked Queue is empty!! 
	}
}

 

 

출처)

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95