03. Stack

2020. 1. 21. 15:46CSE/Data Structure

* 특징

: 데이터를 일시적으로 저장하기 위해 사용하는 자료구조

  후입선출(LIFO, Last In First Out)

 

* java로 간단하게 구현한 모습 & 메소드 설명

import java.lang.reflect.Array;
import java.util.Arrays;

public class Stack<T> {
    private int ptr;
    private int max;
    private T [] stk;

    public Stack(int capacity){
    //생성자 
    
        ptr = 0;
        max = capacity;

        try{
            this.stk = (T[])new Object[max];
        }catch (OutOfMemoryError e){
            max = 0;
        }
    }

    public T push(T x) throws OverflowStackException{
     //스택에 데이터를 push하는 메소드
    
        if(ptr>=max){
            throw new OverflowStackException();
        }

        stk[ptr++] = x;
        return x;
    }

    public T pop() throws EmptyStackException{
    //스택의 꼭대기에서 데이터를 제거하고 그 값을 리턴하는 메소드
    
        if(ptr<=0){
            throw new EmptyStackException();
        }

        return stk[--ptr];
    }

    public T peek() throws EmptyStackException{
     //스택의 꼭대기에 있는 데이터의 값을 리턴하는 메소드
    
        if(ptr<=0){
            throw new EmptyStackException();
        }

        return stk[ptr-1];
    }

    public int indexOf(T x) {
     //스택에 x와 같은 값을 가진 배열의 인덱스를 리턴하는 메소드
    
        for(int i = 0; i<ptr;i++){
            if(stk[i].equals(x)){
                return i;
            }
        }
        return -1;
    }

    public void clear(){
     //스택을 비우는 메소드 => 스택 포인터를 0으로 바꿈
    
        ptr = 0;
    }

    public int size(){
    //스택의 용량을 리턴하는 메소드
    
        return max;
    }

    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.printf("%d ",stk[i]);
            }
            System.out.println();
        }
    }

}

class EmptyStackException extends RuntimeException{
    public EmptyStackException(){ };
}

class OverflowStackException extends RuntimeException{
    public OverflowStackException(){};
}

'CSE > Data Structure' 카테고리의 다른 글

Hash Table, ArrayList  (0) 2021.07.19
04. Queue  (0) 2020.02.02
02. 이진 검색(Binary Search)  (0) 2019.08.21
01. 선형 검색 (Linear Search)  (0) 2019.08.21