IM 7일차 (Stack, Queue)

1. Stack

 

  스택은 자료 구조의 일종으로, 마지막에 삽입된 항목만을 제거하고 접근할 수 있다.

  이러한 원리를 후입 선출(Last In First Out)이라고 부른다.

 

  스택은 속도가 빠르다는 점이 장점이다. 마지막 항목이 제거될 것을 알기 때문에 찾기와 삽입이 상수 시간인 O(1)이다.

  스택의 주요 메서드는 두 가지가 있다. 바로 Push와 Pop이다.

 

  1 - 1) push

    

    스택의 가장 마지막 인덱스에 데이터를 추가해준다.

 

  1 - 2) pop

 

    스택의 가장 마지막 인덱스의 데이터를 삭제한다.

 

  스택의 push와 pop 메서드 모두 마지막 인덱스에서 일어나므로 시간 복잡도는 O(1)이 된다.

  반면 특정 인덱스, 즉 예를 들어 n번째 데이터에 접근하기 위해서는 pop 메서드를 n번 호출해야 하므로 시간 복잡도는 O(n)이 된다.

 

 

 

2. Queue 

 

  큐는 스택과 달리 첫 번째 항목만을 제거할 수 있는 자료 구조다.

  이러한 원리를 선입선출(First In First Out)이라고 한다. 연산이 상수 시간이라는 점이 스택과 마찬가지로 장점이다.

  

  큐의 주요 메서드도 두 가지가 있다. 바로 Dequeue와 Enqueue이다.

 

  2 - 1) dequeue

    

    스택의 첫 번째 데이터를 삭제한다.

 

  2 - 2) enqueue

 

    스택의 가장 마지막 인덱스의 데이터를 추가한다.

 

  Queue의 dequeue와 enqueue 메서드도 스택과 마찬가지로 첫 번째 or 마지막 인덱스에서 일어나므로 시간 복잡도는 O(1)이 된다.

  반면 특정 인덱스, 즉 예를 들어 n번째 데이터에 접근하기 위해서는 dequeue 메서드를 n번 호출해야 하므로 시간 복잡도는 O(n)이 된다.

 

 

 

스택과 큐의 구현은 사실 크게 어렵지 않아서 따로 코드를 첨부하진 않아도 될 것 같다.