스택은 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 그래서 마지막에 삽입된 데이터가 먼저 삭제되는 구조를 가지고 있습니다.

쌓여있는 접시를 생각하면 이해가 쉽습니다. 가장 위에 접시를 올리고, 가장 위에 접시를 먼저 사용합니다.

참고로 스택은 힙 메모리 영역에서 일반적인 데이터를 저장하는 스택과, 스택 영역 메모리에서 프로그램의 변수와 같은 정보를 저장하는 스택으로 나뉩니다.

스택 - 특징

• 후입선출 방식이다. LIFO (Last In First Out)
• 가장 위에서만 자료의 입출력이 이루어 진다.
• 같은 구조와 크기의 데이터만 정해진 방향으로 쌓을 수 있다.
• 보통 크기를 고정해서 사용하기 때문에 메모리가 넘칠 수 있다. 이를 이용한 해킹 방법이 바로 Stack OverFlow다.

스택 - 연산

• push() : 가장 위에 데이터를 추가한다.
• pop() : 가장 위에 있는 데이터를 제거한다.
• peek() : 가장 위에 있는 데이터를 반환한다.
• isEmpty() : 스택이 비어있으면 1, 그렇지 않으면 0을 반환한다.

스택 - 장점

• 데이터를 받는 순서대로 정렬된다.
• 데이터 입출력 속도가 빠르다.

스택 - 단점

• 데이터 크기를 미리 정해야 한다.
• 저장 공간의 낭비가 생길 수 있다.
• 가장 최신 데이터만 가져온다.
• 한 번에 하나의 데이터만 처리가 가능하다.

스택 - 사용

• 재귀 알고리즘 구현
• 브라우저 방문 기록
• 실행 취소 (UNDO)
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산

코드

Java Stack

import java.util.Stack;

Stack<Integer> stack = new Stack<>();;

//push
for (int i=0; i<5; i++) {
    stack.push(i);
}
System.out.println(stack);  //[0, 1, 2, 3, 4]

//peek
System.out.println(stack.peek());   //4

//pop
stack.pop();
System.out.println(stack.peek());   //3

//search
System.out.println(stack.search(3));    //1

//empty
System.out.println(stack.empty());  //false

Array Stack

import java.util.Arrays;

public class ArrayStack {
    private int top;
    private int size;
    private String[] stack;

    public ArrayStack(int size) {
        this.top = -1;
        this.size = size;
        this.stack = new String[size];
    }

    public void push(String item) {
        if (top == size - 1) {
            System.out.println("Stack is full");
        } else {
            stack[++top] = item;
        }
    }

    public void pop() {
        if (!empty()){
            stack[top--] = "";
        }
    }

    public String peek() {
        if (empty()) {
            return "";
        } else {
            return stack[top];
        }
    }

    public String search(int index) {
        if (empty()) {
            return "";
        } else {
            return stack[size - index - 1];
        }
    }

    public boolean empty() {
        return (top == -1);
    }

    public static void main(String[] args) {
        int size = 5;
        ArrayStack arrayStack = new ArrayStack(size);

        //push
        arrayStack.push("A");
        arrayStack.push("B");
        arrayStack.push("C");
        arrayStack.push("D");
        arrayStack.push("E");
        System.out.println(Arrays.toString(arrayStack.stack));  //[A, B, C, D, E]

        //peek
        System.out.println(arrayStack.peek());  //E

        //pop
        arrayStack.pop();
        System.out.println(arrayStack.peek());  //D

        //search
        System.out.println(arrayStack.search(3));   //B

        //empty
        System.out.println(arrayStack.empty());  //false
    }
}