[JAVA] 자바 stack (스택) 클래스

# stack 이란?

스택은 후입선출(LIFO - Last in First Out)의 특성을 가지는 자료구조이다. 후입선출이란 말그대로 맨 마지막에 들어온 값이 제일 먼저 나간다는 말이다. 아직 스택이 이해가 되지 않는다면 다음 예를 생각해보자. 엘레베이터가 20층에서 1층으로 내려오는데 20층에서 사람이 한 명, 10층에서 다른 사람이 한 명 탑승했다. 이 엘레베이터가 1층에 도착하게 되면 앞에있던 10층 주민이 먼저 내리고, 그 뒤에 있던 20층 주민이 나중에 내리게 되는데 바로 이런 상황이 후입선출이다. Stack 은 사전적 의미로도 '쌓다' 라는 뜻이 있는데, 이러한 자료구조를 생각하면 정말 잘 만든 이름같다!

# stack 선언

import java.util.Stack; //import
Stack<Element> stack = new Stack<>();

스택은 이런 식으로 선언을 할 수 있는데, 원하는 Element 에 맞게 스택을 선언할 수 있다. 예를 들어 int 형 스택을 선언하고 싶다면, Stack<Integer> stack = new Stack<>(); String 형 스택을 선언하고 싶다면 Stack<String> stack = new Stack<>(); 으로 선언해주면 된다.

 

# push(), pop(), clear()

 

stack 을 빈 바구니라고 생각해보자. 스택이라는 빈 바구니 안에 값을 집어넣는 것이 push() 라는 메소드이다.

Stack<Integer> stack = new Stack<>(); 
stack.push(1);     
stack.push(2);     
stack.push(3);

이렇게 int 형 스택을 선언해주고, 차례대로 1, 2, 3을 푸시해주게 되면 스택 바구니의 맨 밑에는 1, 그 위에 2, 그리고 맨 위에는 3이 존재하게 된다. 이렇게 추가된 스택의 값들은 pop() 이라는 메소드를 이용해서 순서대로 제거할 수 있다! 아래의 예시를 살펴보자.

Stack<Integer> stack = new Stack<>(); 
stack.push(1);     
stack.push(2);     
stack.push(3);
stack.pop(); // 이때 stack 에는 맨 뒤에 추가된 값인 3이 지워지고 1과 2만 남게된다

이렇게 stack.pop() 을 사용하게 되면 현재 stack 에는 1과 2만이 담겨있을 것이다! 위의 코드에서 stack.pop();을 한 번 더 실행하게 되면 두번째로 입력된 값인 2가 지워지고 stack 안에는 1만 남게 된다. 

 

만약 stack 의 전체 값들을 지우고 싶다면 clear() 메소드를 이용하면 된다.

Stack<Integer> stack = new Stack<>(); 
stack.push(1);     
stack.push(2);     
stack.push(3);
stack.clear(); // 스택의 모든 값들 삭제 (초기화)
stack.push(4);
stack.push(5); // stack 에는 4와 5만 존재한다

 

# peek(), empty()

peek() 메소드는 stack 에서 가장 나중에 입력된 값, 즉 스택이라는 바구니 맨 위에 있는 값이 무엇인지 출력해주는 함수이다. 

Stack<Integer> stack = new Stack<>(); 
stack.push(1);     
stack.push(2);     
stack.push(3);
stack.push(4);
stack.push(5); 
System.out.println(stack.peek()); // 5

 

empty() 메소드는 stack 의 값이 비어있다면 true 를 리턴하고, 비어있지 않다면 false 를 리턴한다. 

Stack<Integer> stack = new Stack<>(); 
stack.push(1);     
stack.push(2);     
stack.push(3);
stack.push(4);
stack.push(5); 
System.out.println(stack.empty()); // false

 

# 예제

다음 문제를 풀어보면서 stack을 풀면 얼마나 쉽게 알고리즘을 해결할 수 있는지 느껴보자.

문제 :

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항 : 문자열 s의 길이 : 100,000 이하의 자연수, 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12909

코딩테스트 연습 - 올바른 괄호

풀이 (자바)  - 스택 이용 X : 

class Solution {
    boolean solution(String s) {
    int length = s.length() -1;
           int count = 0;
           if (s.charAt(0) == ')' || s.charAt(length) == '(') {return false;}
           for (int i = 0; i < s.length(); i++) {
              if (s.charAt(i) == '(') {
                 count++; // ( 을 찾으면 카운트 +
              }
              if (s.charAt(i) == ')') {
                 count--; // ) 을 찾으면 카운트 - 
              }
              if (count < 0) {return false;} // 괄호 닫힘이 괄호 열림보다 먼저 나옴 ex (()))(() 
           }
           if (count == 0){return true;}
           return false;
    }
}

위의 알고리즘도 잘 실행이 되지만, if (s.charAt(0) == ')' || s.charAt(length) == '(') 나, if (count < 0) 와 같은 예외처리를 해야한다는 단점이 있다. 하지만 이것은 스택을 이용하면 쉽게 해결할 수 있다! 

풀이 (자바)  - 스택 이용 O : 

import java.util.Stack;
class Solution {
    boolean solution(String s) {
    	boolean answer = true;
        Stack<Integer> stack = new Stack<>(); // 선언

        for(int i = 0; i < s.length(); i++){
                if(s.charAt(i) == '(')  // '(' 이면 
                    stack.push(1);	// stack 에 푸쉬
                else{ 					// '(' 이 아니라면 = ')' 이면 
                    if(stack.isEmpty()) // 스택이 비어있을경우
                        return false;	// false 
                    else				// 스택이 비어있지 않다면 
                        stack.pop();    // 	pop 으로 가장 최근 값을 지워준다 
                }
        }
        answer = (stack.isEmpty()) ? true : false; 
        // 스택이 비어있다면 = (모든 괄호가 잘 pop 된 경우임) true, 그렇지 않다면 false
        return answer;
    }
}

이런 식으로 스택을 사용하니 알고리즘이 훨씬 간결하고 편리해졌다. 앞으로 알고리즘을 풀 때 정말 요긴하게 쓰일 것 같다!