[JAVA] Stack이란 ? (사용법, 관련 문제 풀이)

Stack

 

오늘 stack에 대해 배우면서, 정의와 사용법에 대해 간단히 정리해보고 문제 풀이를 올리려고 한다.

Stack과 Queue

 

먼저, Stack은 이름에서도 느껴지는 것처럼 쌓아 올리는 자료구조를 말한다.

 

쉽게 이해하려면, 접시를 쌓아올린다고 생각하면 된다. 그림에서 보는 것과 같이 밑부분이 막혀있는 상자에 접시를 쌓아올리면 새로운 데이터를 넣을 때도 가장 위에 넣고 데이터를 빼낼때도 가장 위에서 빼게 된다.

 

이러한 자료구조를 LIFO(Last In First Out)이라고 한다.

 

이런 Stack과 자주 비교되는 Queue는 FIFO 자료구조로, 터널에 비유해서 이해할 수 있다.

---

💻 Stack 사용법

 

import java.util.Stack;

public class Stack {
	public static void main(String[] args) {
    	Stack<Integer> stack = new Stack<>();
    }
}

 

stack은 java.util.Stack 클래스를 import하고 Stack을 위와 같이 선언해 사용할 수 있다.

---

📃 Stack 관련 메소드

 

데이터 추가, push()

 

가장 먼저,데이터를 추가하기 위해서는 push() 메서드를 사용한다. push(E e) 메서드를 사용해 새로운 원소값을 넣어주면, 가장 위에 데이터가 위치하게 된다. 이렇게 Stack에서 가장 위에 있는 데이터를 Top이라고 부른다. 

 

import java.util.Stack;

public class Stack {
	public static void main(String[] args) {
    	Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < 3; i++) {
        	stack.push(i);
        }
    }
}

 

위 코드는 stack에 0, 1, 2를 차례로 넣는 동작을 수행하고 있다.

 

데이터 조회, peek()

 

데이터를 추가해주면 이를 조회하는 메서드 역시 필요하다. 스택에서는 peek()이라는 메서드를 사용해서 Top 데이터를 조회할 수 있다. 

 

import java.util.Stack;

public class Stack {
	public static void main(String[] args) {
    	Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < 3; i++) {
        	stack.push(i);
        }
        
        System.out.print(stack.peek() + " ");
	System.out.print(stack.peek() + " ");
    }
}

 

결과 : 4 4

 

peek()을 사용하면, 가장 위(최근) 데이터를 조회만 하기 때문에 위와 같이 작성하면 모두 4가 나온다.

 

데이터 빼내기, pop()

 

데이터를 빼내기 위해서는 pop()메서드를 사용한다. 

 

import java.util.Stack;

public class Stack {
    public static void main(String[] args) {
    	Stack<Integer> stack = new Stack<>();
    	
    	for (int i = 0; i < 3; i++) 
	    stack.push(i);
			
        while(!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

 

결과 : 2 1 0

 

위에서 나오는 isEmpty()는 stack이 비었는지 원소를 가지고 있는지를 확인해준다. 원소가 비어있다면 true를 반환한다.

나는 stack이 비어있지 않으면 계속 stack의 원소를 빼낼 것이므로 !stack.isEmpty()를 while 반복해 print 한다.

 

주의할 점은 stack의 경우 가장 최근(뒤)의 원소를 빼내기 때문에 흔히 생각하는 0 1 2로 출력되는게 아닌, 2 1 0으로 출력된다는 것이다 ! 이와 관련해서 문제를 풀어보면서 감을 익혀보자

 

---

📌 문제 풀이

프로그래머스 stack 문제 링크 (stack으로 풀어볼 것)

프로그래머스

 

항상 알고리즘 공부를 할 때 문제를 같이 푸는 습관을 들여야 한다고 생각하기 때문에, 이론 공부를 한 뒤에 바로 찾아 풀어보았다. stack 공부를 하고 있는 분이라면 풀이를 보기 전에 stack을 사용해 위의 문제를 풀어보시기를 권장 드린다.

 

문제 설명

 

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 

이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 

단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 

 

예를 들면,
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 

문제 풀이

 

 

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        
        Stack<Integer> stack = new Stack<>();
        
        for(int i : arr) {
            if(stack.isEmpty() || i != stack.peek()) {
                stack.push(i);
            }
        }
        
        int[] answer = new int[stack.size()];

        for(int i = stack.size() -1; i >= 0; i--) {
            answer[i] = stack.pop();
        }
        
        return answer;
    }
}

 

1. stack 선언 후 arr 길이만큼 foreach문을 사용한다.

• stack의 top 데이터가 i(기존 배열에서 가져온 값)와 같지 않다면, stack에 i 값을 넣어준다.
• 가장 처음에는 stack이 비어있기 때문에 그냥 stack.peek()로 비교하면 EmptyStackException이 발생한다. 그러니까 비어있는지도 함께 확인 해준다. => stack.isEmpty()

2. stack의 크기만큼 int 배열을 선언해준다.

3. stack의 크기를 n이라고 가정할 때, index i를 n-1부터 0까지 반복하도록 하여 정답 배열에 stack원소들을 넣어준다.

• stack은 최근 값부터 불러오기 때문에, index를 역으로 설정하지 않으면 배열이 거꾸로 들어가게 된다.
• ⭐ 이 부분이 문제에서 가장 주의해야 할 점이자 stack의 정의에서 핵심적인 부분이라고 볼 수 있다.  ⭐

---

출처

1. stack, queue 이미지

https://velog.io/@lsx2003/%EC%8A%A4%ED%83%9DStack-%EA%B5%AC%ED%98%84

[자료구조] Stack