스택(Stack)

스택이라는 것은 영어사전에서 찾아 봤을 때 더미 라는 의미가 있다

쉽게 말해서 쌓여있는 무언가를 이야기할때 스택이라고 표현을 한다고 보면 된다

스택의 입출력 형태를 후입선출 (LIFO : Last-In First-Out)이라고 한다

스택은 입출력은 스택의 최상단에서만 이루어진다

---

스택의 구조

• 스택 상단

• 스택의 요소들

• 스택 하단

스택을 구현하기 위해서

필요한 메서드들을 한번 살펴보도록 하겠다

create(size) <- 최대 크기가 size인 스택을 생성한다

is_full(stack) <- 스택이 가득찼는지 확인한다

is_empty(stack) <- 스택이 비었는지 확인한다

push(stack, item) <- 스택의 맨 위에 item을 추가한다

pop(stack) <- 스택의 맨 위의 원소를 제거하고 반환한다

peek(stack) <- 스택의 맨 위의 원소를 제거하지 않고 반환한다

 

필요한 프로퍼티에 대해서 살펴보도록 하겠다

top <- 이 변수는 스택은 최상단에서 값 교환이 일어나기 때문에 제일 위의 인덱스를 저장하고 있을 변수가 하나 필요하다

capacity <- 현재 스택의 크기를 저장하는 프로퍼티이다.

data <- 스택의 자료들을 저장할 자료형인 배열을 선언하는 프로퍼티이다.

---

이번에는 스택을 코드로 구현해 보도록하겠다

사용언어 : 자바

 

변수 구현 부분

private int top;
private int capacity;
private int data[];

create() 메서드를 대신한 초기화 구문

public Stack() {
        this.top = -1;
        this.capacity = 1;
        this.data = new int[capacity];
}

is_full(stack) 메서드 구현 부분

public boolean is_full() {
        if (data.length == top+1) {
            return true;
        }else {
            return false;
        }
}

is_empty(stack)메서드 구현 부분

public boolean is_empty() {
        if (top == -1) {
            return true;
        }else {
            return false;
        }
}

push(stack, item)메서드 구현 부분

public void push(int element) {
        if (is_full() == true) {
            capacity *= 2;
            int temp[] = new int[capacity];
            for (int i = 0;i < data.length; i++) {
                temp[i] = this.data[i];
            }
            this.data = temp;
        }
        this.data[++top] = element;
}

push메서드를 구현 할 때는 stack의 크기를 동적으로 조정해주기 위해서

스택이 가득 찼는지 확인 한 다음에 가득찼다면 원래 길이의 두배로 길이를 늘려서 재할당 할수있겠끔 구현했습니다

 

pop(stack)메서드 구현 부분

public int pop() {
        if (is_empty() == true) {
            System.out.println("스택이 비어있습니다");
            return -1;
        }
        else {
            return this.data[top--];
        }
}

peek(stack)메서드 구현 부분

public int peek() {
        if (is_empty() == true) {
            System.out.println("스택이 비어있습니다");

            return -1;
        }
        else {
            return this.data[top];
        }
}

제가 아직 자바에 대한 완전한 이해가 부족해서 스택을 구현하는 과정중에서 부족한 부분이 있을텐데

혹시나 이 글을 보신다면 댓글로 적어주시면 감사하겠습니다!! :)

---

stack의 완전한 코드가 궁금하시다면

아래의 링크로 들어가면 완전한 코드를 보실 수 있습니다

<완전한 코드 보러가기>