스택 ( 자료구조 ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.
가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.
접시를 쌓아올린다고 생각하면 된다.

스택 ( Stack )

• 후입 선출 ( LIFO, Last In First Out )
• 한쪽 끝에서만 데이터 삽입( push )과 삭제( pop )가 이루어짐
• 재귀 호출, 백트래킹, 수식 계산 등 다양한 알고리즘에서 활용됨

    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

스택의 기본 연산

1. push(value): 데이터 삽입

• 스택의 맨 위(top)에 데이터를 추가하는 연산

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

2. pop(): 데이터 제거

• 스택의 맨 위(top)에 있는 데이터를 제거하고 반환하는 연산
• 만약 스택이 비어 있다면 언더플로우(Underflow, 데이터 부족 에러) 발생

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

3. peek() (또는 top()): 최상단 데이터 확인

• 스택의 맨 위(top)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

4. isEmpty(): 스택이 비어 있는지 확인

• 스택이 비어 있으면 true, 아니면 false 반환

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

 

로직 예시)

왼쪽 위부터 오른쪽으로 진행된다

 

1. 빈 스택이다

2. push를 통해 값 ( 1 ) 을 넣었다. 이 때 top은 1을 가리킨다

3. push를 통해 값 ( 2 ) 을 넣었다. 이 때 top은 2를 가리킨다.

4. peek를 통해 값 ( 2 ) 을 받았다.

5. pop을 통해 값 ( 2 ) 를 꺼냈다. 이 때 top은 1을 가리킨다.

6. pop을 통해 값 ( 1 ) 를 꺼냈다. 이 때 top은 아무것도 가리키지 않는다. ( -1 상태 )

 

배열을 활용하여 스택에 대해 설명했지만, 
List 클래스 ( 하위 클래스 포함 ArrayList 등 ) 으로도 구현 가능하다.
 개념을 이해하고 상황에 맞게 사용하면 된다.

전체 구현 코드

package org.example;


public class TestStack {
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

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