[자료구조] 큐와 스택

큐

큐는 주기억장치에서 연속적인 공간을 배정하여 데이터를 Rear라는 포인터가 가르치는 방향에서 데이터가 삽입되며

Front라는 포인터가 가리키는 방향에서 삭제되도록 하는 알고리즘으로 구성되어 있는 순서 리스트와 같은 자료 구조이다.

그리고 큐는 운쳥제제의 작업 스케줄링 등에 사용이 된다.

큐 알고리즘 FIFO Frist-in Frist-out 선입선출이며 FCFS 라고도 한다. 아무것도 없는 큐에서 데이터를 삭제할 경우 언더플로우 에러가

발생한다. 

이미 꽉 찬 큐에 데이터를 삽입하려는 경우 오버플로우 에러가 발생한다.

스택

스택은 주기억장치에서 연속적인 공간을 배정하여 데이터를 1, 2, 3과 같이 차례대로 삽입 연산을 실행할 때 TOP  포인터를 이용하여 

순서 리스트의 한 쪽 끝에서만 실행하는 알고리즘으로 구성된 자료 구조이다.

자료의 삽입 : TOP=TOP + 1

자료의 삭제 : TOP=TOP - 1

스택의 크기가 S일 때 TOP>S이면 오버플로우가 발생한다.

FILO 선입후출, LIFO 후입선출의 구조를 가진다

// 삽입 알고리즘
TOP = TOP + 1
 
if(Top > S) Then
            Stack_overflow
else
            Stack(top) <- data
 
// 삭제 알고리즘
if(Top = =0)then
    Stack_underflow
else
    Stack(top)< - data
    Top= Top-1

스택은 인터럽트 처리 , 수식의 계싼 , 서브루틴의 복귀번지 저장에 쓰인다.

아무것도 없는 스택에서 Pop()으로 데이터를 꺼내려고 하면 언더플로우 에러가 발생한다.

반대로 이미 꽉 찬 스택에 PUSH()로 데이터를 삽입하려는 경우 오버플로우 에러가 발생한다.