스택과 큐

스택(Stack)

• LIFO(Last In First Out) 구조
• 입력과 출력이 한 곳에서만 발생하고, top으로 정한 곳을 통해서만 접근 가능
• top을 통해 삽입하는 연산을 'push', 삭제하는 연산을 'pop'
• 시간복잡도
  • 접근: O(N) => top에서부터 순차적으로 접근
  • 삽입 및 삭제: O(1) => 한 곳(top)에서만 발생
• 활용
  • 후위 표기법 계산
  • 수식의 괄호 검사
  • 실행 취소(undo)
  • 웹 브라우저 방문기록(뒤로 가기)

 

큐(Queue)

• FIFO(First In First Out) 구조
• 한쪽 끝(rear)에서 삽입이, 다른 쪽 끝(front)에서 삭제가 이루어짐
• rear를 통해 삽입하는 연산을 'enqueue', front에서 삭제하는 연산을 'dequeue'
• 시간복잡도
  • 접근: O(N) => 순차적으로 접근
  • 삽입 및 삭제: O(1) => 한 곳(rear or front)에서 발생 
• 활용
  • 우선순위가 같은 작업 예약(프린터의 인쇄 대기열)
  • 은행 업무
  • 프로세스 관리
  • 너비 우선 탐색(BFS) 구현 

 

 

참고

https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시