[자료구조] 스택 Stack (Python,Java)

스택

• 후입선출 (LIFO : Last In First Out) 구조
• 단방향 입출력 구조 : 데이터의 들어오는 방향과 나가는 방향이 같다.
• 깊이 우선 탐색(DFS)에 이용된다.
• 재귀 함수의 동작 흐름과 같은 구조를 가진다.
• push / pop / peek 모두 O(1)의 시간 복잡도를 가진다.

스택 선언

import java.util.Stack;

Stack<Integer> stackInt = new Stack<>();
Stack<String> stackStr = new Stack<>();
Stack<Boolean> stackBool = new Stack<>();

스택 조작

stackInt.push(1); // 값 추가 + 반환
stackInt.push(2);
stackInt.push(3);

stackInt.pop(); // 3 값 제거 + 3 반환

stackInt.add(4); // 값 추가 + 반환

stackInt.peek(); // 마지막요소 반환. 스택비었을경우 NoSuchElementExecption

/*
search()
인자를 스택에서 검색하여 빠져나오는 순서 인덱스 위치를 반환.
찾는 값이 스택에 없을 경우 -1을 반환
*/
System.out.println(stackInt.search(2)); 

System.out.println(stackInt.isEmpty()); // 빈 경우 true,아닐경우 false 반환

stackInt.clear(); // 값 모두 제거

관련 문제 1.Baseball Game

https://leetcode.com/problems/baseball-game/description/

LeetCode - The World's Leading Online Programming Learning Platform

Python

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        score_stack = []

        for o in operations:

            if o == "+" and len(score_stack) >= 2:
                summed = score_stack[-2] + score_stack[-1]
                score_stack.append(summed)
            
            elif o == "D" and len(score_stack) >= 1:
                doubled = score_stack[-1] * 2
                score_stack.append(doubled)
            
            elif o == "C" and len(score_stack) >= 1:
                score_stack.pop()
            else:
                score_stack.append(int(o))
        
        return sum(score_stack)

Java

class Solution {
    public int calPoints(String[] operations) {
        Stack<Integer> st = new Stack<>();

        for(String op : operations) {
            if(op.equals("+") && st.size()>=2) {
                int score1 = st.pop();
                int score2 = st.peek();
                int score3 = score1 + score2;
                st.push(score1);
                st.push(score3);
            } else if(op.equals("D") && !st.isEmpty()) {
                int score = st.peek();
                st.push(score*2);
            } else if(op.equals("C") && !st.isEmpty()) {
                st.pop();
            } else {
                st.push(Integer.parseInt(op));
            }
        }

        int sum = 0;
        while(!st.isEmpty()) {
            sum += st.pop();
        }
        return sum;        
    }
}

관련 문제 2.Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

Python

class Solution:
    def isValid(self, s: str) -> bool:
        Map = {")": "(", "]": "[", "}": "{"} # val : key
        stack = []

        for c in s:
            if c not in Map:
                stack.append(c)
                continue
            if not stack or stack[-1] != Map[c]:
                return False
            stack.pop()

        return not stack

Java

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(stack.isEmpty() && (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']'))
            return false;
            else if (
                        s.charAt(i) == ')' && stack.peek() == '('
                    ) stack.pop(); else if (
                        s.charAt(i) == '}' && stack.peek() == '{'
                    ) stack.pop(); else if (
                        s.charAt(i) == ']' && stack.peek() == '['
                    ) stack.pop(); else stack.add(s.charAt(i));
            }
            return stack.isEmpty();
        }
}

 

hashmap 사용

class Solution {
    public boolean isValid(String s) {
        Stack<Character> brackets = new Stack<>();
        Map<Character, Character> map = new HashMap<>(3);

        map.put(')','(');
        map.put('}','{');
        map.put(']','[');

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c)) { // ), }, ] 일때
                if(!map.isEmpty() && map.get(c).equals(brackets.peek())) brackets.pop();
                else return false;
            } else {
                brackets.push(c);
            }
        }
        return brackets.isEmpty();
    }
}

관련 문제 3. Min Stack

https://leetcode.com/problems/min-stack/

Min Stack - LeetCode

 

Python

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]

Java

class MinStack {

    private Stack<Integer> st;
    private Stack<Integer> minSt;

    public MinStack() {
        st = new Stack<>();
        minSt = new Stack<>();
    }
    
    public void push(int val) {
        st.push(val);

        val = Math.min(val, minSt.isEmpty()? val : minSt.peek());
        minSt.push(val);
    }
    
    public void pop() {
        st.pop();
        minSt.pop();
    }
    
    public int top() {
        return st.peek();
    }
    
    public int getMin() {
        return minSt.peek();
    }
}