Queue 큐 ( JAVA )

 

Queue 큐

 

---

Queue 란 ?

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다.

스택과는 반대되는 개념이다.

 

큐의 탐색에는 O(N) 만큼의 시간이 걸리고 삽입/삭제에는 O(1) 만큼의 시간이 소요된다.

 

 

구현

Queue를 직접 구현해본다.

배열과 리스트를 이용할 수 있는데 리스트로 큐의 삽입과 삭제를 구현해보겠다.

 

먼저 큐를 구현하기 위해 Node 클래스를 생성한다.

static class Node{
		int val;
		Node next;
		public Node(int val) {
			this.val = val;
			next = null;
		}
	}
	
	static Node head;
	

 

다음으로는 Node 클래스를 활용하여 삽입을 구현해보자

삽입을 하는 메소드 이름은 Enqueue로 명명하겠다.

• 삽입하려는 값을 매개 변수로 받는다.
• 새로운 Node 객체를 생성하고 매개 변수로 들어온 값으로 초기화를 진행한다.
• 큐가 비어있다면 head에 그렇지 않다면 맨 마지막 위치를 탐색하여 그 곳에 값을 추가해준다.

static void Enqueue(int val) {
		Node newNode = new Node(val);
		
		if(head == null) {
			head = newNode;
		}else {
			Node tail = head;
			while(tail.next !=null) tail = tail.next;
			tail.next = newNode;
		}
	}

 

마지막으로 큐의 삭제를 구현해보자.

삭제 메소드 이름은 Dequeue로 명명하겠다.

• 큐가 비어있다면 -1을 반환해준다. (예외처리)
• 가장 앞의 Node를 임시 저장해두고 head를 현재 head의 next로 변경해준다.
• 임시 저장해둔 값을 반환해준다.

static int Dequeue() {
		if(head == null) return -1;
		Node target = head;
		head = head.next;
		return target.val;
	}

---

 

cpdm