[자료구조] 2. 스택(Stack) 구현하기 (Java)

스택(Stack)

①

스택(Stack)는 가장 마지막에 들어간 데이터가 먼저 나오는 LIFO(Last In First Out) 구조를 가지고 있습니다. 아래 소스코드에서 1차원 배열로 스택을 구현하였고 스택 관련 함수들은 다음과 같습니다.

stackIsEmpty(): 스택이 비어있는지 판단하는 함수

stackIsFull(): 스택에 더이상 들어갈 공간이 없는지 판단하는 함수

size(): 스택에 들어가있는 데이터의 개수를 return하는 함수

push(int value): 스택에 value값을 저장하는 함수

peek(): 스택에 가장 마지막에 들어간 데이터를 return하는 함수

pop(): 스택에 가장 마지막에 들어간 데이터를 return하고 삭제하는 함수

 

②

아래 소스코드의 맨 아래 주석 부분을 보면 Input과 Output을 알 수 있습니다. 테스트 케이스의 개수는 2이고 첫번째 테스트 케이스에서 5개의 숫자가 들어옵니다. 1 2 3 4 5가 들어오면 순차적으로 스택에 저장합니다. 스택에 들어있는 데이터들을 꺼내 출력하면 저장된 순서의 역순으로 5 4 3 2 1이 결과값으로 나옵니다.

소스 코드

import java.util.Scanner;
 
class ArrayStack{
    int top; //top: stack 저장을 위한 index 변수
    int max_size = 10000; //max_size: stack 배열의 최대 크기
    int[] stack;
    
    public ArrayStack() {
        top = 0; //top: stack의 초기 index는 0
        stack = new int[max_size]; //배열 생성
    }
    
    boolean stackIsEmpty() { //stackIsEmpty(): stack에 아무것도 들어있지 않은지 판단하는 함수
        return (top == 0);
    }
    
    boolean stackIsFull() { //stackIsFull(): stack에 더이상 들어갈 공간이 없는지 판단하는 함수
        return (top == max_size);
    }
    
    int size() { //size(): stack에 현재 들어가있는 데이터의 개수를 return하는 함수
        return top;
    }
    
    void push(int value) { //push(int value): value값을 stack에 넣음
        if(stackIsFull()) System.out.println("stack overflow!");
        else stack[top++] = value;
    }
    
    Integer peek() { //peek(): stack에 가장 최근에 들어간 값을 return하는 함수
        if(top==0) {
            System.out.println("stack is empty!");
            return null;
        }
        else {
            Integer value = new Integer(stack[top-1]);
            return value;
        }
    }
    
    Integer pop() { //pop(): stack에 가장 최근에 들어간 값을 return하고 삭제하는 함수
        if(top==0) {
            System.out.println("stack is empty!");
            return null;
        }
        else {
            Integer value = new Integer(stack[--top]);
            return value;
        }
    }
}
 
class STL_Stack {
    public static void main(String arg[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            ArrayStack stk = new ArrayStack();
            for (int i = 0; i < N; i++) {
                int value = sc.nextInt();
                stk.push(value);
            }
            System.out.print("#" + test_case + " ");
            while (!stk.stackIsEmpty()) {
                Integer value = stk.pop();
                if (value != null) System.out.print(value.intValue() + " ");
            }
            System.out.println();
        }
        sc.close();
    }
}
/*
input
2
5
1 2 3 4 5
5
5 4 2 3 1
output
#1 5 4 3 2 1
#2 1 3 2 4 5
*/