[Data Structure] Stack 구조

 

 

  이번 글에서는 자료구조의 대표적인 stack 구조에 대해 정리해 보겠다.

 

  stack에 대해 정리하고 Java코드로 구현해보겠다.

 

 

---

 

 

Stack 구조란?

 

  자료구조에서 대표적인 후입선출 특성을 지닌다. (LIFO Last In First Out)  

  Stack은 한쪽으로만 데이터를 넣고 뺄 수 있다. 입구와 출구가 단 한 개이므로 마지막으로 넣은 데이터가 제일 먼저 빠져나오는 구조이다.

 

  Stack은 마치 테이블 위에 책을 쌓는 것과 같다. 제일 처음 올려둔 책이 맨 아래, 제일 마지막에 올린 책이 맨 위로 쌓일 것이다. 그리고 제일 마지막에 올린 책을 제일 먼저 꺼내는 구조이다.

 

  

  Stack에서 데이터를 넣는 것을 push  데이터를 꺼내는 것을 pop이라고 부른다.

 

 

 

 

 

  그림처럼 스택은 매우 단순한 로직이다. LIFO만 기억하면 쉽다.

 

 

---

 

 

Stack에 사용되는 다양한 함수

 

기능	기능 설명
push(value)	새로운 value를 스택에 추가
pop()	스택 맨 위에 있는 요소 꺼낸다.
isEmpty()	스택이 비어있으면 true, 아니면 false
isFull()	스택이 가득 차 있으면 true, 아니면 false
size()	스택에 들어 있는 전체 요소의 수 반환
peek()	스택의 맨 위에 있는 요소 삭제하기 않고 반환

 

  주요 메서드를 이러하고 상황에 맞게 다양한 메서드를 더 추가 구현하면 된다.

 

 

 

  스택은 배열 혹은 링크드리스트로 구현할 수 있다. 하지만 스택은 배열로 구현하는 것이 더 효율적이다. 스택은 맨 마지막 값만 삭제하면 되는 구조이다. 링크드 리스트로 만들게 되면 맨 마지막 노드를 삭제 후 연결도 끊어야 완전히 삭제된 것이다. 하지면 배열은 맨 마지막 값 변경 후 값을 참조 못하게 pointer만 수정하면 된다.

 

 

---

 

 

 

🔐코드 Stack 인터페이스

public interface StackStruct {
    // 스택에 값 넣는 메서드.
    public int push(int value);

    // 스택에 있는 값 빼는 메서드.
    public int pop();

    // 스택 꼭대기 값 조회 메서드.
    public int peek();

    // 스택에 데이터 찾는 메서드.
    public void indexOf(int value);

    // 스택 용량을 확인하는 메서드.
    public int capacity();

    // 스택을 비우는 메서드.
    public void clean();

    // 스택에 쌓여있는 데이터 반환 메서드.
    public int size();

    // 스택이 비어있는지 확인하는 메서드.
    public boolean empty();

    // 스택이 가득차 있는지 확인하는 메서드.
    public boolean isFull();

    public String toString();
}

 

 

🔐코드 Stack 구현

package stack;

import java.util.Arrays;

public class StackImplement implements StackStruct {

    private int[] array;
    private int max;
    private int pointer;  // 스택을 참조하고 있는 위치

    StackImplement() {
        this(10);   //기본 스택 용량 10
    }

    StackImplement(int max) {
        this.max = max;
        try {
            array = new int[max];
            pointer = 0;
        } catch (OutOfMemoryError oome) {
            this.max = 0;
        }
    }

    class OverflowStack extends RuntimeException {
        OverflowStack() {
            super("스택 초과 예외 발생");
        }
    }

    class EmptyStack extends RuntimeException {
        EmptyStack() {
            super("스택 비어있음 예외 발생");
        }
    }

    @Override
    public int push(int value) throws OverflowStack {
        if (isFull())
            throw new OverflowStack();

        return array[pointer++] = value;
    }

    @Override
    public int pop() {
        return array[--pointer];
    }

    @Override
    public int peek() throws EmptyStack {
        if (empty()) {
            throw new EmptyStack();
        }
        return array[pointer - 1];
    }


    // 특정 값 스택에서 검색하는 메서드
    @Override
    public void indexOf(int value) {
        for (int i = pointer - 1; i >= 0; i--) {
            if (array[i] == value) {
                System.out.println("find array[" + i + "] ");
                return;
            }
        }
        System.out.println("값을 찾을 수 없음.");
    }


    // 스택의 최대 용량 return
    @Override
    public int capacity() {
        return max;
    }


    // array를 기존 max값에 맞게 새롭게 생성
    @Override
    public void clean() {
        pointer = 0;
        array = new int[max];
    }


    // 스택에 쌓여있는 데이터 개수 return
    @Override
    public int size() {
        return pointer;
    }


    // 스택이 비어있는지 확인
    @Override
    public boolean empty() {
        return pointer <= 0;
    }


    // 스택이 가득차 있는지 확인
    @Override
    public boolean isFull() {
        return pointer >= max;
    }


    // 스택을 구현한 Array toString method로 문자열로 출력.
    @Override
    public String toString() {
        return Arrays.toString(array);
    }
}

 

 

 max 변수는 스택의 용량을 저장하는 변수이다.

 pointer는 스택이 현재 데이터가 저장될 위치를 추적하는 변수이다. 

 

 

  pop 메서드 동작 시 데이터를 완전히 삭제를 안 한다. pointer--  pointer를 1 감소시킨다. 배열에는 아직 pop 한 값이 존재할 것이다. 하지만 pointer는 push를 통해서 값을 증가시킬 수 있다. pointer를 증가시키기 위해 push를 호출하면 push parameter가 전에 pop 했던 값을 덮어씌워 버릴 것이다. 이로서 pop 했던 값이 완전히 삭제된 것을 확인할 수 있다.

 

 

 

---

 

 

StackImplement 실행 main 코드

 

package stack;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        StackImplement stack = new StackImplement(15);
        int menu;
        Scanner sc = new Scanner(System.in);

        while (true) {
            System.out.print("1. push(value) 2. pop() 3. peek()  4. indexOf(value)  5. size()   //0: exit  : ");
            menu = sc.nextInt();
            if (menu == 0) {
                break;
            }

            int value = 0;
            switch (menu) {
                case 1 -> {
                    System.out.print("스택에 넣을 값은?: ");
                    value = sc.nextInt();
                    stack.push(value);
                }
                case 2 -> System.out.println(stack.pop());
                case 3 -> System.out.println(stack.peek());
                case 4 -> {
                    System.out.print("찾을 값은?: ");
                    value = sc.nextInt();
                    stack.indexOf(value);
                }
                case 5 -> System.out.println(stack.size());

                default -> System.out.println("다시 입력!!!");
            }
        }
        System.out.println("종료!!!");
    }
}