2.4 스택과 큐

2.4.1 스택
빈 접시들이 가지런히 쌓여 있는 상황에서 가장 위의 접시를 가져가거나, 책상 위에 쌓여진 책 더미 위에 책을 하나 올려 놓는 것과 같은 상황을 표현할 수 있는 자료구조(접시 더미나 책 더미)= 스택.

* 스택- 데이터의 삽입과 삭제가 한쪽 끝(더미의 가장 위쪽)에서만 이루어지는 자료구조.

top- 데이터의 삽입과 삭제가 일어나는 부분.
데이터 삽입 - top이 가리키는 곳의 바로 위쪽에 저장.
데이터 삭제 - top이 가리키는 데이터가 제거.
후입선출(LIFO: Last-In First-Out) - 가장 마지막으로 삽입된 데이터가 가장 먼저 삭제되는 구조.

데이터의 삽입 연산= push, 삭제 연산=pop

2.4.2 큐
매표창구에서 표를 사서 가는 사람과 표를 사기 위해 줄의 맨 끝에서 기다리는 사람의 줄 - 큐

큐(queue)-> 리스트의 한쪽 끝에서는 데이터의 삭제, 다른 한쪽 끝에서는 데이터의 삽입.

선입선출(FIFO: First-In First-Out) - 가장 먼저 입력된 데이터가 가장 먼저 제거.

* 2개의 포인터 변수 front와 rear
front 포인터 - 삭제가 일어나는 큐의 한쪽 끝(실제 큐의 저장 데이터보다 하나 앞)
-> 큐의 저장 데이터보다 하나 앞을 가리키는 이유는 큐의 마지막 원소의 삭제로 인해 빈 큐(empty queue)가 될 경우에, front와 rear의 값이 같아지게 하여 프로그래밍 작성을 편리하게 하기 위해.

rear 포인터 - 삽입이 일어나는 큐의 다른 한쪽 끝(큐의 실제 저장 데이터)

오버플로(overflow) - 큐를 위해 할당된 저장공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상.

언더플로(underflow) - 삭제 연산을 수행할 때 큐에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상.

rear는 -1부터 시작해서 데이터가 큐에 삽입되고 n-1이 되면 더 이상 데이터가 삽입될 수 없는 상태가 됨.(큐에 n개의 항목이 가득 차 있다는 것을 의미하는 것은 아님)
이유 -> 데이터 삽입 연산만 발생하는 것이 아니라 삭제 연산도 함께 발생하는 경우에는 rear가 n-1이 되더라도, 삭제된 데이터 때문에 front가 가리키는 부분에는 저장 공간의 여유가 있을 수 있기 때문.

큐 - 운영체제가 프로세스(작업)를 관리할 때 사용되는 대표적인 자료구조. 먼저 도착한 프로세스에 CPU를 할당할 때 사용되며, 변형된 큐의 자료구조를 사용하기도 함.