[자료구조] 큐, 스택(Queue , stack)

1. 큐 (queue)

선형 리스트의 한쪽에서 삽입, 다른쪽에서 삭제작업이 이루어지도록 구성된 자료구조입니다.

따라서 먼저 삽입된 자료가 먼저 삭제되는, FIFO(First-in, First-Out)선입선출 방식입니다.

시작과 끝을 표시하는 두 개의 포인터를 가집니다.

삭제작업에 사용되며 가장 먼저 삽입된 자료의 기억공간을 가리키는 프런트(Front) 포인터와, 삽입작업에 사용되며 가장 마지막에 삽입된 자료가 위치한 장소를 가리키는 리어(Rear) 포인터를 가집니다.

큐(Queue)의 사용 용도

서비스 순서를 기다리는 등 대기행렬의 업무처리

운영체제의 작업 스케줄링에 사용된다.

 

 

2.스택(Stack)

리스트의 한쪽 끝으로만 자료 삽입, 삭제작업이 이루어 지는 자료구조 입니다.

제일 늦게 삽입된 자료가 가정 먼저 삭제되는 후입선출(LIFO : Last-In, First-out)방식으로 자료가 처리 됩니다.

따라서 추가와 삭제가 같은 쪽 끝에서 발생하는 자료 구조입니다.

 

* TOP : Stack으로 할당된 기억공간에 제일 마지막에 삽입된 자료가 기억된 위치를 가르치는 요소이며,

        스택 포인터라고 해요.

* Bottom : Stack의 가장 밑바닥을 뜻해요.

 

-Stack의 용도-

함수 호출의 순서를 제어

인터럽트가 발생하여 복귀주소를 저장할 때

후위 표기법으로 표현되 산술식 연산시

부 프로그램 호출 시 복귀주소를 저장할 때

0 주소지정방식 명령어의 자료 저장소

재귀(Recursive) 프로그램의 순서를 제어

컴파일러를 이용해 언어 변역 시

 

-Stack의 삽입과 삭제-

*삽입(Push)

Item이 가지고 있는 값을 스택의 Top로 삽입시키고 스택 포인터(TOP)를 1을 증가 시켜요.

만약 스택 포인터가 스택의 크기보다 크다면 OverFlow를 발생시킵니다.

 

*삭제(Pop)

Top위치의 값을 Item으로 옮기고 스택포인터를 1을 감소 시킵니다.

스택 포인터값이 0이면 스택의 바닥(자료가 없음)이라 삭제가 불가능하여 Underflow를 발생시킵니다.