스택과 큐, 데크
3.1 스택(Stack)
• 삽입과 삭제가 한쪽 끝에서만 발생하는 선형 리스트
• top(stack pointer) 포인터 : 자료의 삽입과 삭제가 발행하는 부분
→ top 포인터는 항상 제일 위에 있는 자료를 가리킴
• BOTTOM(밑바닥) 포인터 : 막혀있는 다른 한쪽 끝
• PUSH :자료를 삽입하는 연산, POP : 자료를 삭제하는 연산,
TOP 연산 : 현재top 포인터가 가리키는 자료의 내용을 조사하는 연산
• 자료의 삽입: top 포인터가 가리키는 위치보다 1이 증가한 위치에
→ top = top + 1
• 자료의 삭제: top 포인터가 가리키는 위치의 자료가
→ top = top - 1
• top의 초기치는 -1이다
• 입출력 정책(policy): 후입 선출 방식인 LIFO(Last In First Out) 구조
• 예 - 동전통(택시)
• 스택을 사용하는 분야: ① 산술 연산 ②서브루틴의 복귀 주소를 저장
③ 인터럽트 처리시 복귀 주소를 저장
3.1.1 자료의 삽입
• top 포인터를 1만큼 증가시킨 후 → top이 가리키는 위치(top+1)에 자료 삽입
• 삽입 알고리즘
void PUSH (stack, n, top, item)
{
/* 크기가 n인 STACK에 item을 삽입하는 알고리즘
STACK : 최대 크기가 n인 배열
n : 스택의 크기
top : 스택 포인터로 스택이 선언될 때는 초기치가 -1이다. */
if(top >= (n-1)) then /* top 포인터가 (n-1)과 같거나 크면 */
{
printf("stack overflow"); /* 여분의 기억 장소 없음 */
exit(0); /* 종료 */
}
else
{
top++; /* top 포인터 1 증가시킴 */
STACK[top] = item ; /* top 포인터가 가리키는 곳에 자료 삽입 */
}
}
• 예) 삽입순서 : C, D, E, F (단, 스택의 크기는 3이다.)
3.1.2 자료의 삭제
• 현재 top 포인터가 가리키는 위치의 자료를 삭제 → top 포인터를 1만큼 감소시킴
• 삭제 알고리즘
char POP( )
{
/* 크기가 n인 STACK에서 자료를 삭제하는 알고리즘
item : 삭제된 자료를 저장할 변수
top : 스택 포인터 */
char item;
if(top < 0) then /*top 포인터가 0보다 작으면 */
{
printf("stack underflow"); /* 스택이 비었음 */
exit(0); /* 종료 */
}
else
{
item = STACK[top]; /* top 포인터가 가리키는 곳의 자료를 삭제하여 item에 저장한다. */
top--; /* top 포인터 1 감소시킴 */
}
}
• 예) 스택에서 자료를 모두 제거(단, 스택의 크기는 3이다.)
3.1.3 스택의 TOP 내용 조사
• TOP 연산은 현재 스택에서 제일 위에 있는 자료를 알려준다.
char TOP( )
{
/* 현재 스택의 제일 위에 있는 자료를 반환하는 알고리즘
STACK : 크기가 n인 배열
top : 스택 포인터 */
if(top < 0) then /* top 포인터가 0보다 작으면 */
{
printf("stack empty"); /* 스택이 비었음 */
exit(0); /* 종료 */
}
else
return(STACK[top]); /* top 포인터가 가리키는 곳의 자료를 되돌려 준다*/
}
3.2 큐(Queue)
• 한 쪽 끝에서는 자료가 삽입되고 다른 한 쪽 끝에서는 자료가 삭제되는 선형 리스트이다.
• rear(tail) 포인터 : 삽입이 발생하는 부분
제일 마지막에 있는 자료를 가리킴
• front(head) 포인터 : 삭제가 발생하는 부분
제일 앞에 있는 자료 보다 1작은 위치를 가리킴
• 연산자 : 특별한 연산자 없음
• 삽입 : rear 포인터가 가리키는 위치보다 1증가한 위치(rear+1)에
• 삭제 : front 포인터가 가리키는 위치보다 1증가한 위치(front+1)에
• front와 rear의 초기치는 -1이다.
그림 3.4 큐의 구조
• 입출력 정책(policy): 선입 선출 방식인 FIFO(First In First Out) 구조
• 사용하는 분야 : 운영체제에서 수행할 작업들을 스케쥴링(scheduling)할 때
3.2.1 자료의 삽입
• rear 포인터를 1만큼 증가시킨 후 → rear가 가리키는 곳(rear+1)에 자료를 삽입
• 삽입 알고리즘
void insert_queue(item)
{
/* 크기가 n인 Queue에 item을 삽입하는 알고리즘
Queue : 최대 크기가 n인 배열
n : 큐의 크기
rear : 큐에 마지막으로 삽입된 원소의 위치를 가리킨다.
item : 큐에 삽입할 자료 */
if(rear==(n-1)) then
{
printf("Queue full"); /* 여분의 기억 장소 없음 */
exit(0); /* 종료 */
}
else
{
rear++; /* rear 포인터 1 증가시킴 */
Queue[rear] = item; /* rear 포인터가 가리키는 곳에 자료 삽입 */
}
}
• 예) 삽입순서 : C, D, E, F (단, 큐의 크기는 3이다.)
3.2.2 자료의 삭제
• 현재 front 포인터에 1증가시킨 위치에 있는 자료를 삭제
• 먼저 front 포인터를 1증가시킨 후 → front 포인터가 가리키는 자료를 삭제
• 삭제 알고리즘
void delete_queue( )
{
/* 크기가 n인 Queue에서 item을 삭제하는 알고리즘
Queue : 최대 크기가 n인 배열
n : 큐의 크기
front : 큐에서 자료를 삭제할 위치보다 1작은 위치를 지정한다.
item : 큐에서 자료를 삭제하여 저장할 변수 */
if(front==rear) then
{
printf("Queue empty");
exit(0); /* 종료 */
}
else
{
front++; /* front 포인터 1 증가시킴 */
item = Queue[front]; /* front 포인터가 가리키는 곳의 자료를 삭제하여 item에 저장한다. */
}
• 예) 큐에서 자료를 모두 제거
3.3 원형 큐(Circular Queue)
• 큐를 원형으로 표현한 것
• 큐의 첫 번째 원소와 마지막 원소가 서로 연결되어 있는 형태
→ Cqueue[n-1]의 다음 요소는 Cqueue[0]이다
→ 삽입이나 삭제되는 원형 큐의 위치를 찾기 위해서는
%(나머지) 연산자를 사용
• 큐에 새로운 자료를 추가할 때 rear 포인터가 큐의 끝을 가리킨다 해도 큐가 자료들로 모두 차 있는 게 아니므로
• 큐의 뒷 자료들을 큐의 앞 빈 공간으로 이동시키는 낭비를 해결하는 방법으로 고안된 큐
• rear 포인터 : 삽입이 발생하는 부분을 가리킴
제일 앞에 있는 자료보다 반 시계 방향으로 1 작은 위치를 가리킴
• front 포인터 : 삭제가 발생하는 부분을 가리킴
제일 마지막에 있는 자료를 가리킴
• 자료의 삽입 : rear 포인터가 가리키는 위치보다 1증가한 위치((rear+1) % n)에서 이루어짐
• 자료의 삭제 : front 포인터가 가리키는 위치보다 1증가한 위치
((front+1) % n)에서 이루어짐
• front와 rear의 초기치 : 0
원형 큐의 경우 하나의 공간을 비워둔다
그 이유는 그 비어있는 공간이 하나 없다면 꽉찬 큐와 비어있는 큐를 구별 할 수 없게 된다. 10개의 큐일 경우 9의 자료를 저장할 수 있다.
3.3.1 자료의 삽입
• rear 포인터를 1만큼 증가시킨 후 rear가 가리키는 위치((rear+1) % n)에 자료를 삽입하면 된다.
• 삽입 알고리즘
void insert_cqueue(item)
{
/* 크기가 n인 원형 큐에 item을 삽입하는 알고리즘
Cqueue : 최대 크기가 n인 배열
n : 원형 큐의 크기
rear : 원형 큐에 마지막으로 삽입된 원소를 가리킨다.
item : 원형 큐에 삽입할 자료 */
char item;
rear = (rear+1) % n; /* 삽입될 위치 계산 */
if(front==rear) then
{
printf("circular queue full"); /* 여분의 공간 없음 */
exit(0);
}
else
Cqueue[rear] = item; /* rear 포인터가 가리키는 곳에 자료 삽입 */
}
3.3.2 자료의 삭제
• front 포인터를 1만큼 증가시킨 후 front가 가리키는 위치
((front+1) % n)에 있는 자료를 삭제
• 삭제 알고리즘
void delete_cqueue( )
{
/* 크기가 n인 원형 큐에서 자료를 삭제하는 알고리즘
Cqueue : 최대 크기가 n인 배열
n : 원형 큐의 크기
front : 원형 큐에서 제일 앞에 있는 자료보다 반시계 방향으로 1작은 위치를 가리킨다.
item : 원형 큐에서 삭제할 자료를 저장할 변수 */
char item;
if(front==rear) then
{
printf("circular queue empty"); /* 원형 큐가 비었음 */
exit(0);
}
else
{
front = (front+1) % n; /* 삽입될 위치 계산 */
item = Cqueue[front]; /* front 포인터가 가리키는 곳의 자료를 삭제하여 item에 저장한다. */
}
}
3.4 데크(Deque)
• 양쪽 끝에서 추가와 삭제가 가능한 선형 리스트
• 스택과 큐를 하나의 선형 리스트 구조로 혼합시킨 형태
• 두 개의 스택의 bottom 부분을 서로 연결시켜 큐 모양이 되게 했음
• L-bottom 포인터 : 왼쪽 끝에서 삽입과 삭제가 일어날 위치를 가리킴
• R-bottom 포인터 : 오른쪽 끝에서 삽입과 삭제가 일어날 위치를 가리킴
그림 3.8 데크의 구조
• 데크의 입출력에 제한을 두어 다음 2개의 데크가 있음
① 입력 제한 데크 : 입력을 한쪽 끝에서만 가능하게 한 데크로 스크롤(SCROLL)이라 한다.
② 출력 제한 데크 : 출력을 한쪽 끝에서만 가능하게 한 데크로 쉘프(SHELF)라고 한다.
그림 3.9 데크의 종류
