[Zero-Base #01] 스택

이번 제로베이스에서는 자료 구조 중 스택이라는 것에 대해 배우는 시간이었다.

 

자료구조에는 흔히 배열, 스택(LIFO), 큐 (FIFO) 가 있다.

그중 스택에 대해 정리해보려 한다.

 

스택

- LIFO(Last In First Out) : 후입 선출, 마지막에 삽입된 것을 먼저 내보내는 것

- 데이터를 역순으로 처리할 때 사용한다.

 

스택 연산

CreatS 연산 => 빈 스택을 생성하고 반환, 스택의 크기를 정할 수 있다 (컴파일 시)

PUSH 연산 => 스택의 공간에서 삽입을 담당

POP 연산 => 스택의 공간에서 삭제를 담당

 

스택의 사용

- 시스템 스택 : 함수의 호출과 복귀 순서는 스택의 구조를 응용하여 관리할 수 있다

- 그외 : 역순 문자열 만들기, 수식의 괄호 검사, 수식의 후위 표기법 변환

 

*스택 오버플로우는 무엇인가?

스택 포인터가 스택의 경계를 넘어 설 때 일어나는 것, 호출 스택은 제한된 양의 주소공간을 이루며 프로그램 시작 시 결정된다.

 

그외 : https://hellowworlds.tistory.com/170

 

필수 문제

포스택

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in); //받는 숫자
        int n = scan.nextInt();

        //순열 A
        ArrayList<Integer> listA = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            listA.add(scan.nextInt());
        }

        //네 개의 스택
        Stack<Integer>[] stacks = new Stack[4];
        
        //네 개의 스택 0으로 초기화
        for(int i = 0; i < 4; i++){
            stacks[i] = new Stack<>();
            stacks[i].push(0);
        }

        for(int i = 0; i < listA.size(); i++){ //순열 A 돌리기
            boolean possible = false;
            
            for(int j = 0; j < 4; j++){ //스택 쌓기
                if(listA.get(i) > stacks[j].peek()){ //스택에 삽입할 값이 peek 보다 크면 삽입
                    stacks[j].push(listA.get(i));
                    possible = true;
                    break;
                }
            }
            
            if (!possible){ //모든 스택에 삽입하지 못했다면
                System.out.println("NO");
                return;
            }
        }

       System.out.println("YES");
    }
}

 

추가 문제

같은 숫자는 싫어

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]); //첫번째는 그냥 입력
        
        for(int i = 1; i < arr.length; i++){
            if(arr[i - 1] != arr[i]){ //두번째부터 비교하면서 입력 (그 전에 입력했던 값과 비교)
                list.add(arr[i]);
            }
        }
        
        int[] answer = list.stream().mapToInt(i->i).toArray(); //int 배열로 변환
        
        return answer;
    }
}