728x90
⬛ Queue 개념
- 한쪽 방향(Rear)에서는 자료의 삽입이, 다른 한 쪽 방향(Front)에서는 자료의 삭제가 이루어지는 FIFO(First In First Out) 형식의 자료 구조
- Queue의 가장 먼저 들어온 요소를 Front, 가장 늦게 들어온 요소를 Rear라고 부르며 이 두가지 요소에 의해서만 접근이 가능
- Rear에서 이루어지는 삽입 연산을 ‘enQueue’, Front에서 이루어지는 삭제 연산을 ‘deQueue’라고 한다.
⬛ Queue 연산
1. enQueue(int data) : Rear에 데이터를 추가
2. deQueue() : Front에 있는 데이터를 반환 후 삭제
3. peek() : Front에 있는 데이터를 반환 (삭제 x)
⬛ Queue 활용
- 프로세스 스케줄링
- 프린터 출력
- 은행 번호표
- 너비 우선 탐색 알고리즘
⬛ Queue 구현
MyQueue.java
더보기
더보기
package com.queue;
public class MyQueue {
private Node front;
private Node rear;
private int size = 0;
private void enQueue(int data) {
Node new_node = new Node(data);
if (isEmpty()) {
front = new_node;
rear = new_node;
} else {
rear.setNext(new_node);
rear = new_node;
}
size++;
}
private int deQueue() {
if (isEmpty()) {
System.out.print("Stack Underflow ");
return -1;
}
int data = front.getData();
front = front.getNext();
if (front == null) {
rear = null;
}
size--;
return data;
}
private int peek() {
if (isEmpty()) {
System.out.print("No item ");
return -1;
}
return front.getData();
}
private boolean isEmpty() {
if (size == 0) {
return true;
}
return false;
}
private int size() {
return size;
}
@Override
public String toString() {
if (isEmpty()) {
return "Queue is empty";
}
String str = "[";
Node temp = front;
while (temp.getNext() != null) {
str += temp.getData();
str += ", ";
temp = temp.getNext();
}
str += temp.getData();
return str + "]";
}
public static void main(String[] args) {
MyQueue mq = new MyQueue();
mq.enQueue(0);
mq.enQueue(1);
mq.enQueue(2);
mq.enQueue(3);
mq.enQueue(4);
mq.enQueue(5);
System.out.println(mq);
System.out.println(mq.peek());
System.out.println(mq.deQueue());
System.out.println(mq.deQueue());
System.out.println(mq.deQueue());
System.out.println(mq.deQueue());
System.out.println(mq.deQueue());
System.out.println(mq.deQueue());
System.out.println(mq.size());
System.out.println(mq);
}
}
Node.java
더보기
더보기
package com.queue;
public class Node {
private int data;
private Node next;
Node(int data) {
setData(data);
setNext(null);
}
Node() {
setNext(null);
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
728x90
'공부의 기록 > Data Structure' 카테고리의 다른 글
[자료 구조] Tree & Binary Tree의 개념 설명 (0) | 2022.03.02 |
---|---|
[자료 구조] Hash의 개념 설명 (0) | 2022.02.11 |
[자료 구조] Heap의 개념 설명과 구현 (0) | 2022.02.03 |
[자료 구조] Stack 개념 설명과 구현(배열, 연결리스트) (0) | 2022.01.31 |
[자료 구조] LinkedList 개념 설명과 구현 (0) | 2022.01.31 |