신입 개발자 기술면접 질문 정리 - 자료구조

목차

• Stack 클래스를 손코딩으로 구현해주세요.
• Priority Queue (우선순위 큐)에 대해 설명해주세요.
• Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요.

1. Stack 클래스를 손코딩으로 구현해주세요.

public class Stack{

    private static int MAX_STACK_SIZE = 10;
    private int top;
    private int[] data = new int[MAX_STACK_SIZE];

    public Stack() {
      top = -1;
    }

    public void push(int data_) throws Exception {
      if(isFull()){
          throw new Exception("스택이 가득 찼습니다.");
      }
      data[++top] = data_;
    }

    public int peek() throws Exception {
      if(isEmpty()){
        throw new Exception("스택이 비었습니다.");
      }
      return data[top];
    }

    public boolean isEmpty(){
      return top == -1;
    }

    public boolean isFull(){
      return top == MAX_STACK_SIZE - 1;
    }

    public int size(){
      return top + 1;
    }
}

2. Priority Queue (우선순위 큐)에 대해 설명해주세요.

• 우선순위 큐는 자료구조의 일종으로, 각각의 요소가 우선 순위를 가지고 있고,
  우선 순위가 높은 요소가 먼저 나가는(처리되는) 구조를 말한다.
• 표준 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조를 가지지만,
  우선 순위 큐는 요소들이 순서에 상관 없이 우선 순위에 따라 나가는 구조로 작동

1) 특징

• 요소를 삽입하거나 삭제할때, 그 요소의 우선 순의를 고려하여 처리한다.
• 우선 순의 기준은 사용자가 정의할 수 있으며, 숫자, 알파벳 순서등 다양한 기준이 사용될 수 있다.
• 보통 힙이라는 자료구조를 사용하여 구현된다.
  • 힙을 사용하는 이유는 우선 순위가 가장 높은 요소에 대한 접근, 삽입, 삭제를 효율적으로 처리하기 위함이다.

2) 예제

import java.util.PriorityQueue;

public class Example {

    public static void main(String[] args){

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(4);
        pq.add(20);
        pq.add(2);

        while(!pq.isEmpty()){
          System.out.println(pq.poll());      // 2, 4, 20 순으로 출력
        }
    }
}

3. Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요.

1) Stack

• 웹 브라우저 방문기록 : 사용자가 뒤로가기 버튼을 누를때, 가장 최근에 방문한 페이지로 돌아가는 기능에 사용
• 역순 문자열 생성 : 문자열을 역순으로 만들때, 문자들을 스택에 넣었다가 모두 꺼내어 새로운 문자열 생성
• 실행 취소기능 : 프로그램에서 사용자의 최근행동을 취소하는 기능
• 함수 호출 관리 : 프로그램에서 함수를 호출할 때, 호출된 함수의 정보(반환주소, 매개변수)를 스택에 저장하여 관리

2) Queue

• 프린터 출력 작업 관리 : 여러 문서의 인쇄 요청이 있을때, 처음 요청된 문서부터 차례대로 인쇄하는 데 큐를 사용
• 키보트 버퍼 : 사용자가 키보드로 입력하는 데이터를 순서대로 처리하기 위해 큐 사용
• 운영체제의 프로세스 관리 : 운영체제가 여러 프로세스를 관리할 때, 작업의 순서를 정하기 위해 큐를 활용

출처

신입 개발자 기술면접 질문 정리 - 자료구조