[자료구조]스택과 큐. (stack and queue)

1. 스택 (stack)

 : [명사] 동적이고 순차적인 자료의 목록. 
 : [영어] 무더기, 많음 다량, 굴뚝

등 여러 의미로 사용되는 스택은 자료구조에서는 무언가를 쌓는다라는 의미를 갖는 자료구조입니다. 
즉. 자료를 순서대로 쌓아서 보관하고 사용한다.

모양으로 살펴보면.. 

                                                          


다음과 같이 밑에 있는 것을 빼기위해서는 쌓인 순서대로 빼야지 사용가능 합니다.
넣는 방향성 ▼ 빼는 방향성 ▲
그래서 일반적으로 LIFO ( Last In First Out ) :  후입선출 이라고 불립니다.
( 제일 마지막에 삽입된 원소가 제일 먼저 삭제되기 때문에... ) 

스택에서 사용되는 함수로는 Push와 Pop가 있겟습니다. (Push : 자료넣기&입력, Pop : 자료빼기&삭제 )
                          변수는 Top (초기값 : -1 , 꼭데기 즉 가장 위의 변수를 가리키는 변수 ) 

< 예외처리 부분 >
단, 자료가 없을 때 Pop을 한다면 자료가 없기에 뺄수도 없죠, 이때 발생하는 Err를 "Stack Underflow"라고 합니다.  
또한 반대로 스택의 크기, 즉 배열의 크기 이상의 자료를 Push 할 때도 자료를 넣을 수 없으므로 "Stack Overflow"
Error가 발생합니다. 


2. 큐 (queue )

: 규, 대기 행렬, 줄을 서서 기다리다
: 꼬리, 끝, 후미

                                 

"Stack의 단점"
무언가를 기다리는 사람들은 자연스럽게 대기하기 위해서 줄을 스게 된다.
먼저 온 사람이 제일 앞에 있다. 하지만 stack으로 처리하게 된다면!!
LIFO 라는 자료구조 형태로 나중에 온 사람이 먼저 일을 처리하게 되는 단점이 있다.

즉, 오래 기다린 사람이 먼저 나간다. 무언가를 산다. 바로 큐 이다.
그래서 큐(queue)는 FIFO ( First In First Out ) : 선입선출 이라고 불리며, 프로세스 처리, CPU 관리 에서
많이 사용된다.

[문제점!!!]
큐의 문제점은 일반적으로 배열을
[1][2][3][4][5] 
이런 직선 형태로 보왔을 때, 
[Pop][2][3][4][5] 가장 오래기다린, 처음 들어온 [1]이라는 데이터가 Pop이 되면 다른 데이터들을 차례대로
땡겨주어야 한다.
( 소수의 자료의 경우는 상관이 없지만 많은 데이터의 경우 연산에 많은 시간이 걸린다. )

이러한 문제점을 해결하기 위해 나온게 원형 큐, 순환 큐, 환영 큐 라고 불리우는 방법이다.

 

배열을 직선으로 보는게 아니라 원형으로 보는 방법이다. 

큐에서 사용하는 변수로는 Front  : 처음이며, 자료가 나갈 경우(pop) 이 부분의 변수가 나가고 --

                                       ( -1 라면, 자료의 끝으로 감 )
                               Rear  : 꼬리라고 보시면 되고, 입력 될 경우 이 부분에 입력되고 ++

               (자료의 끝이라면 0이라고 하시면 됩니다.)

가 있습니다.