[TIL]CS: 스택,큐

스택(Stack)

스택(Stack) 자료구조는 벽돌 쌓듯이 차곡차곡 쌓아 올린 형태이고

내부의 데이터는 최근(마지막)에 들어온 자료인 ‘top’을 통해 접근할 수 있습니다. 즉 시간 순서에 따라 데이터가 쌓이고

데이터를 삽입할 때는, (top) 위에 쌓게 됩니다.(push 연산)

또한 스택에서 데이터를 삭제할때는 가장 마지막에 삽입 된 데이터가 가장 먼저 삭제됩니다.(pop 연산)

이러한 스택의 구조를 후입 선출 자료구조 라고 합니다.

+스택의 활용 예시를 하나 들어주세요!

• 웹 브라우저 방문기록 (뒤로 가기)

  • 가장 마지막에 열린 페이지부터 다시 보여준다.

• 실행 취소 (undo)

  • 가장 마지막에 실행된 것부터 실행을 취소한다.

• 역순 문자열 만들기

  • 가장 마지막에 입력된 문자부터 출력한다.

• 후위 표기법 계산

  • 연산자가 피연산자들의 뒤에 위치.

• 수식의 괄호 검사

  • 연산자 우선순위 표현을 위한 괄호 검사

    큐(Queue)

  

  큐의 자료구조는 가장 먼저 삽입된 데이터가 먼저 삭제 된다는 특징을 가진 선입선출방식입니다.

  큐는 삽입과 삭제가 다른 방향에서 이루어지는데 리어(rear)에서 이루어지는 삽입 연산을 인큐(enQueue) 라고 하며 프론트(front)에서 이루어지는 삭제 연산을 디큐(dnQueue) 라고 합니다.

  +큐의 활용 예시를 하나 들어주세요!

  • 큐는 주로, 데이터가 입력된 순서에 따라 처리되어야 할 때 사용된다.
    • 일상생활에서, 줄을 서서 기다려야하는 모든 행동
      • 은행 업무
      • 콜센터 고객 대기시간
      • 놀이동산
    • 프로세스 관리
    • 너비 우선 탐색(BFS, Breadth-First Search) 구현
    • 캐시(Cache) 구현