[자료구조] 스택 Stack (JAVA, PYTHON)

 

Stack

• LIFO(Last In First Out) 방식으로 작동하는 동적 데이터 구조
• 요소를 삽입한 역순으로 요소를 제거하기 때문에 문자열과 같은 순서를 역순으로 사용하는 데 사용할 수 있다.
• push, pop, peek 의 시간 복잡도는 O(1)

Python

def push(self, n):
    # using the pushback function from dynamic arrays to add to the stack
    self.stack.append(n)
    
def pop(self):
return self.stack.pop()

def peek(self):
    return self.stack[-1]

Java

// stack 선언
Stack<Integer> stack = new Stack<>();

// stack 값 추가
stack.push(1);
stack.push(2);
stack.push(3);

stack.peek(); // stack 가장 상단 값 출력

stack.size() // stack 크기 출력 ;3

stack.empty() // stack이 비어있으면 true

stack.contains(1) // stack에 1이 있으면 true

stack.pop(); // stack 값 제거

stack.clear(); // stack 전체 값 제거

---

🔓 Stack 연관 문제

1. Baseball Game

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

LeetCode - The World's Leading Online Programming Learning Platform

Python

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

        for op in ops:
            if op == "+":
                stack.append(stack[-1] + stack[-2])
            elif op == "D":
                stack.append(2 * stack[-1])
            elif op == "C":
                stack.pop()
            else:
                stack.append(int(op))

        return sum(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();
                st.push(score1);
                st.push(score1+score2);
            } 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/baseball-game/

LeetCode - The World's Leading Online Programming Learning Platform

 

Python

class Solution:
    def isValid(self, s: str) -> bool:
        Map = {")": "(", "]": "[", "}": "{"}
        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) {
        // 짝수개가 아닌경우 false
        if(s.length() % 2 != 0) return false;

        Stack<Character> st = new Stack<>(); // ({[ 저장
        
        for(int i = 0; i < s.length(); i++) {

            // ),},]가 남은 경우
            if(st.isEmpty() && (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) ==']')) return false;

            // 대응되는 괄호를 찾는다
            else if(s.charAt(i) == ')' && st.peek() == '(') st.pop();
            else if(s.charAt(i) == '}' && st.peek() == '{') st.pop();
            else if(s.charAt(i) == ']' && st.peek() == '[') st.pop();
            else st.add(s.charAt(i)); // ({[ 저장
        }
        return st.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/

LeetCode - The World's Leading Online Programming Learning Platform

 

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

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();
}

 

---

📚 JAVA HashMap

HashMap<String,String> map1 = new HashMap<>();
HashMap<String,String> map2 = new HashMap<>(map1); // map1 모든값을 가진 hashMap
HashMap<String,String> map3 = new HashMap<>(10); // 초기 용량(capacity) 지정
HashMap<String,String> map4 = new HashMap<String,String>(){{put("a","aaa");}}; // 초기값 지정

// * 값 추가
HashMap<Integer,String> map = new HashMap<>();
map.put(1,"사과");
map.put(2,"바나나");
map.put(3,"포도");

System.out.println(map.get(1)); // key값 1의 value ;사과

// * 값 출력
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}

// keySet() 활용
for(Integer i : map.keySet()) {
System.out.println("[Key]" + i + " [Value]:" + map.get(i));
}

// entrySet(),iterator()
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()) {
Map.Entry<Intger, String> entry = entries.next();
System.out.println("[Key]:" + entry.getKey() + " [Value]:" +  entry.getValue());
}

// * 값 삭제
map.remove(1); // key값 1 제거 remove(key);
map.clear(); // 모든 값 제거