Stack이란?

Stack은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 자료구조입니다.

추상자료형( abstract data type, ADT )이며, 이는 논리적인 기능을 명시해 놓은 것이라 볼 수 있고, 이는 구현체가 이를 상속받아 구현하는 방식으로 자료형은 Stack이지만 구현은 여러 방법으로 구현할 수 있음을 의미합니다.

Stack은 Vector를 상속받아 구현을 하고 있는데 이는 Vector를 구현되 LIFO방식으로 데이터를 다룰 수 있게 다루기 위해 Stack이란 자료형이 존재한다 생각해 볼 수 있습니다.

우선 기본적인 기능을 확인해 보겠습니다.

Stack은 Vector를 상속한 ADT이기 때문에 기본적으로 Object []인 elementData로 데이터를 관리하고 있습니다.

배열의 크기는  기본적으로 10의 크기로 생성하고 있으며, resizing을 통해 많은 데이터가 들어오더라도 수용할 수 있습니다. 이렇듯 대부분의 기능은 동일하지만, 외부에서 접근할 수 있는 pop메서드를 확인해 보면 elemtnData의 Size를 확인하여 맨 마지막 데이터만을 추출할 수 있도록 구현되어 있는 것을 확인할 수 있습니다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

제공하는 기능

사용처

그럼 Stack은 어떤 곳에서 사용하게 될까요??

웹브라우저 History 즉 뒤로가기 앞으로가기 와 같은 기능처럼 history를 쌓아두고 이를 최신 것부터 접근하는 상황이 있다면 이럴때는 Stack을 사용함으로써 편하게 관리할 수 있습니다.

또한 재귀함수와 같이 연산이 루프를 도는 방향의 알고리즘을 구현을 한다면,

최근 접근 한 것들을 접근 할 수 있는 Stack을 통해 쉽게 최근에 넣은 데이터를 꺼내 연산을 하면서 손쉽게 구현할 수 있습니다. 백준 코딩 테스트

References

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

주제

금주 테코테코의 주제는 Stack입니다.

Stack 자료구조를 활용하거나 Stack자료구조의 작동원리를 이해하여 아래 문제를 해결하였습니다.

문제

1.  올바른 괄호

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

코드

public class 올바른_괄호 {

    boolean solution(String s) {

        Node first = null;
        Node last = null;

        int len = s.length();
        for(int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(c == '(') {
                if(first == null) {
                    first = new Node();
                    last = first;
                    continue;
                }
                last = last.newNextNode();
                continue;
            }
            if(first == null) return false;
            Node prev = last.removeNowNode();
            if(prev == null) {
                first = null;
            }
            last = prev;
        }

        return last == null;
    }

    public static class Node {
        public Node prevNode;
        public Node nextNode;

        public Node() {
        }

        public Node(Node prevNode) {
            this.prevNode = prevNode;
        }

        public static Node from (Node prev) {
            return new Node(prev);
        }

        public Node newNextNode() {
            this.nextNode = Node.from(this);
            return this.nextNode;
        }

        public Node removeNowNode() {
            Node prev = this.prevNode;
            if(prev == null) return null;
            prev.nextNode = null;
            return prev;
        }
    }
}

2.  괄호_회전하기

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

코드

package com.codingTest.programers.level2;

import java.util.*;

public class 괄호_회전하기 {
    Map<Character, Integer> map;

    public 괄호_회전하기() {
        map = new HashMap<>();
        map.put('(', 0);
        map.put('[', 1);
        map.put('{', 2);
        map.put(')', 3);
        map.put(']', 4);
        map.put('}', 5);
    }

    public int solution(String s) {
        int len = s.length();

        int answer = 0;

        boolean flag;
        Stack<Character> checkPoint;

        int point = 0;
        for(int i = 0; i < len; i++){
            flag = false;
            checkPoint = new Stack<>();
            for(int j = 0; j < len; j++){
                char c = s.charAt((j + point)%len);
                int index = map.get(c);
                if(index < 3) {
                    checkPoint.push(c);
                } else {
                    if(checkPoint.isEmpty()) {
                        flag = true;
                        break;
                    }
                    char check = checkPoint.pop();
                    int prevIndex = map.get(check);
                    if(prevIndex != index%3) {
                        flag = true;
                        break;
                    }
                }
            }
            if(checkPoint.isEmpty() && !flag) {
                answer++;
            }
            point++;
        }

        return answer;
    }
}