[자료구조] 스택과 큐

안녕하세요 코밑이에염!

다시 기여운 모루카쟝과 함께 돌아왔습니다!

 

오늘 알아볼 것은 스택과 큐에요!

자료구조를 공부하고 있는 여러분도 한번씩은 들어봤을 거라고 생각하고 있습니당

 

그림으로 먼저 보시죠!

스택

 

먼저 스택입니다!

스택은 원통 안에 차곡차곡 쌓아올린다고 생각하면 이해하기 쉬워요!

먼저 들어가면 가장 나중에 나온답니다!

이것을 LIFO(Last In First Out), 후입선출 방식이라고 해요

 

값을 스택에 넣을때는 push

뺄 때는 pop이라고 한답니다

 

최근에 프로그래머스의 같은 숫자는 싫어를 스택을 이용해서 풀었지요

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

 

배열 안에는 여러 숫자들이 있구요

연속한 같은 숫자를 하나만 남기고 돌려주면 됩니다!

어렵지 않은 문제에요

import java.util.*;

public class Solution {
	public int[] solution(int[] arr) {
		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < arr.length; i++) {
			list.add(arr[i]);
		}
		for (int i = 0; i < list.size() - 1; i++) {
			if (list.get(i) == (list.get(i + 1))) {
				list.remove(i + 1);
				i--;
			}
		}
		System.out.println(list);
		int[] answer = new int[list.size()];

		for (int i = 0; i < list.size(); i++) {
			answer[i] = list.get(i);
		}

		return answer;
	}
}

 

처음엔 뭣도 모르고 무지성 어레이리스트를 갖다 박았어요 ㅜㅜ

효율성 테스트에서 통과를 못해서 처음엔 억까당하는 줄 알았습니다 ㅜㅜㅜㅜ

 

다시 문제를 보니 스택을 사용하는 문제였더라구요

import java.util.*;
class Solution { // 같은 숫자는 싫어
	public int[] solution(int[] arr) {

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

		for (int i = 0; i < arr.length; i++) {
			// 스택 안이 비어있거나 스택의 가장 위가 다른 값이라면
			if (stack.isEmpty() || stack.peek() != arr[i]) {
				stack.push(arr[i]); // 스택에 값을 추가한다
			}
		}
		int[] answer = new int[stack.size()]; 
		for (int i = 0; i < stack.size(); i++) { //스택 이사시키기 
			answer[i] = stack.get(i);
		}
		return answer;
	}
}

 

그래서 스택을 이용해 다시 풀었더니 바로 성공해버렸습니다~!

 

간단한 설명을 하자면

peek()을 이용해 스택의 가장 위의 값을 확인할 수 있는데

현재의 값과 다른 값이라면 스택에 추가해주면 되죵

 

 

큐 (기여운 폴아저씨)

다음은 큐에요!

큐는 빨대를 생각하면 이해하기가 쉽답니다

먼저 들어간 값은 먼저 나오게 되어있어요!

이것을 FIFO(First In First Out), 선입선출 방식이라고 해요!

 

값을 스택에 넣을때는 offer

뺄 때는 poll이라고 한답니다

 

그럼 안농~