[알고리즘] 선형 리스트(Stack, Queue, Deque)

Stack

; LIFO(Last In First Out)구조.

- 배열을 이용한 데이터 구조이며, 삽입과 삭제가 리스트 한쪽 끝에서만 이루어지는 제한된 리스트구조

- 이용분야 ; 함수 호출 시 복귀주소 저장, 수식 계산(중위 표기법/전위 표기법/후위 표기법)

 

 

Queue

; FIFO구조, 변수 2개(tail과 head) 사용

- 리스트의 한쪽 끝에서 원소들이 추가(rear)되고, 다른 한쪽 끝에서 삭제(front)되는 선형리스트

- 

- 시스템에서, 프로세스의 순차처리와 보조기억장치를 이용한 spool처리 등에 이용

# Spool 처리 ; CPU에서 I/O장치로 보낼 때 임시로 보조기억장치에 저장하는것

 

무빙 큐

; 데이터 삭제 시 데이터를 한칸 왼쪽으로 이동시킴 -> 많은 시간적 손실 초래

 

원형 큐

; 배열의 끝 인덱스에서 배열의 시작 인덱스로 연결되는 큐

- 선형 큐의, rear이 배열의 마지막 인덱스를 가리킬 때 앞에서 발생한 배열의 빈 공간을 활용할 수 없는 문제점을 해결

 

 

Deque

; 원소의 삽입과 삭제가 리스트의 양쪽 끝에서 모두 허용되는 선형 리스트