[알고리즘] JAVA 자료구조(1) - Stack

작성자	이재영
일 시	2024. 9. 3  (화) 18:00 ~ 21:00
장 소	미래관 자율주행스튜디오 429호
참가자 명단	임혜진, 이재영, 성창민, 김명원, 장원준
사 진

---

목차

1. 스택이란?
2. 스택의 특징
3. 사용법
4. 백준 풀이

이번 학기 모각코에서 Java를 사용한 알고리즘을 공부해볼 것이다. Java는 현재 한국에서 가장 많이 사용되는 언어라고 봐도 무방할 정도의 인지도를 가졌는데, 아마도 Java 프레임워크인 Spring 때문일 것이다. 이번 모각코를 통해 Java 활용 능력을 기르고, 이후 Spring 스터디까지 나아가볼 것이다.

 

1. 스택이란?

스택은 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 한쪽에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 형태로 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(Last-In-First-Out) 구조이다. 

 

여기서 데이터가 입력되고 삭제되는 부분을 스택 상단(Stack Top), 스택의 맨 밑바닥 부분은 스택 하단(Stack Bottom), 스택에 저장되는 데이터를 요소(Elements), 삽입 연산(Push), 삭제 연산(Pop) 등과 같은 용어들이 있다.

스택의 구조

2. 스택의 특징?

• 후입선출 구조 : 먼저 들어온 데이터가 나중에 빠져나가는 구조
• 단방향 입출력 구조 : 데이터의 들어오는 방향과 나가는 방향이 같다.
• 데이터를 하나씩만 넣고 뺄 수 있다.
• 깊이 우선 탐색에 이용된다.
• 재귀 함수의 동작 흐름과 같은 구조를 가진다.

삽입과 삭제 연산

이런 특징을 가진 스택은 편집기의 되돌리기, 이전페이지 이동 등과 같은 곳에 사용된다.

 

스택의 시간복잡도는 다음과 같다.

• 접근 : O(n)
• 탐색 : O(n)
• 삽입 : O(1)
• 삭제 : O(1)

스택은 위에서부터 차례대로 접근하거나 탐색할 수 있기 때문에 접근과 탐색의 시간 복잡도는 O(n)이고, 삽입과 삭제는 항상 맨 위에서 일어나기 때문에 시간 복잡도는 O(1)이다.

3. 사용법

우선 Java에서 Stack을 사용하려면 라이브러리를 import 해주어야 한다.

import java.util.Stack;

 

라이브러리를 가져왔으면 Stack을 선언해주어야 하는데, Stack을 선언할 때는 다음과 같은 양식으로 진행한다.

Stack<자료형> 스택명 = new Stack<>();

실제 코드를 보면 다음과 같다.

// 정수형
Stack<Integer> stackInt = new Stack<>();
// 문자열형
Stack<String> stackStr = new Stack<>();
// 불린형
Stack<Boolean> stackBool = new Stack<>();
// 실수형
Stack<Double> stackDouble = new Stack<>();

 

이렇게 선언까지 했으면 사용할 준비는 끝났다. 다음은 Stack에서 많이 사용하는 메서드를 알아보자.

 

메서드	설명
Stack.isEmpty()	Stack이 비어있는지 알려주는 메서드. boolean 값을 리턴한다.
Stack.peak()	Stack의 맨 위에 저장된 객체를 반환한다. 비어있을 경우 EmptyStackException을 발생시킨다.
Stack.pop()	Stack Top에 저장된 객체를 까냄과 동시에 Stack에서 삭제시킨다. 비어있을 경우 동일하게 EmptyStackException을 발생시킨다.
Stack.push(Object item)	Stack Top에 item을 저장한다.
Stack.search(Object o)	Stack에서 주어진 o를 찾아서 그 위치를 반환한다. 못 찾을 경우 -1을 반환하고, 배열과 달리 위치는 0이 아닌 1부터 시작한다.
Stack.size()	Stack의 요소 갯수를 반환한다.

 

Stack<Integer> stackInt = new Stack<>();

if(stackInt.isEmpty()){
    System.out.println("Stack is empty");
}

stackInt.push(1);
System.out.println(stackInt.peek());

if(!stackInt.isEmpty()){
    System.out.println("Stack is not empty");
}

System.out.println(stackInt.search(1));
System.out.println(stackInt.search(2));

stackInt.push(2);
stackInt.push(3);
System.out.println(stackInt.size());

System.out.println(stackInt.pop());
System.out.println(stackInt.pop());

코드 실행 결과

4. 백준풀이

백준(9012번 괄호) : https://www.acmicpc.net/problem/9012

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Stack;

public class StackTest {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++) {
            boolean result = true;
            String tmp = br.readLine();
            Stack<Character> stack = new Stack<>();
            for(char c : tmp.toCharArray()) {
                if(c == '('){
                    stack.push(c);
                } else{
                    if(stack.isEmpty()){
                        result = false;
                        break;
                    }
                    stack.pop();
                }
            }
            if(result && stack.isEmpty()){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
}

 

이 문제는 스택의 선입후출 특징을 활용하여 해결하였다. '('가 나오면 Stack에 Push, ')'가 나오면 Stack에 Pop을 해준다. 그러나 Pop을 하는 과정에서 Stack이 이미 Empty 하면 괄호가 맞지 않기 때문에 reulst를 false로 바꿔준다. 그렇게 반복하다가 모든 문자열에 대한 처리가 끝난 후에 reulst가 true이면서 Stack에 요소가 하나도 남지 않으면 올바른 괄호 문자열로 판단하고, 아니라면 올바르지 않다고 판단한다.

---

이번 모각코 활동을 통해 자바와 더 친해지고, 알고리즘 능력을 키워 조금 더 나은 개발자가 될 것이다.