[자료구조] 스택(배열 이용) - push, pop

안녕하세요. PEACE-입니다.

자료구조 스터디 [세 번째] 글입니다.

1. 스택

스택이란 자료구조 중 하나입니다. 가장 최근에 들어간 데이터가 가장 먼저 나오며 흔히 후입선출(Last In First Out)이라고 말합니다. 이와 같은 데이터 구조를 통해 다양한 작업을 수행할 수 있습니다. 하나의 예를 들겠습니다. 재귀적 함수의 작업 수행 중에 함수의 호출이 일어나면 스택에 함수에 대한 정보가 push되고 함수의 끝이나 return을 만나면 함수가 종료되면서 pop을 통해 나중에 호출된 함수가 스택에서 빠져나옵니다.

2. 스택 구현

배열은 사이즈가 정해져있습니다. 현재 데이터의 위치를 알기 위해 top이라는 변수를 사용합니다. 스택 포인터라고도 합니다. 또한 push 메서드는 스택(배열)에 데이터를 넣는 작업을 구현하고 pop 메서드는 스택(배열)에 들어있는 데이터를 빼내는 작업을 구현합니다. 실제로 배열을 이용한 스택 구조에서는 데이터를 뺀다는 의미에 완벽하게 들어맞는 작업을 구현할 수없기 때문에 top의 위치를 변경함으로써 데이터를 빼낸 것 처럼 처리합니다. 배열로 구현한 스택에서는 push와 pop의 작업을 수행할 때는 데이터가 하나도 없는지(isEmpty), 가득 찼는지(isFull)를 확인하는 로직을 반드시 거쳐야합니다. 그렇지 않는다면 배열 index의 올바르지 않는 사용으로 IndexOutOfBoundsException등의 예외 상황이 발생할 수 있기 때문입니다. 

*필요 멤버

 - 멤버 변수 : 

MAX_SIZE : 스택의 사이즈

Array : 데이터를 담을 배열

top : 스택 포인터, 초기값 = -1

 - 메서드 :

isEmpty() : boolean

isFull() : boolean

push(data) : void

pop() : data type of stack array

3. Push

push는 간단합니다. isFull을 통해 스택에 데이터가 가득찼는지 확인 후 가득차있지 않다면 데이터를 넣어주는 작업입니다.

[그림 1] PUSH

스택은 데이터가 위로 쌓이듯이 저장됩니다.

4. Pop

pop 역시도 간단합니다. 데이터를 빼내는 작업이므로 isEmpty를 통해 스택에 데이터가 있는지 확인 후 데이터를 빼거나 빼지않고 종료합니다.

[그림 2] POP

스택은 후입선출입니다. 위 그림에서  pop 수행 시 나중에 push된 데이터가 먼저 나오는 것을 확인할 수 있습니다.

5. 소스코드

/* Array를 이용한 스택 구현
 * 1. 변수 : 배열, MAX 사이즈, top
 * 2. isEmpty : boolean, isFull : boolean
 * 3. input -> push : void
 * 4. output -> pop : data type of stack
 * */

public class Stack {
    private int MAX_SIZE;
    private int[] stack;
    private int top;

    public Stack() {
        MAX_SIZE = 5;
        stack = new int[MAX_SIZE];
        top = -1;
    }

    private boolean isEmpty() {
        return top == -1 ? true : false;
    }
    private boolean isFull() {
        return (top + 1 == MAX_SIZE) ? true : false;
    }

    public void push(int data) {
        if (!isFull())
            stack[++top] = data;
    }

    public int pop() {
        if (!isEmpty())
            return stack[top--];
        return -1;
    }

    public void display() {
        System.out.print("top : " + top + "\nstack : ");
        for (int idx = 0; idx <= top; idx++)
            System.out.print(stack[idx] + " ");
        System.out.println();
    }
}