Stack (2)

 

 

 

 

자료구조에서 중요한 개념인 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();
        }
    }
}

 

 

 

 

 

 

Stack

 

 

Queue

 

 

❑ 자료구조란?

 

여러 자료(데이터)를 다루는 구조

자료(데이터)란?

휴대폰 번호, 방문기록, 고객명단, 대기열 등 모든 것이 자료이다.

자료를 정리하는 방식은 자료의 형태마다 달라야한다.

만약에 규칙없이 저장하거나 하나의 구조만으로 저장하면 자료마다 활용하는 것이 불편하다.

자료를 효율적으로 정리하면 저장하고 활용하는데 있어서 훨씬 유리하게 된다.

 

자료를 효율적으로 정리하는 방법은 여러가지가 있다.

 

자료를 다루는 구조 그 자체를 뜻하고 구현하는 방식에는 제약이 없음

 

주로쓰는 자료구조 : stack, queue, graph, tree

 

❑ Stack?

 

FILO(First In Last Out) / LIFO(Last In First Out)

먼저 들어간놈이 나중에 나오고 나중에 들어간 놈이 먼저 나오는 자료 구조

출입구가 하나고 끝이 막힌 구조를 생각하면 된다.

 

 

자바에서 Stack을 배열로 구현해보기

더보기

Doit! 자료구조와 함께 배우는 알고리즘 입문(자바편)에서 참고해서 작성하였다.

 

package 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();
        }
    }
}

 

 

테스트할 코드도 구현해보았다.

package 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;
            }

        }
    }
}

 

 

자바에서는 Stack 자료구조가 클래스로 이미 지원되고 있다.

여러가지 메소드들을 이용해서 효과적으로 관리할수 있다.

  • push : 데이터를 넣는다.
  • pop : 데이터를 꺼낸다.
  • peek : 스택의 꼭대기에 있는 요소를 반환한다.
  • empty : 스택이 비었는지 확인한다.
  • search : 찾고자 하는 요소가 꼭대기부터 맨 처음으로 등장하는 index를 반환한다.

 

 

 

❑ Queue?

 

FIFO / LILO

먼저 들어간 놈이 먼저 나온다

줄 서서 기다리는 것을 이미지하면 된다.

은행이나 마트에서 줄서서 기다리면 먼저 온 사람 먼저 처리해준다

인큐 : 큐안에 들어옴

디큐 : 큐안에서 나감

 

자바에서 배열로 구현한 Queue..작성중..

 

 

➤ 현실적인 예시

 

문서를 출력하면 문서가 들어간 순서대로 인쇄 된다.

컴퓨터(출력버튼)-(임시기억장치)Queue에 하나씩 들어옴 - Queue에 들어온 순서대로 문서 인쇄

인쇄할 때 CPU가 인쇄 데이터를 보내는 속도가 프린터가 인쇄하는 속도보다 빠르기 때문에 인쇄 데이터를 잠시 보관할 임시저장공간이 필요하다.

만약에 CPU가 프린터가 하나씩 인쇄 되는것을 기다렸다가 데이터를 전송하면 CPU가 그 시간동안 다른일을 처리하지 못하기 때문에 비효율적이다.

컴퓨터 장치간에 데이터를 주고받을 때 장치 사이 속도가 존재한다.

시간차이나 속도차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용

-> 버퍼(Buffer) 라고 함

 

 

 

 

 

읽어주셔서 감사합니다.😍

오개념에 대한 지적은 언제나 환영입니다.

 

 

 

1