Stack

💡 스택

• 데이터를 순서대로 쌓는 자료구조
• 먼저 들어간 데이터는 제일 나중에 나오는 LIFO 구조
• 데이터 삽입은 Push, 데이터 추출은 Pop이다.
• 데이터를 하나씩 넣고 뺄수 있다.
• 입출력 방향이 한곳이다.

---

구현

• push(): 스택에 데이터를 추가할 수 있어야 합니다.
• pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
• size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
• peek(): 가장 나중에 추가된 데이터를 리턴해야 합니다.
• show(): 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴합니다.
• clear(): 현재 스택에 포함되어 있는 모든 데이터 삭제합니다.
• remove(): 삭제와 삭제된 요소 반환이 동시에 됩니다.

Stack<Integer> stack = new Stack<>();

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

stack.pop();
stack.pop();
stack.pop();
stack.pop();

// 4, 3, 2, 1 순으로 데이터가 빠져나감

브라우저의 앞으로가기&뒤로가기를 생각해보자

• 새 페이지 접속 시, 현재 페이지는 Prev Stack에 보관
• 뒤로 가기 버튼을 누르면 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 끝에 보관된 페이지 = 현재페이지
• 앞으로 가기 버튼을 누르면 Next Stack의 가장 처음 페이지를 가져오고 현재 페이지는 다시 Prev Stack 으로 넘김

---

ArrayList로 스택 구현

public class Implementation_Stack {
    private ArrayList<Integer> listStack = new ArrayList<Integer>();

    public void push(Integer data) {
        listStack.add(data);
    }

    public Integer pop() {
        if (listStack.size() == 0) {
            return null;
        } else {
            return listStack.remove(listStack.size()-1);
        }
    }

    public int size() {
        return listStack.size();
    }

    public Integer peek() {
        if (listStack.size() == 0) {
            return null;
        } else {
            return listStack.get(listStack.size()-1);
        }
    }

    public String show() {
        return listStack.toString();
    }

    public void clear() {
        listStack.clear();
    }
}

---

스택을 배열로 구현했을 때

배열은 순서가 있고 첫 부분을 제거하거나 추가하려면 요소들을 하나씩 뒤로 옮겨야 하며 시간복잡도는 O(n) 임
스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않음

그래서 첫 부분을 제거하거나 추가하는 과정의 시간복잡도가 상수인 연결 리스트를 스택 & 큐에 적용하는게 좋음

배열로 스택 구현

• addLast, removeLast -> O(1)의 시간복잡도
• addFirst, removeFirst -> 배열의 원소들은 메모리 상에서 순차적으로 저장되기 때문에 맨 앞에서 삽입/삭제 연산이 일어나면 뒤로 한칸씩 미루거나 앞으로 한칸씩 당겨야 하므로 O(n)의 시간복잡도
• Last In First Out (LIFO, 후입선출, 나중에 들어온 원소가 제일 먼저 나간다.)
• top에서만 삽입/삭제가 일어나며, 배열로 구현하면 O(1)의 시간복잡도 (addLast, addFirst)

---

💡 스택으로 오름차순 수열 구현

임의의 수열을 스택에 넣었다가 출력하는 방식으로 오름차순 수열을 출력할 수 있는지 확인.

출력할 수 있다면 push와 pop 연산을 어떤 순서로 수행해야 하는지 알아내는 프로그램 작성

push 연산은 +, pop 연산은 -, 불가능 할 때는 NO 출력

 static int AA = 5;
 static int[] BB = {3,4,5,6,7};

    public static void main(String[] args) {
//        average(A, B);
        stack(AA, BB);
    }

    // Stack의 오름차순 수열 구현
    // 수열의 개수 a, 수열[] b
    public static String stack(int a, int[] b) {
        int[] A = new int[a];

        for (int i=0; i<a; i++) {
            A[i] = b[i];
        }

        Stack<Integer> stack = new Stack<>();
        StringBuffer bf = new StringBuffer();

        // 오름차순의 수
        int num = 1;
        boolean flag = true;

        for (int i=0; i<A.length; i++) {
            // 현재 수열의 수
            int su = A[i];
            System.out.println("su = " + su);
            // 현재 수열 값 >= 오름차순의 자연수
            // pop()을 수행해 수열을 꺼낸다
            if (su >= num) {
                // push
                while (su >= num) {
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
                // 현재 수열값 < 오름자순의 자연수
                // pop()을수행해 수열을 꺼낸다
            } else {
                int n = stack.pop();
                // 스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크면 수열 출력 불가
                if (n > su) {
                    System.out.println("NO");
                    flag = false;
                    break;

                } else {
                    bf.append("-\n");
                }
            }
        }
        if (flag) {
            System.out.println(bf.toString());
        }
        return bf.toString();
    }

---

💡 Stack을 이용한 오큰수 구현

for문으로 오큰수를 찾으면 시간복잡도가 높아 제한시간을 초과할 우려가 있으므로,

스택을 이용하여 오큰수를 구현한다.

입출력 예시

입력

int N = 수열의 크기

int[] M = 수열

출력

5 7 7 -1

풀이

스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.

오큰수를 구한 후, 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다.

풀이 순서

• 스택에 채워져 있거나 A[index] > A[top]인 경우 pop한 인덱스를 이용해 정답 수열에 오큰수 저장.
  (pop은 조건을 만족하는 동안 계속 반복)
• 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어간다.
• 위의 과정을 수열의 길이만큼 반복하고 현재 스택에 남아있는 인덱스에 -1을 저장한다.

    public int O(int a, int[] b, String[] c) {
        // 수열 배열 생성
        int[] A = new int[a];
        // 정답 배열 생성
        int[] B = new int[a];

        for (int i = 0; i < a; i++) {
            A[i] = Integer.parseInt(c[i]);
        }

        // 스택의 최초값을 0 으로 초기화
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 0; i < a; i++) {
            // 스택이 비어있지 않고 현재 수열이 스택의 top이 가리키는 수열보다 클 경우
            while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
                // 정답 배열에 오큰수를 현재 수열로 저장
                B[stack.pop()] = A[i];
            }
            // 신규 데이터 push
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            // 반복문을 다 돌았는데 스택이 비어 있지 않다면 빌때까지
            // 스택에 쌓인 인덱스에 -1을 넣는다
            B[stack.pop()] = -1;
        }

        int temp = 0;
        for (int i = 0; i < a; i++) {
            temp = B[i];
            System.out.println(temp + " ");
        }

        return temp;
    }