[DataStructure] 스택 & 큐 (Stack & Queue)

오늘은 다른 알고리즘에서 많이 사용되기 때문에 꼭알아야할 자료구조인 Stack과 Queue에 대해서 알아보자

---

Stack

퇴적(堆積)

스택 어떤 것을 쌓아 올림을 뜻하는 단어이다.

데이터들을 저공간에 쌓아 올리는 방식이다.

코딩에서는 list 즉 배열에 데이터를 담는 방식이다.

array = {1,2,3,4,5};
stack = {1,2,3,4,5};

 

위 코드는 배열과 스택에 1부터 5까지의 정수를 담아뒀다. 2개는 차이가 없다. stack은 array와 값을 저장하는 방식이 같다.

그럼 왜 stack이라고 부를까?

LastInFirstOut(LIFO) 즉 마지막으로 담은 데이터를 처음으로 빼는 배열이 있다면 그것이 바로 stack이다.

이를 후입선출 이라고 부른다.

---

1. 스택 동작 방식

스택은 크게 2가지 행동을 한다.

배열의 아래부터 순서대로 값을 넣을때 이런 두가지 행동이 배열의 가장 위 일어난다.

접시에 팬케이크를 층층히 담는것처럼 위에서부터 담기고 위에서부터 먹는다.

1. push :
   값을 스택의 위에서 넣는다.
2. pop :
   값을 스택의 위에서 빼서 가져온다.

(pop하지 않고 위의 값을 확인하는 법도 있다. 이는 어떤 언어로 코딩하냐에 따라 다르다는 걸 기억하자)

다음은 스택의 2가지 행동을 했을때 값이 변화하는 모습을 보여주겠다.

 

처음에 배열에 값이 [1,2,3] 순서대로 존재했다고 치자

차래대로 push 4, pop, push 5을 수행했다.

1. push 4
   4를 stack의 가장 위에 넣는다.
2. pop
   stack의 가장 위에 값인 4를 뺀다.
3. push 5
   5를 stack의 가장 위에 넣는다.

그럼 이러한 과정을 코드로 한번 보자

---

2. 스택 코드

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

 

위코드는 Int형 값이 들어가는 stack을 코드로 구현했다. 그럼 Stack에 처음부터 값을 담아둘수는 없을까?

List<Integer> elements = Arrays.asList(1, 2, 3);
Stack<Integer> stack = new Stack<>();
stack.addAll(elements);

 

1,2,3이 담겨져 있는 List를 선언한 후 stack에 넣어준다. 

stack.push(4);
stack.pop();
stack.push(5);

 

stack에 4를 넣어주고 pop해서 빼고 stack에 다시 5를 넣어두는 모습이다.

간단하지 않은가? 값을 빼는고 넣는 위치가 어디인지, LIFO 후입선출리스트라는 것을 기억하자

---

3. 응용 해보자

스택을 활용하는 대표적 문제인 괄호 문제를 풀어보자

프로그래머스

 

그럼 설계를 해보자

알고리즘 문제해결의 중요한 방법은 문제를 작은 단위로 쪼개야 한다.

이 문제의 가장 중요한 점은 괄호들짝이 맞는지 확인하는 것이다.

 

1. 그럼 어떤식으로 확인 할까?

괄호가 있다면 시작은 '('로 시작한다. 이 '('를 스택에 push하면 된다. '(' 이렇게 혼자 있어도 괄호는 닫힐 수 있고 '((('이렇게 3개가 같이 있어도 괄호는 닫힐 수 있다.

Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++){
if ('(' == c){
	stack.push('(')
}

 

2. 그럼 닫는 괄호는 어떻게 사용할까?

')'이것이 나온다면 스택의 가장 마지막 값을 확인한다. 스택의 마지막 값이 '('여는 괄호라면 스택을 pop한다 괄호가 닫혔으니 완성된 괄호이고 이는 더이상 볼 필요가 없으니까 괄호를 빼준다. 즉 ')'를 스택에 넣지 않고 스택의 '('를 빼준다.

static boolean solution(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (stack.isEmpty()){
            stack.push(c);
        }
        else {
            if (')' == c && stack.peek().equals('(')){
                stack.pop();
            }else{
                stack.push(c);
        	}
        }
    }
}

 

3. 그럼 올바르지 않는 괄호는 어떻게 알 수 있을까?

올바른 괄호일경우 '('와 ')'는 전부다 맞는 짝을 찾아서 사라졌을 것이다. 주어지는 문자열의 처음부터 끝까지 확인 했을 때 스택에 어떠한 괄호가 남아있다면 짝이 맞지 않아서 남아있는 것이니 올바르지 않다는 것을 출력해준다.

static boolean solution(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (stack.isEmpty()){
            stack.push(c);
        }
        else {
            if (')' == c && stack.peek().equals('(')){
                stack.pop();
            }else{
                stack.push(c);
        	}
        }
    }
    return stack.isEmpty();
}

 

지금을 설명을 위해서 코드를 단계별로 바로바로 짠것처럼 적어뒀다. 하지만 코딩을 하기전엔 무조건 설계를 한뒤에 짜야한다는 것을 기억하자

---

Queue

대기행렬( 待機行列 )

Queue는 영어로 대기열 또는 줄이라는 의미이다.

데이터들이 한줄로 표를 사기위해서 서있는 모습을 상상해보자

[1->2->3->4->5]

 

위 자료구조는 숫자가 커지는 순서대로 넣었다 위의 스택에서는 가장 마지막에 넣은 5부터 나왔지만 이번엔 가장 먼저넣은 1부터 나온다.

FirstInFirstOut(FIFO) 즉 처음으로 넣은 값을 처음으로 빼는 자료구조가 있다면

이를 선입선출이라고 부른다.

 

왜 배열이라고 안하고 자료구조라고 하는지 궁금하면 열어보자

위 자료구조는 링크드 리스트로 자주 구성된다. 배열을 사용할때 가장 앞의 값을 삭제하게되면 index를 한칸씩 땡겨야해서 O(N)의 시간 복잡도가 걸리게 되지만 링크드 리스트는 연결을 끊어도 시간 복잡도가 O(1)이 걸리기 때문에 시간적인 이득이 있다. 하지만 배열처럼 값을 순서대로 읽을 때 손해가 많이 발생한다. 모든 것엔 장단점이 있으니 장단점을 잘 보고 사용하자.

---

1. 큐 동작 방식

Queue도 2가지 행동을 한다.

자료구조의 아래부터 순서대로 값을 넣을때 이런 두가지 행동이 자료구조의 양 끝에서 일어난다.

표를 먼저 사러온사람이 먼저 사고 나중에 온사람이 나중에 사는 것처럼 한다.

1. Enqueue :
   값을 자료구조의 마지막에 넣는다.
2. dequeue :
   값을 자료구조의 처음에서 빼서 가져온다.

(pop하지 않고 처의 값을 확인하는 법도 있다. 이는 어떤 언어로 코딩하냐에 따라 다르다는 걸 기억하자)

(양뱡향 큐를 구성하면 뒤에 넣기 앞에 넣기 뒤에서 빼기 앞에서 빼기 둘다 가능하다.)

다음은 queue의 2가지 행동에 따른 자료구조의 변화를 보여주겠다.

처음에 queue에 1,2,3 순서대로 값이 담겨져 있었다.

차래대로 pop, push(4), pop이 이루어 졌다.

1.  pop
   가장 먼저 들어가 있었던 1이 나온다.
2. push 4
   가장 위에 4를 넣는다.
3. pop
   남은 숫자 중 가장 먼저 들어가 있었던 2가 나온다.

그럼 이러한 과정을 코드로 한번 보자

---

2. 큐 코드

Queue<Integer> queue = new LinkedList<>();

 

위 코드는 LinkedList를 사용해서 Int형 값들을 담는 큐를 생성한다. 이번에도 한번에 초기 값을 담아두는 법을 알려주겠다.

Integer[] elements = {1, 2, 3};
Queue<Integer> queue = new LinkedList<>();
Collections.addAll(queue, elements);

 

1,2,3이 담겨져 있는 List를 선언한 후 에 넣어준다. 

queue.poll();
queue.add(5);
queue.poll();

 

poll을 통해서 dequeue 를 구현하고 add을 통해서 Enqueue를 구현한다.

간단하지 않은가? 값을 빼는고 넣는 위치가 어디인지, FIFO 자료구조라는 것을 기억하자
(양방향 큐, 회전 큐 같은것도 있다는 것을 기억하)

---

3. 응용 해보자

큐 활용하는 문제를 풀어보자. 두 큐 합 같게 만들기라는 큐를 사용하는 문제이다.

프로그래머스

그럼 문제를 분석해보자

1. 같은 길이 두개 큐가 주어진다.
2. 큐한곳에서 값을 출해서 다른 곳에 값을 넣는다.
3. 2개의 큐를 같은 값으로 만들어야 한다.
4. 2번을 행한 횟수를 기억해서 출력해야 한다.
5. 같게 만들수 있는 방법이 없는지 알아야 한다.

크게 5가지 세부적인 문제로 나눌수 있다.

그럼 이 분석을 토대로 설계를 해보자

1. 같은 길이 두개 큐가 주어진다.
   문제에서는 int[]형 배열로 주어지니 que에 담아야 한다. 
2. 큐한곳에서 값을 출해서 다른 곳에 값을 넣는다.
   큐의 값을 뺴서 다른 곳으로 넣는 로직을 구현해야 한다.
3. 2개의 큐를 같은 값으로 만들어야 한다.
   2개의 큐의 값을 비교하는 방법을 구현해야한다. 매번 값을 계산하면 시간이 많이 걸리니 각 큐의 전체 값을 저장하는 변수를 만들어야 한다. 문제를 보면 오버플로우 가능성이 있기 때문에 int가 아닌 long type를 사용한다. 이 전체 값을 저장하는 변수를 비교하면서 큰 큐에서 작은 큐로 값을 넣어주면서 비교해준다.
4. 2번을 행한 횟수를 기억해서 출력해야 한다.
   answer에 횟수 값을 저장한다.
5. 같게 만들수 있는 방법이 없는지 알아야 한다.
   answer값이 얼마정도 초과하면 더이상 행할 수 없는 것이니 정지하는 로직을 만든다.

위 방식을 따라가서 코드를 만들 수 있다. 주석으로 세부적 문제를 어디서 사용했는지 적어뒀다.

import java.util.*;

class Solution {
    public static int solution(int[] queue1, int[] queue2) {
        int answer = 0; //4번
        long que1Value = 0; //3번
        long que2Value = 0;
        Queue<Integer> que1 = new LinkedList<>(); //1번
        Queue<Integer> que2 = new LinkedList<>();
        for (int i = 0; i < queue1.length; i++){
            que1.add(queue1[i]);
            que1Value += queue1[i];
            que2.add(queue2[i]);
            que2Value += queue2[i];
        }

        while(true) {
            if (que1Value > que2Value){ //3번
                int temp = que1.poll(); //2번
                que1Value -= temp;
                que2Value += temp;
                que2.add(temp);
            } else if (que1Value < que2Value) {
                int temp = que2.poll(); //2번
                que2Value -= temp;
                que1Value += temp;
                que1.add(temp);
            } else{
                return answer;
            }
            answer += 1;
            if (answer > 600000){ //5번
                return -1;
            }
        }
    }
}

 

그럼이제 que를 자연스럽게 사용해보자