스택과 큐

스택

스택은 데이터를 임시 저장할 때 사용하는 자료구조. 데이터의 입력과 출력 순서는 후입선출 방식입니다.

스택에 데이터를 넣는 작업은 push, 스택에서 데이터를 꺼내는 작업은 pop이라고 합니다. 데이터를 차곡차곡 채우고, 꺼내는 작업은 맨위부터 수행합니다. pop되는 윗부분을 top이라고하고, 아랫부분(마지막)을 bottom이라고 합니다.

• stk: 스택배열
  푸시한 데이터를 저장하는 스택 본체인 list형 배열. 인덱스가 0인 원소는 스택의 바닥(bottom)이라 합니다.
• capacity: 스택의 크기
  스택의 최대 크기를 나타내는 int형 정수. 이 값은 배열 stk의 원소 수인 len과 일치합니다.
• ptr: 스택 포인터
  스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값. 스택이 비어있으면 ptr은 0이고, 가득 차 있으면 capacity와 같은 값이 됩니다.
  

  

큐

큐도 스택과 비슷합니다. 그러나 후입선출인 스택과 다르게 선입선출 구조를 가집니다.

큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업을 dequeue, 데이터를 꺼내는 쪽을 front, 데이터를 넣는 쪽을 rear라고 합니다.

• 우선순위 큐: 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 때 우선순위가 가장 높은 데이터를 꺼내는 방식입니다. 파이썬에서는 heapq 모듈에서 제공합니다.