선형데이터구조, 큐(Queue) #3 배열/연결리스트 기반 큐 구현

1. 배열 기반 큐 특징

• 배열 기반이기 때문에 큐의 크기가 고정적임
• 큐 구조의 제일 앞쪽과 제일 뒤쪽을 나타내는 인덱스가 필요함(front, rear)
• 삽입과 삭제시 연산이 복잡함

 

2. 배열 기반 큐 구현

public class Queue {
	int front, rear, size;
	int capacity;
	int array[];

	public Queue(int capacity)
	{
		this.capacity = capacity;
		front = this.size = 0;
		rear = capacity - 1;
		array = new int[this.capacity];
	}

	// 큐가 가득찼는지 검사
	boolean isFull(Queue queue)
	{
		return (queue.size == queue.capacity);
	}

	// 큐가 비어있는지 검사
	boolean isEmpty(Queue queue)
	{
		return (queue.size == 0);
	}

	// 큐에 데이터를 삽입 (rear와 size 값이 변경됨)
	void enqueue(int item)
	{
		if (isFull(this))
			return;
		this.rear = (this.rear + 1)
					% this.capacity;
		this.array[this.rear] = item;
		this.size = this.size + 1;
		System.out.println(item
						+ " enqueued to queue");
	}

	// 큐에 데이터를 제거 및 반환(front와 size 값이 변경됨)
	int dequeue()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		int item = this.array[this.front];
		this.front = (this.front + 1)
					% this.capacity;
		this.size = this.size - 1;
		return item;
	}

	// 큐의 제일 앞쪽 데이터 반환
	int front()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		return this.array[this.front];
	}

	// 큐의 제일 뒤쪽 데이터 반환
	int rear()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		return this.array[this.rear];
	}
}

 

3. 연결리스트 기반 큐 특징

• 연결리스트 기반이기 때문에 큐의 크기가 동적임
• 큐의 앞쪽과 뒤쪽을 나타내는 포인터를 가지고 있음 (head, tail)
• 삽입과 삭제 연산이 간단함

 

4. 연결리스트 기반 큐 구현

public class QueueAsLinkedList {
	Node head, tail;
	int numOfData;
	
	static class Node{
		int data;
		Node next;
		
		public Node(int data) {
			this.data = data;
			this.next = null;
		}
	}

	public QueueAsLinkedList()
	{
		head = tail = null;
		numOfData = 0;
	}
	
	// 큐에 데이터를 삽입
	public void enqueue(int item)
	{
		Node newNode = new Node(item);
		
		if(head == null) {
			head = tail = newNode;
		}
		else
		{
			tail.next = newNode;
			tail = newNode;
		}
		
		numOfData++;
	}
	
	// 큐에 데이터를 제거 및 반환
	int dequeue()
	{
		if (isEmpty()) {
			return Integer.MIN_VALUE;
		}
		
		int item = head.data;
		
		if(numOfData == 1) {
			head = tail = null;
		}
		else{
			head = head.next;
		}
		
		numOfData--;
				
		return item;
	}
	
	// 큐가 비어있는지 검사
	public boolean isEmpty()
	{
		return (numOfData == 0);
	}
	
	// 큐의 제일 앞쪽 데이터 반환
	int front()
	{
		if (isEmpty()) {
			return Integer.MIN_VALUE;
		}
		
		return head.data;
	}

	// 큐의 제일 뒤쪽 데이터 반환
	int rear()
	{
		if (isEmpty()) {
			return Integer.MIN_VALUE;
		}
		
		return tail.data;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Node cur = head;
		while(cur != null)
		{
			sb.append(cur.data+" ");
			cur = cur.next;
		}
		return sb.toString().trim();
	}
	
	
}

 

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Queue/Implement