스택(stack) 개념 및 사용법 정리

# 스택(stack)이란?

- 스택(Stack)은 사전적으로 '더미', '쌓아 올림' 이라는 의미

- 후입선출(LIFO - Last In First Out) 형태의 자료구조

  - 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 구조

  - 책을 바닥에 순서대로 쌓아 놓고, 다시 책을 꺼낼때 마지막에 쌓은 것부터 꺼내는 방식

- Stack 클래스는 LIFO 자료구조를 구현한 클래스로 JAVA에서 '컬렉션 프레임워크' 로 이미 제공

- 스택을 구현하는 방법은 배열과 연결 리스트가 있음

# 스택(stack) API

pop(추출)

 - 가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다

 - 이 작업은 O(1)의 복잡도를 가진다

push(삽입)

 - 스택의 최 상위에 새로운 자료를 삽입한다

 - 이 작업은 O(1)의 복잡도를 가진다

isEmpty

 - 스택이 empty 상태인지 확인한다

clear

 - 스택에 존재하는 모든 자료들을 삭제한다

peek

 - 가장 최 상위에 위치한 자료를 추출한다

pop 메소드와는 달리 스택에서 제거하지는 않는다.

 - 이 작업은 O(1)의 복잡도를 가진다

# 스택(stack) 클래스 사용법

import java.util.Stack;
 
public class Main {
    static Stack <Integer> stack;
    
    public static void main(String[] args) {
        stack = new Stack <Integer>();
        
        // stack 초기화
        stack.clear();
        
        // stack에 데이터 1 삽입
        stack.add(1);
        
        // stack에 대이터 5 삽입
        stack.add(5);
        
        // stack의 size 출력
        System.out.println("stack size = " +stack.size());
        
        // stack에서 데이터 확인 및 제거
        System.out.println("data = " +stack.pop());
        
        // stack에서 데이터 확인
        System.out.println("data = " +stack.peek());
        
        // stack에서 데이터 확인 및 제거
        stack.pop();
 
        // stack에 데이터가 없는지 확인
        if (stack.isEmpty()) {
            System.out.println("stack is empty");
        }
    }
}
 
/********** 결과 **********
stack size = 2
data = 5
data = 1
stack is empty
*/

# 스택(Stack) 구현 - 배열 사용

# 문제

N(2<= N <=100)개의 수를 순서대로 Stack에 넣은 후 하나씩 꺼내 화면에 출력

# 입력

2 // 테스트 케이스 수 

5 // 데이터 크기 

1 2 3 4 5 

5 

5 4 2 3 1

# 출력

#1 5 4 3 2 1 

#2 1 3 2 4 5

import java.util.Scanner;
 
class Main {
    static final int MAX_N = 100;
 
    static int top;
    static int stack[] = new int[MAX_N];
 
    static void stackInit() {
        top = 0;
    }
 
    static boolean stackIsEmpty() {
        return (top == 0);
    }
 
    static boolean stackIsFull() {
        return (top == MAX_N);
    }
 
    static boolean stackPush(int value) {
        if (stackIsFull()) {
            System.out.println("stack overflow!");
            return false;
        }
        stack[top] = value;
        top++;
 
        return true;
    }
 
    static Integer stackPop() {
        if (top == 0) {
            System.out.println("stack is empty!");
            return null;
        }
 
        top--;
        Integer value = new Integer(stack[top]);
 
        return value;
    }
 
    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();
 
            stackInit();
            for (int i = 0; i < N; i++) {
                int value = sc.nextInt();
                stackPush(value);
            }
 
            System.out.print("#" + test_case + " ");
 
            while (!stackIsEmpty()) {
                Integer value = stackPop();
                if (value != null) {
                    System.out.print(value.intValue() + " ");
                }
            }
            System.out.println();
        }
        sc.close();
    }
}

# 참고사이트

https://hyeonstorage.tistory.com/262

https://gompangs.tistory.com/5

https://ehclub.co.kr/3059

https://songeunjung92.tistory.com/18