[면접 스터디] 선형 자료구조

1. Stack과 Queue를 설명하고, 탐색,삭제,삽입의 시간복잡도는 어떻게 되는가?

Stack은 선입선출(Last-In-First-Out)구조로 먼저 들어온 데이터가 top의 위치하여 먼저 나간다. 삽입, 삭제는 O(1)의 가능하며 탐색은 O(N)의 시간이 소요된다. 함수 호출, 시스템 콜등에 stack이 사용된다.

Queue는 선입후출(First-In-FirstOut)구조로 먼저 들어온 데이터가 먼저 나간다. 마찬가지로 삽입, 삭제는 O(1)만의 가능하며 탐색은 O(N)의 시간이 소요된다. Queue는 BFS, 순서대로 처리해야 되는 상황등에 자주 사용된다.

이 둘의 자료구조는 링크드리스트로 구현 될 수 있다.

2. Queue로 Stack을 만들어라

메인 큐와 서브 큐, 두개의 큐를 만든다. 데이터가 입력 될 시, 메인 큐에 데이터들을 모두 서브 큐로 옮기고, 입력 데이터를 메인 큐에 저장 후 다시 서브큐에 데이터들을 메인 큐로 옮긴다.

1,2,3 가 순서대로 들어온다고 생각해보자.

• input 1 : 메인 큐에 1을 담는다.
• input 2 : 메인 큐의 1을 서브 큐에 이동시킨 후, 메인큐에 2를 삽입 후, 서브 큐에 2를 메인 큐로 옮긴다.
• input 3: 메인 큐의 데이터를 차례대로 서브 큐로 옮긴 후 메인 큐에 3을 삽입, 이후 서브 큐에 데이터들을 다시 메인 큐로 옮긴다.

public class Queue { 
  private Stack inBox = new Stack(); 
  private Stack outBox = new Stack(); 
  
  public void enQueue(Object item) { 
    inBox.add(item); 
  }
  
  public Object deQueue() { 
    if (outBox.isEmpty()) { 
      while(!inBox.isEmpty()) { 
        outBox.push(inBox.pop()); 
      } 
    } 
    return outBox.pop(); 
  } 
  
  public static void main(String[] args) { 
    Queue queue = new Queue(); queue.enQueue("A"); 					queue.enQueue("B"); queue.enQueue("C");
    System.out.println(queue.deQueue());
    System.out.println(queue.deQueue());
    System.out.println(queue.deQueue()); 
  } 

}
 

3. Linked List에서 가운데 Node 탐색은 어떻게 하는가?

1. 링크드리스트의 총 노드수를 저장하는 cnt 변수를 만들고, 이 변수의 1/2이 될 때까지 노드를 탐색한다.

2. 두개의 포인터를 사용한다. 하나는 노드를 하나씩 이동하고, 다른 하나는 노드를 두개 씩 이동한다. 두개 씩 이동하는 노드가 끝에 도달했을 때 다른 노드가 가르키고 있는 노드가 가운데 노드가 된다.

Reference

책 - 코딩인터뷰 완전분석
출처: https://creatordev.tistory.com/83
https://doublesprogramming.tistory.com/229