자료구조 - 스택

1. Stack!

데이터를 제한적으로 접근할 수 있는 구조 - 한쪽 끝에서만 자료를 넣거나 뺄수 있음.

가장 나중에 쌓은 데이터를 가장 먼저 뺄수 있다. (LIFO)

 

큐가 프로세스에서 대기하도록 만든 데이터라면 스택은 실제 프로그램에서 recursive한 처리를 할때 많이 사용된다. 

그렇다면 스택은 어떤 구조를 나타내는지 살펴보자.

 

2. 본론

 

 

 1) 스택 구조

스택은 LIFO(Last in, First Out) 데이터 관리 방식을 따름.

대표적으로는 컴퓨터 내부의 프로세스 구조의 함수 동작 방식을 나타낼수 있다.

주요 기능으로는 pop, push가 있다.

언어의 뜻대로 pop은 스택에서 꺼내는 것이고, push는 스택에 넣는 기능이다.

하노이 탑 같은 경우가 될 것 같다.

 

 

 2) 스택구조와 프로세스의 스택

다음 예시를 통해서 프로세스가 어떻게 실행되어 지는지 살펴보자.

def recursive(data):
    if data < 0:
        print ("end!!")
    else:
        print("input %d"%data)
        recursive(data - 1)  # 재귀적으로 접근
        print("returned %d"%data)   
recursive(3)

# input 3
# input 2
# input 1
# input 0
# end!!
# returned 0
# returned 1
# returned 2
# returned 3

3부터 들어갔지만 return되어 나오는 값은 0부터 나오는 것을 확인 할 수 있다.

 

이러한 구조를 통해서 얻을 수 있는 장점

일단 구조가 단순하고 구현이 쉽다.

데이터 저장 읽기 속도가 빠르다.

하지만 단점으로는 데이터 최대 갯수를 미리 정해야 한다.

데이터의 최대 공간을 미리 확보해야해서 공간의 낭비가 발생할 수 있다.

 

 

 

 

 3) 스택의 구현

public class Main {

    public static void main(String[] args) {
        Stack s = new Stack(10);
        s.push(9);
        s.push(8);
        s.push(7);
        s.push(6);
        s.push(5);
        s.push(4);
        s.push(3);
        s.push(2);
        s.push(1);
        s.push(0);
//        s.push(-1); // overflow
        s.print();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
        s.pop();
//        s.pop();  // underflow
        s.print();

    }
}


class Stack{
    private Object[] s;
    private int top=-1;
    private int size=0;

    public Stack(int size){
        this.size = size;
        this.s = new Object[this.size];
    }
    public boolean isEmpty(){
        return this.top==0? true:false;
    }
    public boolean isFull(){
        return top==size-1? true:false;
    }
    public void push(Object obj){
        if(isFull()) throw new Overflow();
        s[++top] = obj;
    }
    public Object pop(){
        if(isEmpty()) throw new Underflow();
        Object tmp = s[top];
        s[top--] = null;
        return tmp;
    }
    public void print(){
        for (int i=0; i<=top; i++){
            System.out.println(s[i]);
        }
    }
    class Overflow extends RuntimeException{}
    class Underflow extends RuntimeException{}

}

 

 

하다보니 그냥 반복문을 쓸껄 왜 저렇게 했지?ㅋㅋ..