[자료구조] Stack (스택) 구현 - 자바(JAVA)

스택

 

 

이번 포스팅은 백준 알고리즘 사이트에서 스택 큐 덱 알고리즘 분류가 있어 스택을 배열로 구현하는 방법을 작성한다.

 

먼저 스택은 위 이미지처럼 입구가 맨위에 1개라서 LIFO(Last In First Out) 구조이고 원소 삽입은 push 메소드, 추출은 pop 메소드이다.

 

스택은 간단한 자료구조여서 설명할 게 없다...

 

원소 삽입 및 추출 시 배열 사이즈를 동적으로 할당하는 기능은 원형큐에 추가해 놓았다.

 

https://jiji-gilog.tistory.com/4

자바(JAVA) - Circular Queue (원형큐) 구현

 

 

 

- 스택 구현 소스

public class Stack {

    private static int pointer = -1;
    private static int size = 0;

    private static void push(int[] stack, int val) {
        stack[++pointer] = val;
        size++;
    }

    private static int pop(int[] stack) {
        if(pointer < 0) {
            return -1;
        }

        size--;
        return stack[pointer--];
    }

    private static int size() {
        return size;
    }

    private static boolean empty() {
        if(size <= 0) {
            return true;
        }

        return false;
    }

    private static int top(int[] stack) {
        if(size <= 0) {
            return -1;
        }
		
        // size - 1 or pointer
        return stack[size - 1];
    }

}

 

 

위 소스는 스택의 메소드만 구현한 소스이고 테스트 할 수 있는 소스는 아래와 같다.

 

나는 스택 배열을 main 메소드 안에 지역변수로 설정하였지만 클래스 변수(static)으로 선언해서 메소드 파라미터도 수정하고 작성하는 게 더 낫다.

 

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

/**
 * 스택 - 자료구조
 */
public class BasicStack {

    private static int pointer = -1;
    private static int size = 0;

    private static void push(int[] stack, int val) {
        stack[++pointer] = val;
        size++;
    }

    private static int pop(int[] stack) {
        if(pointer < 0) {
            return -1;
        }

        size--;
        return stack[pointer--];
    }

    private static int size() {
        return size;
    }

    private static int empty() {
        if(size <= 0) {
            return 1;
        }

        return 0;
    }

    private static int top(int[] stack) {
        if(size <= 0) {
            return -1;
        }

        return stack[size - 1];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int cmd = Integer.parseInt(br.readLine());
        int[] stack = new int[cmd];

        for(int i = 0; i < cmd; i++) {
            st = new StringTokenizer(br.readLine());

            String str = st.nextToken();
            switch (str) {
                case "push":
                    push(stack, Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    sb.append(pop(stack)).append("\n");
                    break;
                case "size":
                    sb.append(size()).append("\n");
                    break;
                case "empty":
                    sb.append(empty()).append("\n");
                    break;
                case "top":
                    sb.append(top(stack)).append("\n");
                    break;
            }
        }

        System.out.println(sb);
        br.close();
    }
}