큐 (1)

JAVA/JAVA 기초

자바에서 Stack과 Queue 배열로 구현하기

 

 

 

 

자료구조에서 중요한 개념인 Stack과 Queue를 코드로 직접 구현해보았다.

 

'Doit! 자료구조와 함께 배우는 알고리즘 입문 자바편'을 참고하여 작성하였습니다.

 

 

❑ 자바에서 Stack 배열로 구현하기

 

더보기 
public class IntStack {
    private int[] stk;  // 스택용 배열
    private int capacity;   // 스택 용량
    private  int ptr;   // 스택 포인터
 
    // 실행시 예외: 스택이 비어있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException(){};
    }
 
    // 실행시 예외: 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException(){};
    }
 
    // 생성자
    public IntStack(int maxlen) {
        ptr = 0;
        capacity = maxlen;
        try {
            stk = new int[capacity];
        } catch (OutOfMemoryError e) {
            capacity = 0;
        }
    }
 
    // 스택에 x push
    public int push(int x) throws OverflowIntStackException {
        if(ptr >= capacity) {
            throw new OverflowIntStackException();
        }
        return stk[ptr++] = x;
    }
 
    // 스택에서 데이터를 pop
    public int pop() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }
 
    // 스택에서 데이터를 peek
    public int peek() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[ptr - 1];
    }
 
    // 스택을 비움
    public void clear() {
        ptr = 0;
    }
 
    // 스택에서 x를 찾아 인덱스(없으면 -1)을 반환
    public int indexOf(int x) {
        for(int i = ptr - 1; i >= 0; i--) {
            if (stk[i] == x)
                return i;
        }
        return -1;
    }
 
    // 스택의 용량 반환
    public int getCapacity() {
        return capacity;
    }
 
    // 스택에 쌓여 있는 데이터 개수를 반환
    public int size() {
        return ptr;
    }
 
    // 스택이 비어있는가?
    public boolean isEmpty() {
        return ptr <= 0;
//        return ptr == 0; 으로도 가능
    }
 
    // 스택이 가득 찼는가?
    public boolean isFull() {
        return ptr >= capacity;
    }
 
    // 스택 안의 모든 데이터를 bottom-> top 순서로 출력
    public void dump() {
        if(ptr <= 0) {
            System.out.println("Stack is Empty!");
        }
        else {
            for(int i = 0; i < ptr; i++)
                System.out.print(stk[i]+ " ");
            System.out.println();
        }
    }
}

 

 

❑ Stack 클래스 테스트 하기

 

더보기 
import java.util.Scanner;
 
public class IntStackTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        IntStack s = new IntStack(64);
 
        while(true) {
            System.out.println();
            System.out.printf("present data count: %d / %d\n", s.size(), s.getCapacity());
            System.out.print("(1)push (2)pop (3)peek (4)dump (5)clear (6)getCapacity (7)indexOf (8)isFull (0)exit  : ");
 
            int menu = stdIn.nextInt();
 
            if(menu == 0) break;    //exit
 
            int x;
            switch(menu) {
                case 1 :    // push
                    System.out.print("데이터: ");
                    x = stdIn.nextInt();
                    try {
                        s.push(x);
                    }catch (IntStack.OverflowIntStackException e) {
                        System.out.println("Stack is full!!");
                    }
                    break;
                case 2:     // pop
                    try {
                        x = s.pop();
                        System.out.println("pop data is " + x + ".");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("Stack is Empty!!");
                    }
                    break;
                case 3:     // peek
                    try {
                        x = s.peek();
                        System.out.println("peek data is " + x + ".");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("Stack is Empty!!");
                    }
                    break;
                case 4:     // dump
                    s.dump();
                    break;
                case 5:     // clear
                    s.clear();
                    break;
                case 6:     // getCapacity
                    System.out.println("Capacity : " + s.getCapacity());
                    break;
                case 7:     //indexOf
                    System.out.print("input you want to find : ");
                    x = stdIn.nextInt();
                    System.out.println(x + " is in " + s.indexOf(x));
                    break;
                case 8:
                    System.out.println("Stack is Full? " + s.isFull());
                    break;
            }
 
        }
    }
}

 

 

 

❑ 자바에서 Queue 배열로 구현하기

더보기 
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;
    }
 
    // 큐에서 데이터를 피크(front 데이터를 들여다봄)
    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 int search(int x) {
        for(int i = 0; i < num; i++) {
            if(que[(i + front) % capacity] == x)
                return i + 1;
        }
        return 0;
    }
 
    // 큐 안의 모든 데이터를 front -> rear 순으로 출력
    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();
        }
    }
}

 

 

❑ Queue 클래스 테스트하기

 

더보기 
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;
    }
 
    // 큐에서 데이터를 피크(front 데이터를 들여다봄)
    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 int search(int x) {
        for(int i = 0; i < num; i++) {
            if(que[(i + front) % capacity] == x)
                return i + 1;
        }
        return 0;
    }
 
    // 큐 안의 모든 데이터를 front -> rear 순으로 출력
    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();
        }
    }
}

 

 

 

저작자표시
1

티스토리툴바