스택과 큐

스택

개념

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out)형식

제한적으로 접근할 수 있는 나열식 구조

사용 사례

• 재귀 알고리즘
• 웹 브라우저 방문 기록 ex)뒤로 가기

 

큐(Queue)

개념

컴퓨터의 기본적인 자료 구조 중 하나.

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식

스택과 반대되는 개념

사용 사례

• 프린터의 출력처리
• 윈도우 시스템의 메시지 처리기
• 데이터가 입력된 시간 순서대로 처리해야하는 상황에 이용

종류

선형

• 막대모양으로 된 큐
• 단점
  • 크기제한
  • 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 함.
  • 배열로 선언된 큐에 삭제와 생성이 계속 일어났을 때, 마지막 배열에 도달 후 실제로는 데이터 공간이 남았지만 오버플로우가 발생하는 문제

환형

• 선형큐의 문제점을 보완한 것
• front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내 원형으로 연결하는 방식

링크드

• 연결 리스트로 구현된 큐
• 장점
  • 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않음
  • 필요에 따라 환형으로 만들 수 있음
  • 환형으로 만들지 않아도 삽입/삭제가 제한되지 않아서 편리함