스택과 큐

1. 스택

특징

LIFO 구조

입력과 출력이 한 곳에서만 발생한다. (top)

삽입 연산을 push, 삭제 연산을 pop이라고 부른다.

 

시간복잡도

원소 접근: O(N)

원소 삽입, 삭제: O(1)

 

원하는 순서 혹은 데이터를 찾으려면 순차적으로 접근해야 한다 -> 최악의 경우 O(N)

삽입과 삭제는 한 곳에서만 발생한다 -> O(1)

2. 큐

특징

FIFO 구조

입력은 맨 뒤(rear), 출력은 맨 앞(front)에서만 발생한다.

삽입 연산을 enqueue, 삭제 연산을 dequeue라고 부른다.

 

시간복잡도

원소 접근: O(N)

원소 삽입, 삭제: O(1)

 

원하는 순서 혹은 데이터를 찾으려면 순차적으로 접근해야 한다 -> 최악의 경우 O(N)

삽입과 삭제는 각각 한 곳에서만 발생한다 -> O(1)

3. 스택 VS 큐

스택은 실행 취소, 괄호 짝 검사 등에서 사용된다.

큐는 대기열, 프로세스 관리 등에서 사용된다.