Stack

Stack이란?

스택이란 단어적인 뜻은 "쌓아놓은 더미"라는 뜻이다. 접시를 놓을 때는 제일 위에 놓고, 더미에서 꺼낼 때도 제일 위에 있는 접시를 꺼내는 것과 동일하게 생각하면 된다.

알고리즘에서도 동일하게 접시 -> 데이터만 바뀌고 동일하게 생각하면, 마지막으로 들어온 데이터가 먼저 나가는 구조 즉 LIFO(Last In First Out)이다.

주로 push()를 통해 데이터를 넣고 pop()을 사용해서 꺼내며, 단순히 맨 위의 데이터를 확인할 때는 peek()을 사용한다.

일상에서 Stack을 사용하는 대표적인 예시로는 브라우저 뒤로가기, 작업 취소(UNDO), 괄호 짝 검사 등이 있다.

Java에서의 Stack 및 Queue 사용

자바에는 Stack, Queue이라는 Class가 존재해서 그냥 단순하게 사용해도 되지만, Stack, Queue 클래스는 옛날에 만들어진 Legacy Class이기에 설계 방식이 현대적인 기준에 맞지 않고

public class Stack extends Vector { ... }

vector를 상속받아서 만들어진 클래스이기에 성능이 떨어지기에 Deque 클래스를 보통 사용한다.

cf) Vector 기반이면 성능이 떨어지는 이유???

• 모든 메서드가 synchronized -> 불필요한 락이 걸림 -> 느림
• Vector의 확장 방식 (구식)
• Stack은 Vector를 상속해서 여러 메서드가 섞여 있음(불필요 메서드가 너무 많음)

Stack 알고리즘의 코드 예시

https://www.acmicpc.net/problem/10828

Stack을 이용한 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class boj_10828 {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();

      int N = Integer.parseInt(br.readLine());
      Deque<Integer> stack = new ArrayDeque<>();

      for (int i = 0; i < N; i++) {
          String[] arr = br.readLine().split(" ");

          switch (arr[0]) {
              case "push":
                  stack.push(Integer.parseInt(arr[1]));
                  break;

              case "pop": {
                  Integer temp = stack.pollFirst();
                  sb.append(temp != null ? temp : -1).append('\n');
                  break;
              }

              case "size":
                  sb.append(stack.size()).append('\n');
                  break;

              case "empty":
                  sb.append(stack.isEmpty() ? 1 : 0).append('\n');
                  break;

              case "top": {
                  Integer temp = stack.peekFirst();
                  sb.append(temp != null ? temp : -1).append('\n');
                  break;
              }
          }
      }

      System.out.print(sb);
      br.close();
  }
}

Stack에서 사용하는 함수들

사용한 메서드	원래 위치	역할(기능)	스택에서의 의미	리턴값 / 예외
push(E e)	Deque 기본 메서드	요소를 맨 앞(front) 에 삽입	스택의 push(top에 넣기) 역할	성공 시 void
pollFirst()	Deque	맨 앞(front)의 요소를 제거하고 반환	스택에서 pop (top 제거) 역할	비어있으면 null
peekFirst()	Deque	맨 앞(front)의 요소를 제거하지 않고 반환	스택의 top(peek) 역할	비어있으면 null
size()	Collection	요소 개수 반환	스택의 size	int
isEmpty()	Collection	비어있는지 확인	스택이 비었는지 확인	boolean

cf) pop()을 사용하지 않고 pollFirst()를 사용하는 이유?
Stack이 비어있는 경우 pop()을 하게 되면 null값을 반환해주는 것이 아닌 NoSuchElementException 예외가 발생하기에 예외처리를 해주어야 한다.
하지만 pollFirst()의 경우 null 값을 반환하기에 Integer로 변수를 선언하면 되기에 훨씬 안전하고 처리하기가 편하기에 pop() 메서드 대신 pollFirst()를 사용하는 것이 좋다.

Queue

Queue란?

Queue는 단어 그대로 줄, 대기열이라는 뜻을 가진다.
은행 창구에서 번호표를 뽑고 순서대로 기다리거나, 버스를 타기 위해 줄을 서는 것을 떠올리면 이해하기 쉽다.

가장 먼저 줄에 선 사람이 가장 먼저 서비스를 받는 것처럼, 알고리즘에서도 먼저 들어온 데이터가 먼저 나가는 구조, 즉 FIFO(First In First Out) 방식으로 동작한다.

Queue에서는 데이터를 뒤에 넣을 때 offer(), 맨 앞의 데이터를 꺼낼 때 poll(), 단순히 맨 앞 데이터를 확인할 때는 peek()를 사용한다.

일상에서 Queue 구조가 사용되는 대표적인 예시는 프린터 출력 대기열, 콜센터 전화 연결 대기 등이 있다.

스택이 마지막에 들어간 것이 먼저 나오는 LIFO 구조라면, 큐는 이와 반대로 먼저 들어간 것이 먼저 나오는 구조로, 두 자료구조는 서로 상반되는 특성을 가지고 있다.

Queue 알고리즘의 코드 예시

Queue를 이용한 구현

https://www.acmicpc.net/problem/10845

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class boj_10845 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Deque<Integer> queue = new ArrayDeque<>();

        // 1 <= N <= 10,000
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            String[] arr = br.readLine().split(" ");

            if (arr.length == 2) {
                queue.offer(Integer.parseInt(arr[1]));
            }
            else {
                switch (arr[0]) {
                    case "front":
                        Integer temp = queue.peek();
                        sb.append(temp != null ? temp : -1).append("\n");
                        break;
                    case "back":
                        temp = queue.peekLast();
                        sb.append(temp != null ? temp : -1).append("\n");
                        break;
                    case "pop":
                        temp = queue.pollFirst();
                        sb.append(temp != null ? temp : -1).append("\n");
                        break;
                    case "size":
                        sb.append(queue.size()).append("\n");
                        break;
                    case "empty":
                        sb.append(queue.isEmpty() ? 1 : 0).append("\n");
                        break;
                }
            }
        }

        System.out.println(sb);

        br.close();
    }
}

Queue에서 사용하는 함수들

사용한 메서드	원래 Deque 기능	큐에서의 의미(FIFO)	비었을 때 동작	리턴값
offer(E e)	뒤(back)에 요소 추가 (offerLast)	큐의 push 역할 (enqueue)	예외 없이 false 반환	boolean
peek()	맨 앞(front) 요소 조회 (peekFirst)	큐의 front 조회	null	E
peekLast()	맨 뒤(back) 요소 조회	큐의 back 조회	null	E
pollFirst()	맨 앞(front) 요소 제거 + 반환	큐의 pop(dequeue)	null	E
size()	요소 개수 반환	큐 크기	0	int
isEmpty()	비어있는지 확인	empty 명령 처리	true/false	boolean