210624 스택(Stack) 과 큐(Queue)

스택(Stack) : 접시를 쌓듯이 자료를 쌓아 올린 형태의 자료구조

스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능

스택(stack)

top의 위치에서만 원소를 삽입/삭제하기 때문에 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이며 마지막에 삽입한 원소가 가장 먼저 삭제된다. 그래서 후입선출(LIFO , Last In First Out) 구조라고 함

 

스택의 연산으로는 대표적으로

삽입 연산 : push

삭제 연산 : pop 

이 존재하고 조회하는 peek 등 존재함

 

스택을 응용하는 예시로 시스템 스택이 있음 

가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로 스택을 이용하여 수행순서 관리하는 것.

실행 순서를 복기하면,

1. 프로그램이 실행을 시작하면 메인 함수가 실행되고 메인 함수에 관련된 정보를 스택프레임에 저장하며 시스템 스택에 삽입함.
2. 메인 함수가 실행되면서 별도의 함수들을 실행하고 이들을 담게 된다면 호출과 복귀 정보를 스택 프레임에 담아 시스템 스택에 담게됨. 이럴 경우에는 메인 함수로 복귀하기 위한 주소 값 또한 스택 프레임에 저장. 불러들인 함수가 실행되고, 복귀할 때는 pop하여 스택 프레임에 있는 정보 활용한다.
3. 마지막에 메인 함수가 남고 메인 함수는 복귀할 주소가 없으므로 프로그램이 종료되며 시스템 스택은 공백 스택이 되는 것으로 마침.

예를 들어 덧셈을 하는 함수 add() 하나를 수행하는 메인 함수인 경우에 스택에 메인함수가 먼저 들어가고 add() 가 호출되면서 스택에 add()가 들어가고 add()가 끝나면서 스택에서 나오고 메인함수가 끝나면서 스택에서 나오고 시스템 스택은 공백이 되며 프로그램이 종료된다는 것이다.

그림에는 표현하기 힘들어 빠졌지만 top도 push,pop시 계속 이동하며 항상 맨위의 원소를 가리킨다

 

이외에도 수식의 괄호검사 등에 스택은 사용됩니다

 

 

큐(Queue) : 스택과 마찬가지로 삽입과 삭제의 위치가 제한되어 있는 유한 순서 리스트

큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조  

삽입한 순서대로 나열되어 가장 먼저 삽입한 원소는 가장 먼저 삭제되는 선입선출 (FIFO , First In First Out) 구조

(게임 할때 롤 큐 돌린다 라고 표현하는 것의 큐 개념과 동일하다 볼 수 있다 사실상 대기열)

큐(Queue)

큐의 연산으로는

삽입 : enQueue

삭제 : deQueue 

가 있음

또한 큐의 종류에는 선형과 원형이 있는데, 우선 선형으로 구현하면 어떻게 동작하는지를 보자

선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 마지막 인덱스를 가리키고, 앞에는 비어 있음에도 꽉 찼다고 인식하게 됨 why? 삭제 때마다 실제 데이터의 이동 없이 큐의 연산을 진행했기 때문이다. 

이러한 단점을 보완하기 위해 고안된 것이 원형 큐

똑같은 1차원 배열을 사용해여 구현할 수 있는 차이점이 

선형일 경우 큐가 꽉 찬 상태는 rear = n-1, 큐가 빈 것은 front == rear 인 것으로 인식

반면, 원형인 경우 enQueue 연산시 (rear+1)%배열크기 한 위치에 데이터를 삽입하고, 그 위치가 front 이면 꽉 차 있다고 판단합니다. 또한 데이터 삭제시 front 도 (front+1)% 배열크기 한 위치로 이동합니다. 

예를 들어 선형 큐의 예시의 마지막 상태에서 F를 추가로 삽입하는 것을 그림으로 그려보았다

선형 큐인 경우 이미 rear=n-1 로 꽉 차 있다고 인식하는 상태이기에 삽입이 안되지만 원형 큐인 경우 위와 같이 배열의 인덱스 0 위치에 삽입됩니다.