Stack

Last updated - 2023년 04월 26일 Edit Source


    # 스택 기본개념

    스택 (Stack) : 삽입과 삭제 연산이 LIFO로 이뤄지는 자료구조

    • LIFO (Last-In-First-Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나감
      • 입력과 출력이 하나의 방향으로 제한
    • 바로 넣었다가 거꾸로 정렬된 데이터를 꺼내고 싶을 때 유용
      • 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법 등등
      • DFS에서도 쓰긴 하는데.. 사실 DFS는 그냥 재귀로 하는게 …

    스택을 구성하는 4가지 기능

    • push() : 맨 위에 데이터를 하나 쌓아올리기
    • pop() : 맨 위에 데이터를 가져오면서 삭제
    • peek() : 맨 위에 데이터가 뭔지 보는거
    • isEmpty() : 스택이 비었는지 확인


    # 스택 자바로 구현해보기


     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    
    import java.util.EmptyStackException;  
      
    class Stack<T> {  
        class Node<T> {  
            // 제네릭 타입인 T로 data 받음  
            private T data;  
            // 다음 노드 next        
            private Node<T> next;  
      
            public Node(T data) {  
                this.data = data;  
            }  
        }  
      
        // 스택은 맨 위의 주소만 알고 있으면 되니까  
        private Node<T> top;  
      
        public void push(T item) {  
            // push 할 아이템을 가지고 Node 를 하나 생성  
            Node<T> t = new Node<T>(item);  
            // top 앞에 생성한 Node 를 위치시킴  
            t.next = top;  
            // 이제 이 push 된 Node 가 top        
            top = t;  
        }  
      
        public T pop() {  
            if (top == null) {  
                throw new EmptyStackException();  
            }  
      
            // 맨 위에 있는 데이터를 반환하기 전에  
            // 그 아래에 있는 녀석을 top 으로 만들어줘야함
            // 그래서 데이터 백업해놓는거  
            T item = top.data;  
            top = top.next;  
            return item;  
        }  
      
        public T peek() {  
            if (top == null) {  
                throw new EmptyStackException();  
            }  
            return top.data;  
        }  
      
        public boolean isEmpty() {  
            return top == null;  
        }  
    }  
      
    public class StackTest {  
        public static void main(String[] args) {  
            Stack<Integer> stack = new Stack<Integer>();  
            stack.push(1);  
            stack.push(2);  
            stack.push(3);  
            stack.push(4);  
            System.out.println(stack.pop());  
            System.out.println(stack.pop());  
            System.out.println(stack.peek());  
            System.out.println(stack.pop());  
            System.out.println(stack.isEmpty());  
            System.out.println(stack.pop());  
            System.out.println(stack.isEmpty());  
        }  
    }
    
    // 4
    // 3
    // 2
    // 2
    // false
    // 1
    // true
    


    # 스택 2개로 큐 1개 구현

    • 스택의 특성을 이용하면 를 구현할 수 있다.

    • Enqueue : 큐가 add() 할 때 새로운 데이터를 stack1에다가 push()
    • Dequeue : 큐가 peek(), remove() 호출 했을 때 stack2가 비어있으면
      1. stack1에서 pop()
      2. stack2에다가 push()
      3. stack2에서 pop() 해서 확인

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    
    import java.util.Stack;  
      
    class MyQueue<T> {  
        Stack<T> stackNew, stackOld;  
      
        MyQueue() {  
            stackNew = new Stack<T>();  
            stackOld = new Stack<T>();  
        }  
      
        public int size() {  
            return stackNew.size() + stackOld.size();  
        }  
      
        public void add(T item) {  
            stackNew.push(item);  
        }  
      
        private void shiftStack() {  
            // stackOld 가 비어있는 상태가 아닌 경우에는  
            // 데이터가 mass up 될 수도 있음  
            if (stackOld.isEmpty()) {  
                while (!stackNew.isEmpty()) {  
                    stackOld.push(stackNew.pop());  
                }  
            }  
        }  
      
        public T peek() {  
            shiftStack();  
            return stackOld.peek();  
        }  
      
        public T remove() {  
            shiftStack();  
            return stackOld.pop();  
        }  
    }  
      
    public class StackQueueTest {  
        public static void main(String[] args) {  
            MyQueue<Integer> myQueue = new MyQueue<Integer>();  
            myQueue.add(1);  
            myQueue.add(2);  
            myQueue.add(3);  
            System.out.println(myQueue.remove());  
            System.out.println(myQueue.remove());  
            System.out.println(myQueue.remove());  
        }  
    }
    
    // 1
    // 2
    // 3
    

    Comment