Stack, Queue

# Stack

 - Stack은 데이터를 쌓아올리는 형태로 구성

 - 데이터를 쌓아올릴 때, 정해진 방향으로만 데이터를 쌓아올릴 수 있음

 - 데이터를 삽입하거나 삭제할 때, top으로 정해진 곳으로만 접근해 삽입, 삭제 작업을 수행할 수 있음

 - top을 통해 들어온 데이터가 바닥에서부터 쌓이는 구조이므로 나중에 들어온 자료에 먼저 접근할 수 있고, 먼저 들어온 자료들은 나중에 들어온 자료들이 전부 삭제된 다음에 접근할 수 있음  => 후입선출구조 (Last in First out: LIFO)

 

 

 ## Stack의 사용 예시

 - 컴퓨터 시스템 (시스템 스택, 실행시간 스택: 프로그램의 실행 순서를 관리)

 - 함수의 콜스택

 - 브라우저의 방문기록 (뒤로가기)

 - 실행취소

 - 후위표기법의 계산

 - 하노이 탑

 - 재귀호출 : 함수를 호출하며 매개변수, 리턴값, 리턴 이후 돌아갈 위치 등을 스택에 저장

 

 

 ## Stack의 Method

 

  - push :  데이터를 stack의 top에 삽입

push 연산
  1. stack의 크기 확인
  2. 만약 stack의 크기가 주어진 크기 이상으로 stack이 가득 차 있다면
       push 연산을 수행하지 않고 함수 종료
  3. stack의 크기가 주어진 크기 이하여서 stack이 가득 차 있지 않다면
       stack의 top의 위치를 확인
       top 위치에 데이터 삽입
       stack의 크기를 하나 증가
    

 

  - pop :  stack의 top에 있는 데이터를 삭제하고, 삭제된 데이터를 반환

pop 연산
  1. stack의 크기 확인
  2. 만약 stack의 크기가 0으로 stack이 비어있다면
       pop 연산을 수행하지 않고 함수 종료
  3. stack의 크기가 0이 아니어서 stack이 비어있지 않다면
       stack의 top 위치를 확인
       top 위치에 있는 데이터를 임시로 저장
       top 위치에서 데이터를 삭제
       stack의 크기를 하나 감소
       임시로 저장된 데이터를 반환
    

 

 - peek :  stack의 가장 위의 항목을 읽어 옴

peek 연산
  1. stack의 top 값을 확인
  2. top의 위치에 해당하는 요소를 탐색
  3. 해당 요소를 출력

 

 

 ## Stack의 Property

 

 - top :  stack의 가장 위의 항목을 가리킴

 

 

 

# Queue

 - Queue 역시 데이터를 삽입하고 삭제하는 위치와, 데이터가 쌓이는 방향이 제한되어 있음

 - Queue에 데이터가 들어올 때에는 뒤쪽으로만 들어와 앞쪽부터 쌓이게 됨

 - 데이터가 삭제될 때는 앞쪽부터 삭제되는 구조

 - 먼저 들어온 데이터가 먼저 삭제되고, 나중에 들어온 데이터가 나중에 삭제되는 선입선출구조(FIFO: First in First out)

 

 

 ## Queue의 사용 예시

 - 프린터의 인쇄 대기열 (우선순위가 같은 대기열 예약)

 - 운영체제의 작업 큐 프로세스 관리

 - 캐시 구현

 - 은행 업무

 

 

 ## Queue의 Method

 

   - enqueue :  queue의 끝부분에 데이터 삽입

enqueue 연산
  1. queue의 크기를 확인
  2. queue의 크기가 정해진 크기 이상으로 queue가 가득 찼을 때
       enqueue 연산을 실행하지 않고 함수 종료
  3. queue의 크기가 정해진 크기 미만이라 queue가 가득 차 있지 않을 때
       queue의 끝부분 위치를 확인
       끝부분 위치에 데이터를 삽입
       queue의 크기를 하나 증가
    

 

   - dequeue :  queue의 앞부분에서 데이터를 삭제하고, 해당 데이터를 반환

dequeue 연산
  1. queue의 크기를 확인
  2. queue의 크기가 0으로 queue가 비어 있을 때
       dequeue 연산을 실행하지 않고 함수 종료
  3. queue의 크기가 0 초과라 queue가 비어 있지 않을 때
       queue의 앞부분 위치를 확인
       앞부분 위치의 데이터를 임시저장
       앞부분 위치의 데이터를 삭제
       queue의 크기를 하나 감소
       임시저장된 데이터를 반환
    

 

 

 ## Queue의 Property

 

   - front :  큐에서 요소가 삭제되는 부분의 위치

   - rear :   큐에서 요소가 삽입되는 부분의 위치

 

 

 

데크

우선순위 큐 (힙트리)