[JAVA] 스택

스택이란?
데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(가장 나중에 넣은 데이터를 먼저 꺼냄)

• 데이터 넣는 작업 push -> 스택이 가득 차서 푸시할 수 없는 경우
  OverflowIntStackExcpetion
• 데이터 꺼내는 작업 pop -> 스택이 비어 있으면 EmptyIntStackException
• 스택의 꼭대기에 있는 데이터 peek -> 스택이 비어 있으면 EmptyIntStackException
• 검색 메서드 indexOf
• 모든 요소 삭제 clear
• 용량 확인 capacity
• 데이터 수를 확인 size
• 스택이 비어있는지 ? isEmpty
• 스택이 가득 찼는지 ? isFull

스택 만들기

public class IntStack {
    private int max;
    private int ptr;
    private int[] stk;

    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){}
    }
    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){}
    }
    //생성자 
    public IntStack(int capacity){
        ptr = 0;
        max = capacity;
        try{
            stk=new int[max]; // 스택 본체용 배열 
        }catch(OutOfMemoryError e){
            max=0;
        }
    }
    //스택이 가득 차서 push 할 수 없을 때, Overflow예외 던짐
    public int push(int x) throws OverflowIntStackException{
        if(ptr>=max) // 배열은 max-1까지니까 
            throw new OverflowIntStackException();
        return stk[ptr++]=x;
    }
    //더 이상 pop을 할 수 없을 때, empty예외 던짐 
    public int pop() throws EmptyIntStackException{
        if(ptr<=0)
            throw new EmptyIntStackException();
        return stk[--ptr];
    }
    public int peek() throws EmptyIntStackException{
        if(ptr<=0){
            throw new EmptyIntStackException();
        }
        return stk[ptr-1];
    }
    public int indexOf(int x){
        for(int i=ptr-1;i>=0;i--)
            if(stk[i]==x)
                return i;
            return -1;
    }
    public void clear(){
        ptr = 0;
    }
    public int capacity(){
        return max;
    }
    public int size(){
        return ptr;
    }
    public boolean isEmpty(){
        return ptr<=0;
    }
    public boolean isFull(){
        return ptr>=max;
    }
    public void dump() {
        if (ptr <= 0)
            System.out.println("스택이 비어 있습니다.");
        else{
            for(int i=0;i<ptr;i++){
                System.out.print(stk[i]+" ");
            }
            System.out.println();
        }
    }
}

연습문제 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        IntStack intstack = new IntStack(64);

        while(true){
            System.out.println("현재 데이터 수 : "+intstack.size()+"/"+intstack.capacity());
            System.out.print("(1) push (2) pop (3) peek (4) dump (5) clear (6) indexOf  (0) exit: ");

            int menu = sc.nextInt();
            if(menu==0) break;

            int x;
            switch (menu){
                case 1:
                    System.out.print("데이터 : ");
                    x=sc.nextInt();
                    try{
                        intstack.push(x);
                    }catch(IntStack.OverflowIntStackException e){
                        System.out.println("스택이 가득 찼습니다.");
                    }
                    break;
                case 2:
                    try{
                        x= intstack.pop();
                        System.out.print("pop data : "+x);
                    }catch(IntStack.EmptyIntStackException e){
                        System.out.println("스택이 비어있습니다.");
                    }
                    break;
                case 3:
                    try{
                        x= intstack.peek();
                        System.out.println("peek data : "+x);
                    }catch(IntStack.EmptyIntStackException e) {
                        System.out.println("스택이 비어있습니다.");
                    }
                    break;
                case 4:
                    intstack.dump();
                    break;
                case 5:
                    intstack.clear();
                    break;
                case 6:
                    x=sc.nextInt();
                    if(intstack.indexOf(x)==-1) {
                        System.out.println("찾는 데이터가 없습니다.");
                    }else {
                        System.out.println("찾는 데이터는 " + intstack.indexOf(x));
                    }
                    break;
                case 0:
                    System.exit(0);

            }
        }
    }
}

연습문제 3

//push pop만 구현해보자..
public class doubleStack {

        private int max;
        private int ptrA;
        private int ptrB;
        private int[] stk;

        public class EmptyIntStackException extends RuntimeException{
            public EmptyIntStackException(){}
        }
        public class OverflowIntStackException extends RuntimeException{
            public OverflowIntStackException(){}
        }

        public doubleStack(int capacity){
            max = capacity;

            try{
                stk=new int[max];
                ptrA = 0;
                ptrB= max-1;
            }catch(OutOfMemoryError e){
                max=0;
            }
        }

        public int pushA(int x) throws OverflowIntStackException {
            if(ptrA>=ptrB)
                throw new OverflowIntStackException();
            return stk[ptrA++]=x;
        }
        public int pushB(int x) throws OverflowIntStackException {
            if(ptrB<=ptrA)
                throw new OverflowIntStackException();
            return stk[ptrB--]=x;
        }
        public int popA() throws EmptyIntStackException {
            if(ptrA<=0)
                throw new EmptyIntStackException();
            return stk[--ptrA];
        }
        public int popB() throws EmptyIntStackException {
            if (ptrB>=max-1)
                throw new EmptyIntStackException();
            return stk[++ptrB];
        }
        public int indexOf(int x){
            for(int i=stk.length-1;i>=0;i--){
                if(stk[i]==x){
                    return i;
                }
            }
            return -1;
        }
    }

//test
public class StackTest {
    public static void main(String[] args){
        doubleStack db = new doubleStack(10);
        db.pushA(10);
        db.pushB(100);
        db.pushB(19);
        db.pushA(200);

        System.out.println(db.indexOf(100));
        System.out.println(db.indexOf(200));

    }
}

결과값은 아래와 같음