[자료구조]스택_Stack ADT(Abstract Data Type)

스택을 설명하기 가장 좋은 예

Goal

✔ Stack 이해하기
✔ Stack 기본 연산 이해하기
✔ Stack Implementes in JAVA

Stack 이란?

한 쪽 끝에서만 자료를 삽입, 삭제가 가능한 후입선출(LIFO: Last-In First-Out) 형식의 자료구조

Stack의 사용사례

스택은 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우 많이 사용되는 자료구조이다.

◼ 실행 취소 - (Ctrl + Z)
◼ 웹 브라우저 - 뒤로가기
◼ 역순 문자 만들기 - (ABCD → DCBA)
◼ 재귀 알고리즘 - 재귀호출시 임시 데이터 저장
◼ 기타 다양한 곳에서 많이 사용된다...

Stack 구현/연산

구현

스택은 배열, 구조체, 포인터, 링크드 리스트(Linked List)로 구현될 수 있고,그 사이즈 또한 고정/동적 으로 구현할 수 있다.

int top = -1

top 변수는 스택의 현재 위치를 가르키는 변수이다.

초기값은 -1로 초기화한다. 즉 top 변수의 값이 -1 이라면, 해당 스택은 비어있는 스택이다.

또한, 스택에 item이 들어올때마다 top 변수의 값에 +1를 해주어 현재 스택 마지막 item의 위치를 업데이트 해준다.

마지막으로 top 변수는 스택의 마지막 item의 위치를 가르키므로, 스택의 최대 사이즈보다 커질 수 없다. 즉, top값이 스택의 최대사이즈와 같다면, 해당 스택은 다 찼다는 의미이다.

연산

pop(): 스택의 가장 위에 있는(마지막에 들어온) item을 삭제한다.
push(Object item): 스택의 가장 위에 item을 추가한다.
peek(): 스택 가장 위에 있는(마지막에 들어온) item을 반환한다.
isFull(): 스택이 다 차있으면, true를 반환한다.
isEmpty(): 스택이 비었으면, true를 반환한다.

자바구현 소스코드

코드는 간단하므로, 따로 설명은 적지 않겠다.

public class Stack {

    int MAX_STACK_SIZE = 10;
    int top = -1;
    char[] stack = {};

    public Stack(int MAX_STACK_SIZE) {
        this.MAX_STACK_SIZE = MAX_STACK_SIZE;
        this.top = -1;
        stack = new char[MAX_STACK_SIZE];
    }

    void push(char val) {
        if (isFull() == true) {
            System.out.println("Stack is full!!");
        } else {
            stack[++top] = val;
        }
    }

    void pop() {
        if (isEmpty() == true) {
            System.out.println("stack is empty!!");
        }
        --top;
    }

    char peek() {
        return stack[top];
    }

    boolean isFull() {
        if (top == MAX_STACK_SIZE) {
            return true;
        }
        return false;
    }

    boolean isEmpty() {
        if (top == -1) {
            return true;
        }
        return false;
    }

    void pirntAllElements() {
        if (isEmpty() == true) {
            System.out.println("stack is empty!!");
        } else {
            for (int i = 0; i <= top; i++) {
                System.out.print(stack[i]);
            }
            System.out.println();
        }
    }

    void pushString(String text) { // 문자열을 하나씩 잘라서 스택에 저장하는 함수
        int len = text.length();
        char[] charText = text.toCharArray();
        if (len == MAX_STACK_SIZE) {
            System.out.println("Test length is over the MAX SIZE!");
        } else {
            for (int i = 0; i < len; i++) {
                this.push(charText[i]);
            }
        }
    }

    void popContinue(int times) { // 주어진 횟수대로 pop() 호출 함수
        for (int i = 0; i <= times; i++) {
            this.pop();
        }
    }

    public static void main(String[] args) {
        Stack stack1 = new Stack(10);
        stack1.pushString("Hello!");
        stack1.pirntAllElements();

        System.out.println(stack1.peek());
        stack1.popContinue(3);

        stack1.pirntAllElements();
    }
}