자료 구조

스택 (Stack)

• 스택(Stack)의 개념
  • Stack이란 쌓아 올린다는 것을 의미
  • 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료 구조

• 스택의 특징
  • 스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고
    Top으로 정한 곳을 통해서만 접근 가능
  • 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 Top이 가리키는 자료의 위에 쌓이게 됨
  • 스택에서 자료를 삭제할 때도 Top을 통해서만 가능
  • 스택에서 Top을 통해 삽입하는 연산을 'Push' , Top을 통한 삭제하는 연산을 'Pop'이라고 함
  • 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 됨
    • 후입선출(LIFO, Last-In-First-Out) 구조
  • 비어있는 스택에서 원소를 추출하려고 할 때 Stack Underflow라고 하며, 스택이 넘치는 경우 Stack Overflow라고 함

• 스택 활용 예시
  스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능
  • 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줌
  • 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력
  • 실행 취소 (Undo) : 가장 나중에 실행된 것부터 실행을 취소
  • 후위 표기법 계산
  • 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

큐 (Queue)

• 큐(Queue)의 개념
  • Queue는 (무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미
  • 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in first out) 방식의 자료 구조

• 큐의 특징
  • 정해진 한 곳(Top)을 통해서 삽입, 삭제가 이루어지는 스택(Stack)과는 달리
    큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어짐
  • 이때 삭제 연산만 수행되는 곳을 프론트(Front), 삽입 연산만 이루어지는 곳을 리어(Rear)로 정하여 각각의 연산작업만 수행
    • 큐의 리어에서 이루어지는 삽입 연산 : 인큐(EnQueue)
    • 큐의 프론트에서 이루어지는 삭제 연산 : 디큐(DnQueue)
  • 큐의 가장 첫 원소를 Front • 가장 끝 원소를 Rear라고 함
  • 큐는 들어올 때 Rear로 들어오지만 나올때는 Front부터 빠지는 특성
  • 첫 원소와 끝 원소로만 접근 가능
  • 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
    • 즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것

• 큐의 활용 예시
  큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
  • 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
  • 은행 업무
  • 콜센터 고객 대기시간
  • 프로세스 관리
  • 너비 우선 탐색(BFS, Breadth-First Search) 구현
  • 캐시(Cache) 구현