스택(stack) & 큐(Queue) 1분 요약 정리

스택(stack)

• 삽입과 삭제가 한 쪽 끝에서만 이루어지는 데이터 구조이다.
• 가장 먼저 들어간 데이터가 가장 마지막에 나오는 후입 선출(LIFO, Last In First Out) 방식이다.
• 삽입/삭제의 복잡도는 O(1)이다.
• 활용
  • 재귀 알고리즘을 사용할 때 유용하다.
    • 재귀적으로 함수를 호출 할 때, 데이터를 스택에 넣었다가, 재귀 함수를 빠져나올 때 스택에 넣어둔 데이터를 빼는 방식을 사용할 수 있기 때문이다.
  • 웹 브라우저 방문 기록
  • 실행 취소

 

 

큐(Queue)

• 한 쪽에서는 삽입이, 다른 한 쪽에서는 삭제가 이루어진다.
• 가장 먼저 들어간 데이터가 가장 먼저 삭제되는 선입선출(FIFO, First In First Out) 방식이다.
• 삽입 연산(enQueue)이 이루어지는 곳을 리어(rear), 삭제 연산(deQueue)이 이루어지는 곳을 프론트(front)라고 한다.
• 보통 연결리스트(LinkedList)를 사용하여 구현한다.
• 원형 큐, 우선순위 큐, 데크(Deque) 등이 있다.
• 활용
  • 주로 데이터가 입력된 순서대로 처리하는 상황에 사용된다.
  • 우선순위 예약
  • 은행 업무
  • 콜센터 대기 시간
  • 프로세스 관리

 

 

참고 :

https://hee96-story.tistory.com/91

https://devuna.tistory.com/22