본문 바로가기
공부기록/알고리즘

Chapter 04-2. 스택과 큐_큐란

by 루팽 2024. 8. 4.

큐(queue)

스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)

큐에 데이터를 넣는 작업 인큐(en-queue), 데이터를 꺼내는 작업 디큐(de-queue)

 

int형 고정 길이 큐(링 버퍼 사용하지 않고 구현)

package ch04_2;
 
// int형 고정 길이 큐(링 버퍼 사용하지 않고 구현)
public class IntArrayQueue {
    private int[] que; // 큐용 배열
    private int capacity; // 큐 용량
    private int num; // 현재 데이터 개수
 
    // 실행 시 예외 - 큐가 비어있음
    public class EmptyIntArrayQueueException extends RuntimeException {
        public EmptyIntArrayQueueException() {
        }
    }
 
    // 실행 시 예외 - 큐가 가득 참
    public class OverflowIntArrayQueueException extends RuntimeException {
        public OverflowIntArrayQueueException() {
        }
    }
 
    // 생성자
    public IntArrayQueue(int maxlen) {
        num = 0;
        capacity = maxlen;
        try {
            que = new int[capacity]; // 큐 본체용 배열 생성
        } catch (OutOfMemoryError error) { // 생성할 수 없음
            capacity = 0;
        }
    }
 
    // 큐에 데이터를 인큐
    public int enque(int x) throws OverflowIntArrayQueueException {
        if (num >= capacity) throw new OverflowIntArrayQueueException(); // 큐가 가득참
        que[num++] = x;
        return x;
    }
 
    // 큐에 데이터를 디큐
    public int deque() throws EmptyIntArrayQueueException {
        if (num <= 0) throw new EmptyIntArrayQueueException(); // 큐가 비어있음
        int x = que[0];
        for (int i = 0; i < num - 1; i++) {
            que[i] = que[i + 1];
        }
        num--;
        return x;
    }
 
    // 큐에서 데이터를 피크(맨앞 데이터 들여다봄)
    public int peek() throws EmptyIntArrayQueueException {
        if (num <= 0) throw new EmptyIntArrayQueueException(); // 큐가 비어있음
        return que[num - 1];
    }
 
    // 큐에서 x를 검색하여 인덱스(없으면 -1) 반환
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            if (que[i] == x) return i; // 검색 성공
        }
        return -1; // 검색 실패
    }
 
    // 큐 비우기
    public void clear() {
        num = 0;
    }
 
    // 큐 용량 반환
    public int capacity() {
        return capacity;
    }
 
    // 큐에 쌓여있는 데이터수 반환
    public int size() {
        return num;
    }
 
    // 큐가 비어 있는가
    public boolean isEmpty() {
        return num <= 0;
    }
 
    // 큐가 가득 찼는가
    public boolean isFull() {
        return num >= capacity;
    }
 
    // 큐 안의 모든 데이터를 맨앞부터 끝까지 순서대로 출력
    public void dump() {
        if (num <= 0) {
            System.out.println("큐가 비어 있습니다.");
        } else {
            for (int i = 0; i < num; i++) {
                System.out.print(que[i] + " ");
            }
            System.out.println();
        }
    }
}

 

int형 고정 길이 큐(링 버퍼를 사용하지 않고 구현)의 사용 예

package ch04_2;
 
import java.util.Scanner;
 
// int형 고정 길이 큐(링 버퍼를 사용하지 않고 구현)의 사용 예
public class Ex01_intArrayQueueTester {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntArrayQueue s = new IntArrayQueue(64); // 최대 64개를 푸시할 수 있는 큐
 
        while (true) {
            System.out.println("현재 데이터 개수: " + s.size() + " / " + s.capacity());
            System.out.print("(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: ");
 
            int menu = scanner.nextInt();
            if(menu == 0) break;
 
            int x = 0;
            switch (menu) {
                case 1 -> { // 인큐
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    try {
                        s.enque(x);
                    } catch (IntArrayQueue.OverflowIntArrayQueueException e) {
                        System.out.println("큐가 가득 찼습니다.");
                    }
                }
 
                case 2 -> { // 디큐
                    try {
                        x = s.deque();
                        System.out.println("디큐한 데이터는 " + x + "입니다.");
                    } catch (IntArrayQueue.EmptyIntArrayQueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 3 -> { // 피크
                    try {
                        x = s.peek();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (IntArrayQueue.EmptyIntArrayQueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 4 -> { // 덤프
                    s.dump();
                }
            }
        }
    }
}
/*
현재 데이터 개수: 0 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: 1
데이터: 10
현재 데이터 개수: 1 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: 1
데이터: 5
현재 데이터 개수: 2 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: 1
데이터: 92
 
현재 데이터 개수: 3 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: 2
디큐한 데이터는 10입니다.
 
현재 데이터 개수: 2 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: 3
피크한 데이터는 92입니다.
 
현재 데이터 개수: 2 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(0) 종료: 4
5 92
 */

 

int형 고정 길이 큐

package ch04_2;
 
// int형 고정 길이 큐
public class IntQueue {
    private int[] que; // 큐용 배열
    private int capacity; // 큐의 용량
    private int front; // 맨 앞의 요소 커서
    private int rear; // 맨 뒤의 요소 커서
    private int num; // 현재 데이터 개수
 
    // 실행시 예외 - 큐가 비어 있음
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() {
        }
    }
 
    // 실행시 예외 - 큐가 가득 참
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() {
        }
    }
 
    // 생성자
    public IntQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity]; // 큐 본체용 배열 생성
        } catch (OutOfMemoryError e) { // 생성할 수 없음
            capacity = 0;
        }
    }
 
    // 큐에 데이터를 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= capacity) throw new OverflowIntQueueException(); // 큐가 가득 참
        que[rear++] = x;
        num++;
        if (rear == capacity) {
            // 배열 용량(마지막 인덱스)과 같아지면 첫 인덱스로 변경
            rear = 0;
        }
        return x;
    }
 
    // 큐에 데이터를 디큐
    public int deque() throws EmptyIntQueueException {
        if (num <= 0) throw new EmptyIntQueueException(); // 큐가 비어 있음
        int x = que[front++];
        num--;
        if (front == capacity) {
            // 배열 용량(마지막 인덱스)과 같아지면 첫 인덱스로 변경
            front = 0;
        }
        return x;
    }
 
    // 큐 데이터 피크(프런트 데이터 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if (num <= 0) throw new EmptyIntQueueException(); // 큐가 비어 있음
        return que[front];
    }
 
    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }
 
    // 큐에서 x 검색하여 인덱스(없으면 -1) 반환
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if (que[idx] == x) return idx; // 검색 성공
        }
        return -1; // 검색 실패
    }
 
    // 큐 용량 반환
    public int getCapacity() {
        return capacity;
    }
 
    // 큐 데이터 개수 반환
    public int size() {
        return num;
    }
 
    // 큐가 비어 있는가
    public boolean isEmpty() {
        return num <= 0;
    }
 
    // 큐가 가득 찼는가
    public boolean isFull() {
        return num >= capacity;
    }
 
    // 큐 안의 모든 데이터를 프런트->리어 순으로 출력
    public void dump() {
        if (num <= 0) {
            System.out.println("큐가 비어 있습니다.");
        } else {
            for (int i = 0; i < num; i++) {
                System.out.print(que[(i + front) % capacity] + " ");
            }
            System.out.println();
        }
    }
}

 

int형 고정 길이 큐의 사용 예

package ch04_2;
 
import java.util.Scanner;
 
// int형 고정 길이 큐의 사용 예
public class Ex02_intQueueTester {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntQueue s = new IntQueue(64); // 최데 64개를 인큐할 수 있는 큐
 
        while (true) {
            System.out.println();
            System.out.printf("현재 데이터 개수: %d / %d\\n", s.size(), s.getCapacity());
            System.out.print("(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: ");
 
            int menu = scanner.nextInt();
            if (menu == 0) break;
 
            int x;
            switch (menu) {
                case 1 -> { // 인큐
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    try {
                        s.enque(x);
                    } catch (IntQueue.OverflowIntQueueException e) {
                        System.out.println("큐가 가득 찼습니다.");
                    }
                }
 
                case 2 -> { // 디큐
                    try {
                        x = s.deque();
                        System.out.println("디큐한 데이터는 " + x + "입니다.");
                    } catch (IntQueue.EmptyIntQueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 3 -> { // 피크
                    try {
                        x = s.peek();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (IntQueue.EmptyIntQueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 4 -> { // 덤프
                    s.dump();
                }
            }
        }
    }
}
/*
현재 데이터 개수: 0 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: 1
데이터: 1
현재 데이터 개수: 1 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: 1
데이터: 2
 
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: 4
1 2 
 
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: 2
디큐한 데이터는 1입니다.
 
현재 데이터 개수: 1 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (0)종료: 3
피크한 데이터는 2입니다.
 */

 

int형 고정 길이 큐(메서드 search 추가)

// 큐에서 x 검색하여 맨앞에서 몇번째(없으면 0)인지 반환
    public int search(int x) {
        for (int i = 0; i < num; i++) {
            if (que[(i + front) % capacity] == x) {
                return i + 1; // 검색 성공
            }
        }
        return 0; // 검색 실패
    }

 

int형 고정 길이 큐의 사용 예(메서드 search 추가)

package ch04_2;
 
import java.util.Scanner;
 
// int형 고정 길이 큐의 사용 예(메서드 search 추가)
public class Ex03_intQueueTester2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntQueue2 s = new IntQueue2(64); // 최데 64개를 인큐할 수 있는 큐
 
        while (true) {
            System.out.println();
            System.out.printf("현재 데이터 개수: %d / %d\\n", s.size(), s.getCapacity());
            System.out.print("(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: ");
 
            int menu = scanner.nextInt();
            if (menu == 0) break;
 
            int x;
            switch (menu) {
                case 1 -> { // 인큐
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    try {
                        s.enque(x);
                    } catch (IntQueue.OverflowIntQueueException e) {
                        System.out.println("큐가 가득 찼습니다.");
                    }
                }
 
                case 2 -> { // 디큐
                    try {
                        x = s.deque();
                        System.out.println("디큐한 데이터는 " + x + "입니다.");
                    } catch (IntQueue.EmptyIntQueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 3 -> { // 피크
                    try {
                        x = s.peek();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (IntQueue.EmptyIntQueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 4 -> { // 덤프
                    s.dump();
                }
 
                case 5 -> { // 검색
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    int n = s.search(x);
                    if(n != 0) {
                        System.out.printf("%d번째 데이터로 인덱스%d의 위치에 저장되어 있습니다.\\n", n, s.indexOf(x));
                    } else {
                        System.out.println("그 데이터는 등록되어 있지 않습니다.");
                    }
                }
            }
        }
    }
}
/*
현재 데이터 개수: 0 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 1
데이터: 1
현재 데이터 개수: 1 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 1
데이터: 6
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 1
데이터: 9
 
현재 데이터 개수: 3 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 4
1 6 9
 
현재 데이터 개수: 3 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 2
디큐한 데이터는 1입니다.
 
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 3
피크한 데이터는 6입니다.
 
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)덤프 (5)검색 (0)종료: 5
데이터: 9
2번째 데이터로 인덱스2의 위치에 저장되어 있습니다.
 */

 

제네릭 큐

package ch04_2;
 
// 제네릭 큐
public class Queue<E> {
    // 실행 시 예외 - 큐가 비어 있음
    public static class EmptyGqueueException extends RuntimeException {
        public EmptyGqueueException() {}
    }
 
    // 실행 시 예외 - 큐가 가득 참
    public static class OverflowGqueueException extends RuntimeException {
        public OverflowGqueueException() {}
    }
 
    private E[] que; // 큐 본체
    private int capacity; // 큐 용량
    private int num; // 현재 데이터 개수
    private int front; // 맨앞 요소 커서
    private int rear; // 맨끝 요소 커서
 
    // 생성자
    public Queue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = (E[]) new Object[capacity]; // 큐 본체용 배열 생성
        } catch (OutOfMemoryError e) { // 생성할 수 없음
            capacity = 0;
        }
    }
 
    // 큐에 데이터를 인큐
    public E enque(E x) throws OverflowGqueueException {
        if(num >= capacity) throw new OverflowGqueueException(); // 큐가 가득 참
        que[rear++] = x;
        num ++;
        if(rear == capacity) rear = 0;
        return x;
    }
 
    // 큐에서 데이터를 디큐
    public E deque() throws EmptyGqueueException {
        if(num <= 0) throw new EmptyGqueueException(); // 큐가 비어 있음
        E x = que[front++];
        num--;
        if(front == capacity) front = 0;
        return x;
    }
 
    // 큐에서 데이터 피크(맨 앞 데이터 들여다봄)
    public E peek() throws EmptyGqueueException {
        if(num <= 0) throw new EmptyGqueueException(); // 큐가 비어 있음
        return que[front];
    }
 
    // 큐에서 x 검색하여 인덱스(없으면 -1) 반환
    public int indexOf(E x) {
        for (int i = 0; i < num; i++) {
            if (que[(i + front) % capacity].equals(x)) {
                return (i + front) % capacity; // 검색 성공
            }
        }
        return -1; // 검색 실패
    }
 
    // 큐에서 x 검색하여 맨앞에서 몇번째인지(없으면 -1) 반환
    public int search(E x) {
        for (int i = 0; i < num; i++) {
            if(que[(i + front) % capacity].equals(x)) {
                return i + 1; // 검색 성공
            }
        }
        return -1; // 검섹 실패
    }
 
    // 큐 비우기
    public void clear() {
        num = front = rear = 0;
    }
 
    // 큐 용량 반환
    public int getCapacity() {
        return capacity;
    }
 
    // 큐 데이터 수 반환
    public int size() {
        return num;
    }
 
    // 큐가 비어 있는가
    public boolean isEmpty() {
        return num <= 0;
    }
 
    // 큐가 가득 찼는가
    public boolean isFull() {
        return num >= capacity;
    }
 
    // 큐의 모든 데이터를 맨앞부터 맨끝까지 출력
    public void dump() {
        if(num <= 0) {
            System.out.println("큐가 비어 있습니다.");
        } else {
            for (int i = 0; i < num; i++) {
                System.out.print(que[(i + front) % capacity].toString() + " ");
            }
            System.out.println();
        }
    }
}

 

제네릭 큐 테스트 프로그램

package ch04_2;
 
import java.util.Scanner;
 
// 제네릭 큐 테스트 프로그램
public class Ex04_queueTester {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Queue<String> s = new Queue<>(64); // 최대 64개 넣을 수 있는 큐
 
        while (true) {
            System.out.printf("현재 데이터 개수: %d / %d\\n", s.size(), s.getCapacity());
            System.out.print("(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : ");
 
            int menu = scanner.nextInt();
            if(menu == 0) break;
 
            int idx;
            String x;
 
            switch (menu) {
                case 1 -> { // 인큐
                    System.out.print("데이터: ");
                    x = scanner.next();
                    try {
                        s.enque(x);
                    } catch (Queue.OverflowGqueueException e) {
                        System.out.println("큐가 가득 찼습니다.");
                    }
                }
 
                case 2 -> { // 디큐
                    try {
                        x = s.deque();
                        System.out.println("디큐한 데이터는 " + x + "입니다.");
                    }catch (Queue.EmptyGqueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 3 -> { // 피크
                    try {
                        x = s.peek();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (Queue.EmptyGqueueException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 4 -> { // 덤프
                    s.dump();
                }
 
                case 5 -> { // 검색
                    System.out.print("데이터: ");
                    String str = scanner.next();
                    int n = s.search(str);
                    if(n != 0) {
                        System.out.printf("%d번째 데이터로, 인덱스 %d의 위치에 저장되어 있습니다.\\n", n, s.indexOf(str));
                    } else {
                        System.out.println("그 데이터는 등록되어 있지 않습니다.");
                    }
                }
            }
        }
    }
}
/*
현재 데이터 개수: 0 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 1
데이터: Q
현재 데이터 개수: 1 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 1
데이터: W
현재 데이터 개수: 2 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 1
데이터: E
현재 데이터 개수: 3 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 1
데이터: R
 
현재 데이터 개수: 4 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 3
피크한 데이터는 Q입니다.
 
현재 데이터 개수: 4 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 2
디큐한 데이터는 Q입니다.
 
현재 데이터 개수: 3 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 4
W E R
 
현재 데이터 개수: 3 / 64
(1) 인큐　(2) 디큐　(3) 피크　(4) 덤프　(5) 검색 (0) 종료 : 5
데이터: E
2번째 데이터로, 인덱스 2의 위치에 저장되어 있습니다.
 */

 

int형 고정 길이 덱

package ch04_2;
 
// int형 고정 길이 덱
public class IntDeque {
 
    // 실행 시 예외 - 큐가 비어 있음
    public class EmptyIntDequeException extends RuntimeException {
        public EmptyIntDequeException() {
        }
    }
 
    // 실행 시 예외 - 큐가 가득 참
    public class OverflowIntDequeException extends RuntimeException {
        public OverflowIntDequeException() {
        }
    }
 
    private int[] que; // 덱 본체
    private int capacity; // 덱 용량
    private int num; // 현재 데이터 개수
    private int front; // 맨 앞 요소 커서
    private int rear; // 맨 끝 요소 커서
 
    // 생성자
    public IntDeque(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity]; // 덱 본체용 배열 생성
        } catch (OutOfMemoryError error) { // 생성할 수 없음
            capacity = 0;
        }
    }
 
    // 덱 맨앞에 데이터 인큐
    public int enqueFront(int x) throws OverflowIntDequeException {
        if (num >= capacity) throw new OverflowIntDequeException(); // 덱이 가득 참
        num++;
        if (--front < 0) {
            front = capacity - 1;
        }
        que[front] = x;
        return x;
    }
 
    // 덱 맨끝에 데이터 인큐
    public int enqueRear(int x) throws OverflowIntDequeException {
        if (num >= capacity) throw new OverflowIntDequeException(); // 덱이 가득 참
        que[rear++] = x;
        num++;
        if (rear == capacity) {
            rear = 0;
        }
        return x;
    }
 
    // 덱의 맨앞 데이터 디큐
    public int dequeFront() throws EmptyIntDequeException {
        if (num <= 0) throw new EmptyIntDequeException(); // 덱이 비어있음
        int x = que[front++];
        num--;
        if (front == capacity) {
            front = 0;
        }
        return x;
    }
 
    // 덱의 맨끝 데이터 디큐
    public int dequeRear() throws EmptyIntDequeException {
        if (num <= 0) throw new EmptyIntDequeException(); // 덱이 비어있음
        num--;
        if (--rear < 0) {
            rear = capacity - 1;
        }
        return que[rear];
    }
 
    // 맨앞 데이터 들여다봄
    public int peekFront() throws EmptyIntDequeException {
        if (num <= 0) throw new EmptyIntDequeException(); // 덱이 비어있음
        return que[front];
    }
 
    // 맨끝 데이터 들여다봄
    public int peekRear() throws EmptyIntDequeException {
        if (num <= 0) throw new EmptyIntDequeException(); // 덱이 비어있음
        return que[rear == 0 ? capacity - 1 : rear - 1];
    }
 
    // 덱에서 x 검색해 인덱스(없으면 -1) 반환
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if (que[idx] == x) return idx; // 검색 성공
        }
        return -1; // 검색 실패
    }
 
    // 덱에서 x 검색해 맨앞에서 몇번째인지(없으면 0) 반환
    public int search(int x) {
        for (int i = 0; i < num; i++) {
            if (que[(i + front) % capacity] == x) return i + 1; // 검색 성공
        }
        return 0; // 검색 실패
    }
 
    // 덱 비우기
    public void clear() {
        num = front = rear = 0;
    }
 
    // 덱 용량 반환
    public int getCapacity() {
        return capacity;
    }
 
    // 덱에 쌓여있는 데이터 수 반환
    public int size() {
        return num;
    }
 
    // 덱이 비어 있는가
    public boolean isEmpty() {
        return num <= 0;
    }
 
    // 덱이 가득 찼는가
    public boolean isFull() {
        return num >= capacity;
    }
 
    // 덱 안의 모든 데이터를 맨앞부터 맨끝까지 출력
    public void dump() {
        if(num <= 0) {
            System.out.println("덱이 비어 있습니다.");
        } else {
            for (int i = 0; i < num; i++) {
                System.out.println(que[(i + front) % capacity] + " ");
            }
            System.out.println();
        }
    }
}

 

int형 고정길이 덱의 테스트 프로그램

package ch04_2;
 
import java.util.Scanner;
 
// int형 고정길이 덱의 테스트 프로그램
public class Ex05_intDequeTester {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntDeque s = new IntDeque(64); // 최대 64개 넣을 수 있는 큐
 
        while (true) {
            System.out.printf("현재 데이터 개수 : %d / %d\\n", s.size(), s.getCapacity());
            System.out.print("(1)맨앞에  인큐　(2)맨앞에서  디큐　(3)맨앞에서 피크\\n" +
                    "(4)맨끝에  인큐　(5)맨끝에서  디큐　(6)맨끝에서 피크\\n" +
                    "(7)덤프　(8)검색　(0) 종료 : ");
 
            int menu = scanner.nextInt();
            if(menu == 0) break;
 
            int x = 0;
 
            switch (menu) {
                case 1 -> { // 맨앞에 인큐
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    try {
                        s.enqueFront(x);
                    } catch (IntDeque.OverflowIntDequeException e) {
                        System.out.println("큐가 가득 찼습니다.");
                    }
                }
 
                case 2 -> { // 맨앞에 디큐
                    try {
                        x = s.dequeFront();
                        System.out.println(" 디큐한 데이터는 " + x + "입니다.");
                    } catch (IntDeque.EmptyIntDequeException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 3 -> { // 맨앞에서 피크
                    try {
                        x = s.peekFront();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (IntDeque.EmptyIntDequeException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 4 -> { // 맨뒤에 인큐
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    try {
                        s.enqueRear(x);
                    } catch (IntDeque.OverflowIntDequeException e) {
                        System.out.println("큐가 가득 찼습니다.");
                    }
                }
 
                case 5 -> { // 맨뒤에 디큐
                    try {
                        x = s.dequeRear();
                        System.out.println(" 디큐한 데이터는 " + x + "입니다.");
                    } catch (IntDeque.EmptyIntDequeException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 6 -> { // 맨뒤에 피크
                    try {
                        x = s.peekRear();
                        System.out.println("피크한 데이터는 " + x + "입니다.");
                    } catch (IntDeque.EmptyIntDequeException e) {
                        System.out.println("큐가 비어 있습니다.");
                    }
                }
 
                case 7 -> { // 덤프
                    s.dump();
                }
 
                case 8 -> { // 검색
                    System.out.print("데이터 : ");
                    x = scanner.nextInt();
                    int n = s.search(x);
                    if(n != 0) {
                        System.out.printf("%d번째 데이터로 인덱스%d의 위치에 저장되어 있습니다.\\n", n, s.indexOf(x));
                    } else {
                        System.out.println("그 데이터는 등록되어 있지 않습니다.");
                    }
                }
            }
        }
    }
}

 

원하는 개수만큼 값 입력받고, 요솟수가 N인 배열에 마지막 N개 저장

package ch04_2;
 
import java.util.Scanner;
 
// 원하는 개수만큼 값 입력받고, 요솟수가 N인 배열에 마지막 N개 저장
public class Ex06_lastNElements {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int N = 10;
        int[] a = new int[N]; // 입력받은 값을 저장
        int cnt = 0; // 입력받은 개수
        int retry; // 다시시작
 
        System.out.println("정수를 입력하세요.");
 
        do {
            System.out.printf("%d번째 정수: ", cnt + 1);
            a[cnt++ % N] = scanner.nextInt();
 
            System.out.print("계속 할까요? (예.1 / 아니요.0): ");
            retry = scanner.nextInt();
        } while (retry == 1);
 
        int i = cnt - N;
        if(i < 0) i = 0;
 
        for (; i < cnt; i++) {
            System.out.printf("%2d번째 정수 = %d\\n", i + 1, a[i % N]);
        }
    }
}
/*
정수를 입력하세요.
1번째 정수: 15
2번째 정수: 17
3번째 정수: 64
4번째 정수: 57
5번째 정수: 99
6번째 정수: 21
7번째 정수: 0
8번째 정수: 23
9번째 정수: 44
10번째 정수: 55
11번째 정수: 97
12번째 정수: 85
 
 3번째 정수 = 64
 4번째 정수 = 57
 5번째 정수 = 99
 6번째 정수 = 21
 7번째 정수 = 0
 8번째 정수 = 23
 9번째 정수 = 44
10번째 정수 = 55
11번째 정수 = 97
12번째 정수 = 85
 */
저작자표시 비영리 변경금지 (새창열림)

'공부기록 > 알고리즘' 카테고리의 다른 글

Chapter 05-2. 재귀 알고리즘_재귀 알고리즘 분석  (0) 2024.08.11
Chapter 05-1. 재귀 알고리즘_재귀 알고리즘의 기본  (0) 2024.08.11
Chapter 04-1. 스택과 큐_스택이란  (0) 2024.08.04
Chapter 03-3. 검색 알고리즘_이진 검색  (0) 2024.08.04
Chapter 03-2. 검색 알고리즘_선형 검색  (0) 2024.08.04

관련글

댓글

티스토리툴바