💚 자료구조 - 스택, 큐에 대해 설명하시오.

9) 자료구조 - 스택, 큐에 대해 설명하시오.

스택(stack)

LIFO(Last In First Out) 형태로 데이터를 저장하는 구조

• 주요 동작

  • push(value) : 데이터를 집어넣는 역할

  • pop() : 데이터를 빼내는 역할

  • peek(value) : 데이터를 빼내지 않지만 가장 최상단에 있는 데이터를 확인하는 역할

• 특징

  • 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 top으로 정한 곳을 통해서만 접근할 수 있다.

  • top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키며 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

  • 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.

  • 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하고 스택이 넘치는 경우 stack overflow라고 한다.

• 동작 방식

  

• 활용 예시

  • 웹 브라우저 방문기록(뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줌

  • 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력

  • 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소

  • 후위 표기법

  • 수식의 괄호 검사

• 코드

    Stack<Integer> stack = new Stack<>();
  
    stack.push(1); // 1
    stack.push(2); // 1 2 
    stack.push(3); // 1 2 3
  
    stack.pop(); // 1 2
    stack.peek(); // 2
  
    // 스택이 비어있는지 확인
    System.out.println(stackInt.isEmpty()); // false
  
    // 찾는 인덱스의 값
    System.out.println(stackInt.search(1)); // 2
  

큐(queue)

FIFO(First In First Out) 형태로 데이터를 저장하는 구조

순서 보장

• 주요 동작

  • enqueue : 데이터를 집어넣는 역할

    • add(value) : value를 맨 뒤에 넣음. 성공하면 true, 실패하면 예외 발생

    • offer(value) : value를 맨 뒤에 넣음. 성공하면 true, 실패하면 false 반환

  • dequeue : 데이터를 빼내는 역할

    • remove() : 맨 앞의 값을 반환 후 제거. 큐가 비어있다면 예외 발생

  • peek() : 데이터를 빼내지 않지만 이제 곧 꺼내게 될 데이터를 확인하는 역할

• 특징

  • 정해진 한 곳(top)을 통해 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

  • 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산 작업만 수행된다.

  • 여기서 큐의 리어에서 이루어지는 삽입 연산을 인큐(enQueue), 프론트에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 부름.

• 동작 방식

  

• 활용 예시

  • 우선 순위가 같은 작업 예약 (프린터의 인쇄 대기열)

  • 은행 업무

  • 콜센터 고객 대기시간

  • 프로세스 관리

  • 너비 우선 탐색(BFS)

  • 캐시 구현

• 코드

    Queue<자료형> q = new LinkedList<>();
  
    Queue<Integer> q = new LinkedList<>();
  
    q.add(1); // 성공시 true, 실패시 exception 반환
    q.offer(1); // 성공시 true, 실패시 false 반환
  
    q.remove(); // 삭제된 value / 공백 큐이면 Exception 발생
    q.remove(1); // 해당 값 삭제 후 true, 존재하지 않으면 false 반환
  
    q.poll(); // 삭제된 value, 공백 큐이면 null 반환
  
    q.element(); // 큐 head에 위치한 value / 공백 큐이면 Exception 발생
  
    q.peek(); // 큐 head에 위치한 value / 공백 큐이면 null 반환
  
    q.clear(); // 큐 초기화
  
    q.size(); // 큐 사이즈 반환
  
    q.contains(1); // 해당 값이 존재하면 true / 존재하지 않으면 false 반환
  
    q.isEmpty(); // 공백 큐이면 ture / 아니면 false 반환 
  

에러

StackOverflowError : 스택 메모리 공간을 다 썼을 때 발생하는 에러

❓: 대부분 재귀함수(recursive function)에서 탈출 못해서 발생

public class Fibonacci {

    public static int recurFibo(int n) {
        if (n <= 1) {
            return n;
        } else {
            return recurFibo(n - 1) + recurFibo(n - 2);
        }
    }

    public static void main(String[] args) {
        int n = 10; 
        for (int i = 0; i < n; i++) {
            System.out.print(recurFibo(i) + " ");
        }
    }
}

피보나치 수열에서 n번째 항목이 어떤 값을 가지는지를 계산하는 함수로 재귀 함수의 전형적인 예를 코드로 가져왔다.

recurFibo()라는 함수를 내부에서도 호출을 하고있다. 이렇게 자기 자신을 함수 내부에서 호출하는 것을 재귀함수라고 하고 중요한 부분은 if(n<=1) 처럼 탈출조건이 존재한다.

하지만 개발을 하다 탈출 조건을 적기 까먹거나 잘못 적어서 함수 호출은 시작했지만 끝이 존재하지 않아 스택 메모리를 다 썼을 때 StackOverflowError 가 발생한다.

❗ : 즉, 해결 방법은 탈출 조건을 잘 명시하면 된다!

---

OutOfMemoryError : Java의 힙(heap) 메모리를 다 썼을 때 발생

여기서 힙(heap) 메모리는 객체가 거주하는 메모리 영역임

❓ : 내부적으로 큐를 사용했는데 큐에 데이터가 계속 쌓이기만 한다면 발생한다.

❗ : 해결 방법은 큐 사이즈를 고정하면 된다.

하지만 큐가 다 찬다면 어떻게 해결 해야될까?

• 예외(exception) 던지기

• 특별한 값(null or false) 반환

• 성공할 때까지(큐에 공간이 생길 때까지) 영원히 스레드 블락(대기)

• 제한된 시간만 블락(block)되고 그래도 안되면 포기

Java에서 이런 4가지 방식을 구현한 몇몇 클래스들이 있는데 그 중에 하나가 LinkedBlockingQueue이다.