자료구조 - 선형구조 : 스택

Algoritm에 대해 학습하며, Java를 통해 구현해봅니다.

이 포스팅은 BOJ(Beakjoon Online Judge)의 @jh05013 님 께서 관리하고 계신
단계별로 풀어보기를 기준으로 작성됩니다.

이 포스팅이 올라가는 저장소 : https://github.com/hwk0911

hwk0911 - Overview

혹시 이 포스팅을 보고 알고리즘 공부를 시작하시거나, 복습하시는 분들은
노트와 펜을 준비하시고 직접 그려보면서 하시면 좋습니다.

알고리즘 첫걸음

알고리즘의 첫걸음은 누가 뭐래도 자료구조가 맞다. 많은 알고리즘 서적이 자료구조를
기본 지식으로 하여 설명하고 있다.

이번 포스팅에서는 자료구조의 시작, 스택(Stack)에 대해 알아보려 한다.

스택 (Stack)

스택(Stack). 게임에서도 자주 사용되는 용어다. 예를 들어 피시방 점유율 1위에 빛나는
League of Legend(이하 롤)에서 특히 스택이란 용어가 자주 쓰인다.

나서스.png 출처 : 롤 공식 홈페이지

사실 게임에서의 "스택"은 자료구조에서의 스택과는 관련이 없다! 다만 공통점이라고는 쌓인다는 점?

Stack을 직역하면 "쌓다"이다. 마찬가지로 자료구조 Stack도 특정 데이터를 쌓는 자료구조다.

구조를 먼저 살펴보자.

Stack의 구조

한쪽이 막혀있고, 들어오는 곳이 뚫려있는 구조다. 쉽게 말해 물컵을 생각하면 쉽다.
밑 빠진 물컵이 아니라면 물을 담았을 때, 물이 아래로 나가지 않는 것과 같다.

TOP은 가장 최근에 들어온 데이터의 위치를 향한다. 즉 데이터가 차있는 양을 의미한다.

위와 같이 데이터가 쌓였을 때, 데이터를 뽑아서 쓰고 싶다면, 당연히 Data 4부터 밖으로 나가게 된다.
데이터를 1-2-3-4를 순서로 쌓았을 때, 4-3-2-1의 순으로 빠져나온다.

이것을 LIFO(Last In First Out)구조라한다. 나중에 들어온 데이터가 먼저 나간다.

즉 Stack = LIFO 라 생각하면 된다. Stack자료구조의 입력 연산을 push, 출력 연산을 pop이라 한다.

코드로 살펴보자!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DataStructure_Stack {
    //전역으로 stack, top 선언
    static int[] stack = {0,0,0,0,0};
    static int top = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] work; //push data or pop 을 입력받기 위해 String 배열 선언

        while(true){
            work = br.readLine().split(" ");

            if(work[0].equals("push")){
                push(Integer.parseInt(work[1]));
            }
            else if(work[0].equals("pop")){
                pop();
            }

            checkStack(stack); // stack의 상태를 출력
        }
    }

    public static void push(int data) {
        if(top == stack.length){
            System.out.println("Stack Overflow Error");
        }
        else{
            stack[top] = data;
            ++top;
        }
    }

    public static void pop() {
        if(top == 0){
            System.out.println("Stack Overflow Error");
        }
        else{
            --top;
            stack[top] = 0;
        }
    }

    public static void checkStack(int[] stack) {
        for(int index = 0, size = stack.length ; index < size ; ++index){
            if(stack[index] != 0){
                System.out.print(stack[index] + " ");
            }
        }
        System.out.println();
    }
}

1. push 함수
   1. top이 stack의 사이즈와 같은지 판별 (가득 찬 상태인가)
   2. 가득 찬 상태가 아니면, stack의 top칸을 입력받은 데이터로 초기화
   3. top 1 증가
2. pop 함수
   1. top이 0인지 판별 (빈 상태인가)
   2. top 1 감소
   3. stack의 top칸을 0으로 초기화
3. checkStack 함수
   1. stack의 상태를 출력한다. (0은 데이터가 없는 것으로 판단하여 출력)

구현 방식에 따라 차이가 있다. 필자가 구현한 스택은 top이 먼저 앞으로 가있는 형태다.

따라서 push는 작업 후 top을 증가시켜줬고, pop은 작업 전에 top을 감소시켜줬다.

stack.gif

 

추천 문제 : https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

풀이 : https://cafecoder.tistory.com/entry/BOJStack4949%EA%B7%A0%ED%98%95%EC%9E%A1%ED%9E%8C-%EC%84%B8%EC%83%81

BOJ_Stack_4949_균형잡힌 세상