Home Queue
Post
Cancel

Queue

Posted Nov 1, 2022 Updated Nov 1, 2022
By haedal-uni
16 min read

큐(Queue)

큐는 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO : 선입선출, First In First Out)을 지닌 자료 구조이며,

나중에 집어 넣은 데이터가 먼저 나오는 스택과 반대되는 개념을 가졌다.

삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.


image

Enqueue : 큐 맨 뒤에 데이터 추가

Dequeue : 큐 맨 앞쪽의 데이터 삭제





기본연산

  • front : deQueue 할 위치 기억
  • rear : enQueue 할 위치 기억



image



enQueue()

image

  • 데이터를 넣는 연산
  • 데이터가 들어오면 rear는 새로 들어온 데이터가 된다. (R -> R’)



dnQueue()

image

  • 데이터를 빼는 연산
  • 데이터가 나가면 front는 다음 데이터가 된다. (F -> F’)



isEmpty()

image

  • 데이터가 비었는지 확인
  • front == rear



isFull()

image

  • 데이터가 꽉 차있는지 확인
  • rear == QueueSize



Peek()

  • 가장 첫번째 데이터를 반환하되 삭제는 하지 않는다.
  • 다음 출력 값이 미리 알아보는 역할





자바 속 Queue

Queue 선언

1
2

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

자바에서 큐는 LinkedList를 활용하여 생성해야한다.

(가장 대중적이고, 배열로 구현하는 큐에 비해 쉬운편)



Queue Interface에 선언 할 메소드

  • 추가(enqueue) : Queue명.offer(값);

  • 추가(enqueue) : Queue명.add(값);
    큐가 꽉 차서 추가할 수 없는 경우에는 에러가 출력

  • 삭제(dequeue) : Queue명.remove();

  • 삭제(dequeue) : Queue명.poll();
    값을 반환하고 제거. 큐가 비어있으면 null을 반환

  • 검사 : Queue명.peek();
  • 검사 : Queue명.element();
    다음에 출력될 값을 확인
    Queue에서 다 뽑아내거나 Queue가 비어있으면 에러가 출력



1
2
3
4
5
6
7

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
    queue.offer(1);     // queue에 값 1 추가
    queue.offer(2);     // queue에 값 2 추가
    queue.offer(3);     // queue에 값 3 추가
    queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
    queue.remove();     // queue에 첫번째 값 제거
    queue.clear();      // queue 초기화

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i <= 10; i++) {
            queue.offer(i);
        }
        
        while(!queue.isEmpty()) {
            int element = queue.poll();
            System.out.println(element);
        }
    }
}

1 2 3 4 5 6 7 8 9 10 순서대로 출력된다.





코드

큐의 구조는 한쪽에서는 삽입만 일어나고 한쪽에서는 삭제만 하는 자료구조다.

→ 먼저 들어간 것이 먼저 나오는 FIFO 구조 ex) 줄서기, 프린터 출력 등등


즉, 큐는 항상 첫 번재 저장된 데이터를 삭제하므로,

ArrayList와 같은 배열 기반의 자료구조를 사용하게 되면 빈공간을 채우기 위해서 데이터의 복사가 발생하므로 매우 비효율적이다.

그래서 Queue는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.



LinkedList
LinkedList를 기반으로 Queue를 구현하기에 앞서 가장 기본적인 데이터를 담을 Node 클래스를 먼저 구현한다.



Node

1
2
3
4
5
6
7
8
9

class Node<E> {
    E data;
    Node<E> next;    // 다음 노드를 가리키는 역할을 하는 변수
	
    Node(E data) {
        this.data = data;
        this.next = null;
    }
}




interface

1
2
3
4
5
6
7
8
9
10
11
12

// 자바 Queue Interface
// Queue는 ArrayQueue, LinkedQueue, Deque, PriorityQueue 에 의해 구현
 
public interface Queue<E> {

    boolean offer(E e);

    E poll();

    E peek();
	
}
  • boolean offer(E e); : 큐의 가장 마지막에 요소를 추가
    • @param : e 큐에 추가할 요소
    • @return : 큐에 요소가 정상적으로 추가되었을 경우 true를 반환
  • E poll(); : 큐의 첫 번째 요소를 삭제하고 삭제 된 요소를 반환
    • @return : 큐의 삭제 된 요소 반환
  • E peek(); : 큐의 첫 번째 요소를 반환
    • @return : 큐의 첫 번째 요소 반환




Queue 클래스 및 생성자 구성하기

1
2
3
4
5
6
7
8
9
10
11
12

public class LinkedListQueue<E> implements Queue<E> {
 
    private Node<E> head;
    private Node<E> tail;
    private int size;
	
    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}
  • head : 큐에서 가장 앞에있는 노드 객체를 가리키는 변수
  • tail : 큐에서 가장 뒤에있는 노드 객체를 가리키는 변수
  • size : 큐에 담긴 요소의 개수


처음 큐를 생성할 때는 아무런 데이터가 없으므로 head와 tail은 가리킬 노드가 없는상태이므로 null로 초기화해주고,

size 또한 0으로 초기화 해준다.




offer() : 데이터 추가

Queue에 데이터를 추가하는 메소드(맨 뒤에 데이터 추가)

*리스트로 치면 add(E value)와 같은 역할


기본 삽입 : offer(E item) _ 가장 마지막 부분에 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

@Override
public boolean offer(E value) {
    Node<E> newNode = new Node<E>(value);
		
    // 비어있을 경우 
    if(size == 0) {
        head = newNode;
    }
    // 그 외의 경우 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 한다.
    else {
        tail.next = newNode;
    }
	
    // tail이 가리키는 노드를 새 노드로 바꿔준다.
    tail = newNode;
    size++;
    
    return true;
}

큐에 아무 요소들이 없을 때. 즉 size가 0일 때는 새 요소가 head이자 tail이 된다.

그렇기 때문에 큐가 비어있을 경우에는 head를 새 노드를 가리키도록 해야하고 그 외에는 이미 요소가 있다는 의미이므로

tail이 가리키는 요소의 다음 노드(tail.next)를 새 노드를 가리키도록 한 뒤 tail이 가리키는 노드를 새 노드를 가리키도록 한다.




데이터 삭제

리스트에서의 remove()와 같은 역할로 가장 앞에있는 위치에 있는 요소인 head 요소를 삭제하면 된다.

remove() 같은 경우 삭제 할 요소가 없으면 NoSuchElementException() 예외를 던진다.

반대로 poll()의 경우는 삭제 할 요소가 없다면 null을 반환한다는 차이점이 있다.

1. poll()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

@Override
public E poll() {
		
    // 삭제할 요소가 없을 경우 null 반환
    if(size == 0) {
        return null;
    }
		
    // 삭제될 요소의 데이터를 반환하기 위한 임시 변수 
    E element = head.data;
		
    // head 노드의 다음노드
    Node<E> nextNode = head.next;
		
    // head의 모든 데이터들을 삭제 
    head.data = null;
    head.next = null;
		
    // head 가 가리키는 노드를 삭제된 head노드의 다음노드를 가리키도록 변경 
    head = nextNode;
    size--;
		
    return element;
}



2. remove()

1
2
3
4
5
6
7
8
9
10

public E remove() {
		
    E element = poll();
		
    if(element == null) {
        throw new NoSuchElementException();
    }
		
    return element;
}




조회

가장 앞에 있는 데이터(head.data)를 삭제하지 않고 확인만 하고싶을 때 쓰인다.

poll() 메소드에서 삭제과정만 없는 것이 peek() 이다.

1. peek()

1
2
3
4
5
6
7
8
9

@Override
public E peek() {	
		
	// 요소가 없을 경우 null 반환
    if(size == 0) {
        return null;
    }
    return head.data;
}

head의 데이터를 그대로 반환하기만 하면 된다.



2. element()

1
2
3
4
5
6
7
8
9

public E element() {
		
    E element = peek();
		
    if(element == null) {
        throw new NoSuchElementException();
    }
    return element;
}

peek() 메소드로 데이터를 얻은 뒤, 얻은 요소가 null 이라면 예외를 던진다.




그 외 메소드

size()

현재 큐에 있는 요소의 개수를 알려준다.

1
2
3

public int size() {
    return size;
}




isEmpty()

현재 큐가 비어있는지를 확인 할 때 쓰인다.

요소의 개수가 0개라면 비어있다는 뜻이므로, 비어있다면 true를, 비어있지 않다면 false를 반환한다.

1
2
3

public boolean isEmpty() {
    return size == 0;	
}




contains()

현재 찾고자하는 요소가 큐에 들어가있는지를 알려주는 메소드

1
2
3
4
5
6
7
8
9
10
11

public boolean contains(Object value) {
		
    // head 데이터부터 x가 null이 될 때까지 value랑 x의 데이터(x.data)랑
    // 같은지를 비교하고 같을 경우 true를 반환한다.
    for(Node<E> x = head; x != null; x = x.next) {
        if(value.equals(x.data)) {
        return true;
        }
    }
    return false;
}




clear()

Queue의 모든 요소를 비워버린다.

1
2
3
4
5
6
7
8
9
10

public void clear() {
    for (Node<E> x = head; x != null; ) {
        Node<E> next = x.next;
        x.data = null;
        x.next = null;
        x = next;
    }
    size = 0;
    head = tail = null;
}

이 때는 모든 데이터를 명시적으로 null 처리를 해주는 것이 좋다.

그리고 빈 공간은 초기 상태와 마찬가지로 head 와 tail와 size 모두 0으로 초기화 해준다.




전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

public class LinkedListQueue<E> implements Queue<E> {
	private Node<E> front;
	private Node<E> rear;
	private int size;

	public LinkedListQueue() { // 초기화
		this.front = null;
		this.rear = null;
		this.size = 0;
	}

	@Override
	public boolean enQueue(E value) {
		Node<E> newNode = new Node<E>(value);

		if (size == 0) { // 큐가 비어있을 경우
			front = newNode; // 새 요소가 head이자 tail이 된다.
		}

		// 그 외의 경우 마지막 노드(rear)의 다음 노드(next)가 새 노드를 가리키도록 한다.
		else {
			rear.next = newNode;
		}

		// rear이 가리키는 노드를 새 노드로 바꿔준다.
		rear = newNode;
		size++;
		return true;
	}

	
	
	// 삭제
	@Override
	public E poll() { // 삭제할 요소가 없을 경우 null 반환
		if (size == 0) {
			return null;
		}

		// 삭제될 요소의 데이터를 반환하기 위한 임시 변수
		E element = front.data;

		// head 노드의 다음노드
		Node<E> nextNode = front.next;

		// head의 모든 데이터들을 삭제
		front.data = null;
		front.next = null;

		// front 가 가리키는 노드를 삭제된 front 노드의 다음노드를 가리키도록 변경
		front = nextNode;
		size--;
		return element;
	}

	public E remove() { // 삭제할 요소가 없으면 예외 발생
		E element = poll();
		if (element == null) {
			throw new NoSuchElementException();
		}
		return element;
	}

	
	
	
	// 조회  
	@Override
	public E peek() {
		// 요소가 없을 경우 null 반환
		if (size == 0) {
			return null;
		}
		return front.data;
	}

	public E element() { 
		E element = peek();
		if (element == null) {
			throw new NoSuchElementException();
		}
		return element;
	}

	
	
	
	// 기타 메소드 
	public int size() { // 요소 개수
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public boolean contains(Object value) {
		// front 데이터부터 x가 null이 될 때까지 value랑 x의 데이터(x.data)랑
		// 같은지를 비교하고 같을 경우 true를 반환한다.
		for (Node<E> x = front; x != null; x = x.next) {
			if (value.equals(x.data)) {
				return true;
			}
		}
		return false;
	}

	public void clear() {
		for (Node<E> x = front; x != null; ) {
			Node<E> next = x.next;
			x.data = null;
			x.next = null;
			x = next;
		}
		// 초기화
		size = 0;
		front = rear = null;
	}

	
	
	public static void main(String[] args) {
		LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
		queue.enQueue(5);
		System.out.println(queue.peek());

		queue.enQueue(1);
		System.out.println(queue.peek());

		queue.enQueue(1);

		queue.enQueue(3);

		queue.remove();
		System.out.println(queue.peek());

		System.out.println(queue.size());
		System.out.println(queue.contains(5));

		queue.clear();
		System.out.println(queue.size());
		System.out.println(queue.poll());

	}

}

image




출처
[Java]Queue가 ArrayList 대신 LinkedList를 사용하는 이유
자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기

Study
Data-Structure study summary
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents