ArrayList를 이용하여 Queue 구현하기
import java.util.ArrayList;
class MyQueue1 {
ArrayList list;
MyQueue1() {
this.list = new ArrayList();
}
public boolean isEmpty() {
if (this.list.size() == 0) {
return true;
} else {
return false;
}
}
public void push(int data) {
this.list.add(data);
}
public Integer pop() {
if (this.isEmpty()) {
System.out.println("Queue is empty");
return null;
}
int data = (int)this.list.get(0);
this.list.remove(0);
return data;
}
public Integer peek() {
if (this.isEmpty()) {
System.out.println("Queue is empty");
return null;
}
return (int)this.list.get(0);
}
public void printQueue() {
System.out.println(this.list);
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyQueue1 myQueue = new MyQueue1();
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
myQueue.push(4);
myQueue.push(5);
myQueue.printQueue(); // 1, 2, 3, 4, 5
System.out.println(myQueue.peek()); // 1
myQueue.printQueue(); // 1, 2, 3, 4, 5
System.out.println(myQueue.pop()); // 1
myQueue.printQueue(); // 2, 3, 4, 5
System.out.println(myQueue.pop()); // 2
myQueue.printQueue(); // 3, 4, 5
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
myQueue.printQueue();
}
}MyQueue1 클래스
- 멤버변수
ArrayList list;-ArrayList 타입의 list 멤버변수 선언
-이 요소는 Queue 의 요소를 저장
- 생성자
MyQueue1() {
this.list = new ArrayList();
}-MyQueue1 클래스의 생성자
-객체가 생성될 때마다 ArrayList를 초기화하여 빈 Queue를 생성
- isEmpty() 메서드
public boolean isEmpty() {
if (this.list.size() == 0) {
return true;
} else {
return false;
}
}-Queue가 비어있는지 여부를 확인하는 메서드
-list.size() 가 0이면 Queue가 비어있으므로 true를 반환
- push(int data) 메서드
public void push(int data) {
this.list.add(data);
}-Queue에 데이터를 추가하는 메서드
-list.add(data) 를 호출하여 데이터를 Queue의 맨 끝에 추가
- pop() 메서드
public Integer pop() {
if (this.isEmpty()) {
System.out.println("Queue is empty");
return null;
}
int data = (int)this.list.get(0);
this.list.remove(0);
return data;
}-Queue 의 맨 앞에서 데이터를 제거하고 반환하는 메서드
-Queue가 비어있으면 메세지를 출력하고 null을 반환
-그렇지 않으면 list.get(0) 으로 첫번째 요소를 가져온 후, list.remove(0) 로 제거하고 해당 데이터를 반환
6.peek() 메서드
public Integer peek() {
if (this.isEmpty()) {
System.out.println("Queue is empty");
return null;
}
return (int)this.list.get(0);
}-Queue의 맨 앞에 있는 데이터를 제거하지 않고 반환하는 메서드
-Queue가 비어있으면 메세지를 출력하고 null을 반환
-그렇지 않으면 list.get(0) 으로 첫번째 요소를 반환
7.printQueue 메서드
public void printQueue() {
System.out.println(this.list);
}-현재 Queue의 모든 요소를 출력하는 메서드
배열을 이용해 원형 Queue 구현하기
class MyQueue2 {
int[] arr;
int front = 0;
int rear = 0;
MyQueue2(int size) {
arr = new int[size + 1];
}
public boolean isEmpty() {
return this.rear == this.front;
}
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}
public void enqueue(int data) {
if (this.isFull()) {
System.out.println("Queue is full");
return;
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;
}
public Integer dequeue() {
if (this.isEmpty()) {
System.out.println("Queue is empty");
return null;
}
front = (front + 1) % this.arr.length;
return this.arr[front];
}
public void printQueue() {
int start = (this.front + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for (int i = start; i != end; i = (i + 1) % this.arr.length) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyQueue2 myQueue = new MyQueue2(5);
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
myQueue.enqueue(4);
myQueue.enqueue(5);
myQueue.enqueue(6); // Queue is full!
myQueue.printQueue(); // 1, 2, 3, 4, 5
System.out.println(myQueue.dequeue()); // 1
myQueue.printQueue(); // 2, 3, 4, 5
System.out.println(myQueue.dequeue()); // 2
myQueue.printQueue(); // 3, 4, 5
myQueue.enqueue(6);
myQueue.enqueue(7);
myQueue.printQueue(); // 3, 4, 5, 6, 7
System.out.println(myQueue.dequeue()); // 3
System.out.println(myQueue.dequeue()); // 4
System.out.println(myQueue.dequeue()); // 5
myQueue.printQueue(); // 6, 7
System.out.println(myQueue.dequeue()); // 6
System.out.println(myQueue.dequeue()); // 7
myQueue.dequeue(); // Queue is empty!
}
}MyQueue2 클래스
- 멤버 변수
int[] arr;
int front = 0;
int rear = 0;-arr : Queue의 데이터를 저장할 배열
-front : Queue의 가장 앞 위치를 가리킴
-rear : Queue의 가장 뒤 위치를 가리킴
- 생성자
MyQueue2 (int size) {
arr = new int[size + 1];-Queue 의 크기를 설정하는 생성자
-size + 1로 배열을 생성하는 이유는 원형 큐에서 큐가 꽉 찬 상태와 빈 상태를 구별하기 위함
- isEmpty 메서드
public boolean isEmpty() {
return this.rear == this.front;
}-Queue가 비어있는지 확인
-rear 과 front가 같으면 큐가 비어있는 상태
- isFull() 메서드
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}-Queue가 가득찼는지 확인
-(rear + 1) % arr.length가 front와 같으면 Queue가 가득 찬 상태
- enqueue(int data) 메서드
public void enqueue(int data) {
if (this.isFull()) {
System.out.println("Queue is full");
return;
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;-Queue에 데이터를 추가
-Queue가 가득 차 있으면 메세지를 출력
-rear을 한칸 앞으로 이동하고, 데이터를 해당 위치에 저장
- dequeue() 메서드
public Integer dequeue() {
if (this.isEmpty()) {
System.out.println("Queue is empty");
return null;
}
front = (front + 1) % this.arr.length;
return this.arr[front];
}-Queue에서 데이터를 제거하고 반환
-Queue가 비어있으면 메세지를 출력하고 null을 반환
front를 한칸 앞으로 이동하고 해당위치의 데이터를 반환
7.printQueue() 메서드
public void printQueue() {
int start = (this.front + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for (int i = start; i != end; i = (i + 1) % this.arr.length) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}-Queue의 모든 요소를 출력
-front와 rear 사이의 요소를 출력
-원형 Queue이므로 인덱스가 배열의 끝을 넘어가면 처음으로 돌아감
Hello World