Stack - (선형)자료구조

 

stack은 후입선출 (LIFO)이란 특성을 가진 자료구조이다. 주로 함수콜 스택, 수식 계산, 인터럽트 처리등에 사용된다. 

스택은 삽입과 삭제가 빈번한 상황에서 많이 사용되며 *검색이나 정렬은 시간복잡도가 크게 좋지 않아 다른 자료구조를 많이 사용한다. 

 

stack은 push를 통해 입력하고 pop을 통해 출력한다. 또한 가장 먼저 들어간 값을 bottom으로 표시하고 가장 나중에 들어간 값을 top으로 관리한다. 

 

Stack의 시간 복잡도

1. 삽입/ 삭제 : O(1)
2. 검색 : O(n) (모든 요소들을 확인해야한다)
3. 정렬 : O(nlogn)

 

Java 에서의 사용법 

* JAVA에서는 stack을 import 하여 사용할 수 있다. 이러한 java에서의 stack 사용법은 아래와 같다.

Stack stack = new Stack();

stack.push(1); // stack에 1이란 값 집어 넣기

stack.pop(); // top을 출력 후 비움

stack.peek(); // top 을 return (비우지 않고 출력만)

stack.contains(1); // 1을 포함하는지 true, false로 반환

stack.size(); // stack의 size 반환

stack.empty(); // stack이 비어있는지 true, false로 반환

stack.clear(); // stack내의 모든 값을 지움 

 

이러한 stack을 java에서 import하지 않고 직접 구현하여 사용하는 방법은 두 가지가 있다.

1. ArrayList 를 이용하여 구현

2. 배열을 이용하여 구현

 

먼저 첫 번째 방법인 ArrayList를 이용하여 구현하기위해 예외처리를 포함하고, 생성자에서 ArrayList 객체를 생성한뒤 isEmpty, push, pop, peek, printStack 함수를 구현해주면 된다.

하지만 배열을 이용하여 stack을 구현하기 위해서는 ArrayList에서의 구현과 다르게 신경써주어야 할 부분이 또 있다.

바로 isFull 함수를 따로 신경써서 구현해주어야 한다는 점이다. 왜냐하면 List와는 다르게 배열은 공간이 한정되어 있기때문이다.

또한 push, pop 함수 내에서 top 관리를 계속 업데이트 해주며 구현해주어야한다. 

 

 

Stack을 이용한 대표 문제

1. 문자열 거꿀로 출력하기

   ㄴ 문자열을 stack에 저장 후 pop으로 꺼내서 result에 붙이기

2. 괄호 짝 검사 

  ㄴ 여는 괄호는 stack에 push, 닫는 괄호가 나오면 pop해주기 중간에 stack이 empty이거나 마지막에 stack이 empty가 아니면 false를 출력한다. 

 

이 두개는 stack을 이용하지 않고도 풀 수 있지만 stack을 이용하면 훨씬 더 적은 Big O 시간을 가지게 된다.

 

Stack이용해서 푼 문제들 첨부 

1. 백준 25556번 : 포스택

package baekjoon.dataStructure.stack;

import java.io.*;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

/*
* 자료구조 : Stack
* 백준 25556번 문제
* 포스택
* */
public class Num25556 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));

        int n = Integer.parseInt(br.readLine());
        int[] permutation = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            permutation[i] = Integer.parseInt(st.nextToken());
        }

        boolean result = ascendingOrder(n,permutation);
        if(result){
            bw.write("YES");
        }else{
            bw.write("NO");
        }
        bw.close();

    }

    public static boolean ascendingOrder(int n, int[] permutation){
        Stack stack01 = new Stack();
        Stack stack02 = new Stack();
        Stack stack03 = new Stack();
        Stack stack04 = new Stack();


        for(int i=0; i<n; i++){
            if(stack01.empty() || (int)stack01.peek() < permutation[i]){
                stack01.push(permutation[i]);
            }else if(stack02.empty() || (int)stack02.peek() < permutation[i]){
                stack02.push(permutation[i]);
            }else if(stack03.empty() || (int)stack03.peek() < permutation[i]){
                stack03.push(permutation[i]);
            }else if(stack04.empty() || (int)stack04.peek() < permutation[i]){
                stack04.push(permutation[i]);
            }else{
                return false;
            }
        }
        // 문제에서는 되는지 안되는지만 판별하라고 했기에 여기까지이지만
        // 정렬된 값을 구하고 싶다면
        // 위에서 스택에 정리한 뒤 모든 값을 다 넣을 수 있다면
        // 4개의 스택 peek() 값을 비교하여 제일 큰 값 먼저 뒤로 배치를 반복하기
        return true;
    }
}

문제 풀이:

먼저 주어진 배열을 for문을 통해 4개의 stack에 push 한다.

이때

1. stack이 비어있다면 그냥 배열의 i번째 값을 push 한다.

2. 해당 stack이 비어있지 않으면 stack의 peek 값과 배열의 i번째 값을 비교하여 배열의 i번째 값이 더 크다면 push한다.

2. 배열의 값이 더 작다면 다음 stack 과 비교한다. (해당 값을 넣을때까지 다음 스택으로 넘어가며 1~2 진행)

3. 모든 stack과 비교했음에도 배열의 i번째 값을 넣지 못했다면 for문을 나와 false를 return 한다.

4. 만약 stack에 값을 넣었다면 배열의 i+1번째 값을 1번부터 다시 진행하여 for문을 진행한다.

 

 

2. 프로그래머스 : 같은 숫자는 싫어 

package baekjoon.dataStructure.stack;
import java.util.*;
public class programmers_같은숫자는싫어 {
    /*
        < 프로그래머스 : 같은 숫자는 싫어 >
        문제 분류 :  stack / queue
        주어진 배열 arr에서 연속되는 수가 있을때 숫자 하나만 남기고 전부 제거
        ex) arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return
    */
    public int[] solution(int []arr) {
        Stack stack = new Stack();
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (stack.empty() || ((int) stack.peek() != arr[i])) {
                stack.push(arr[i]);
                count++;
            }
        }
        int[] answer = new int[count];
        for (int i = 0; i < count; i++) {
            answer[count - 1 - i] = (int) stack.pop();
        }

        return answer;
    }
}

문제 해설 : 

1. for 문을 돌려 stack의 peek값과 해당 배열의 값을 비교한다.

2. peek값과 배열의 값이 같으면 넘어가고, 같지 않다면 stack에 해당 값을 push 한다.

3. 연속된 중복된 수가 제거 된 상태로 stack에 저장되었으므로 해당 stack의 값을 새로운 배열에 뒤에서부터 값을 옮긴다(stack은 LIFO이므로)