큐(Queue)

• 큐는 선입선출(FIFO) 구조의 자료구조이다.

선형 큐

배열을 이용한 선형 큐 구현

public class CircularQueue
{
	private int front;
	private int rear;
	private int queueSize;
	private char itemArray[];
	
	public CircularQueue(int queueSize)
	{
		front = 0;
		rear = 0;
		this.queueSize = queueSize;
		itemArray = new char[this.queueSize];
	}
	
	public boolean isEmpty()
	{
		return (front == rear);
	}

	public boolean isFull()
	{
		return ((rear+1)%this.queueSize == front);
	}
	
	public void enQueue(char item)
	{
		if(isFull())
		{
			System.out.println("queue full!");
		}
		else
		{
			rear = (rear + 1) % this.queueSize;
			itemArray[rear] = item;
		}
	}

	public char deQueue()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
			return 0;
		}
		else
		{
			front = (front + 1)%this.queueSize;
			return itemArray[front];
		}
	}

	public void delete()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
		}
		else
		{
			front = (front+1)%this.queueSize;
		}
	}

	public char peek()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
			return 0;
		}
		else
		{
			return itemArray[(front+1)%this.queueSize];
		}
	}

	public void printQueue()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
		}
		else
		{
			System.out.print("Array circular queue >> ");
			for(int i = (front+1)%this.queueSize; i != (rear+1)%this.queueSize; i = ++i % this.queueSize)
			{
				System.out.printf("%c ", itemArray[i]);
			}
			System.out.println();
			System.out.println();
		}
	}
}

• 생성자 CircularQueue(int queueSize) : 배열의 크기를 인자로 받아, 초기 큐를 생성한다.
• isEmpty() : 큐가 비었는지 확인한다.
• isFull() : 큐가 모두 찼는지 확인한다.
• enQueue(char item) : 큐에 자료를 삽입한다.
• deQueue() : 큐에서 자료를 꺼내고, 큐에서 자료를 삭제한다.
• delete() : 큐에서 자료를 삭제한다.
• peek() : 큐에서 자료를 꺼낸다.

리스트를 이용한 선형 큐 구현

원형 큐

배열을 이용한 원형 큐 구현

public class CircularQueue
{
	private int front;
	private int rear;
	private int queueSize;
	private char itemArray[];
	
	public CircularQueue(int queueSize)
	{
		front = 0;
		rear = 0;
		this.queueSize = queueSize;
		itemArray = new char[this.queueSize];
	}
	
	public boolean isEmpty()
	{
		return (front == rear);
	}

	public boolean isFull()
	{
		return ((rear+1)%this.queueSize == front);
	}
	
	public void enQueue(char item)
	{
		if(isFull())
		{
			System.out.println("queue full!");
		}
		else
		{
			rear = (rear + 1) % this.queueSize;
			itemArray[rear] = item;
		}
	}

	public char deQueue()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
			return 0;
		}
		else
		{
			front = (front + 1)%this.queueSize;
			return itemArray[front];
		}
	}

	public void delete()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
		}
		else
		{
			front = (front+1)%this.queueSize;
		}
	}

	public char peek()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
			return 0;
		}
		else
		{
			return itemArray[(front+1)%this.queueSize];
		}
	}

	public void printQueue()
	{
		if(isEmpty())
		{
			System.out.println("queue empty!");
		}
		else
		{
			System.out.print("Array circular queue >> ");
			for(int i = (front+1)%this.queueSize; i != (rear+1)%this.queueSize; i = ++i % this.queueSize)
			{
				System.out.printf("%c ", itemArray[i]);
			}
			System.out.println();
			System.out.println();
		}
	}
}

• 원형 큐는 index를 mod 연산을 이용하여 처리한다는 점이 선형 큐와 다르다.

덱(Deque)

• 덱은 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로써, 스택의 성질과 큐의 성질을 모두 가지고 있는 자료구조다.

참고문헌

[자바로 배우는 쉬운 자료구조] ,한빛아카데미