제 4 장 스택과 큐 4.1 스택(stack) 4.2 스택의 활용 4.3 큐 4.4 데큐

스택(stack) 스택의 정의와 성질 STACK이란? STACK은 선형자료구조의 한 종류로서 모든 원소들의 삽입과 삭제(후입선출:Last-In First-Out)가 리스트의 한쪽 끝에서만 이루어지는 제한된 리스트구조 이다. STACK은 특별한 성질을 갖는 자료구조로서 많은 응용분야를 갖고 있습니다. 특히 수행중의 프로그램 함수나 서브프로그램들의 복귀주소와 관련 정보들을 저장하기 위하여 사용된다.

STACK의 구조 삽입(push) 삭제(pop) A E D C B TOP BOTTOM STACK의 다른 한쪽 끝. 스텍의 TOP포인터가 가리키는 위치의 데이터는 가장 최근에 삽입된 데이터를 의미하며, 가장 먼저 STACK으로부터 삭제되어 출력되는 데이터의 위치를 말하는 것입니다. A E D C B TOP STACK의 다른 한쪽 끝. BOTTOM

표현과 연산 순차리스트의 STACK :하나의 기억장소에 하나의 스택을 사용함. :스택의 크기를 벗어나는 오버플로우(Overflow)와 삭제 시에 빈 스택으로 인한 언더플로우(Underflow)발생.

스택의 연산 TOP 5 4 3 2 1 위치 (1)초기상태 TOP A 5 4 3 2 1 위치 (2)A 삽입

스택의 연산 TOP A B 5 4 3 2 1 위치 (3)B 삽입 TOP A C B 5 4 3 2 1 위치 (4)C 삽입

스택의 연산 TOP A B 5 4 3 2 1 위치 (5)C 삭제 TOP A D B 5 4 3 2 1 위치 (6)D 삽입

스택의 연산 TOP A D B 5 4 3 2 1 위치 E (7)E 삽입 TOP A D B 5 4 3 2 1 위치 (8)E 삭제

STACK의 알고리즘. (크기가 n인 배열로 표현.) 배열로 구현된 스택 STACK의 알고리즘. (크기가 n인 배열로 표현.) [-1] [0] [1] [2] . . . [n-2] [n-1] A B C bottom STACK의 시작위치 TOP STACK의 끝 위치

스택의 삽입 알고리즘 void push(item, stack, n, top) int item, stack[],n, top; { if(top≥n) then printf(" Stack full "); /* 스택의 오버플로우 */ else{ top = top + 1; /* 스택의 top 증가 */ stack[top] = item; /* 스택의 top에 데이터 삽입 */ }

스택의 삭제 알고리즘 void pop(item, stack, top) int item, stack[], top; { if(top == -1) then printf(" Stack empty "); /*스택 언더플로우*/ else{ item = stack[top]; /* 데이터 삭제 */ top = top - 1; /* 스택의 top 감소 */ }

다중 STACK 2개의 STACK을 이용한 구조 :하나의 기억장소에 2개의 스택을 표현한 구조. 사용가능공간 스택1 스택2 bottom1 TOP1 bottom2 TOP2

다중 STACK n개의 STACK을 이용한 구조 :하나의 기억장소에 n개의 스택을 구현. 스택1 스택2 스택3 스택n . . . B[1] B[2] B[3] B[4] B[n] T[n] T[1] T[2] T[3] T[n-1]

다중 스택의 삽입 알고리즘 /* i 번째 스택에서의 삽입 */ void multi_stackpush(i, item) int i, item; { if(t[i] == b[i+1]) printf("i-th Stack full"); else{ t[i]++; stack[t[i]] = item; }

다중 스택의 삭제 알고리즘 /* i 번째 스택에서의 삭제 */ void multi_stackpop(i, item) int i, item; { if(t[i] == b[i]) printf("i-th Stack Empty"); else{ item = stack[t[i]]; t[i]--; }

연결리스트의 STACK 자료의 이동 없이 오버플로우를 쉽게 해결. 삽입(push)과 삭제(pop)연산이 연결 방향에 따라 쉽게 이루어진다. 리스트의 헤드(head) 포인터를 스택의 top포인터로 정의.

연결리스트의 STACK data link top . . .

연결리스트 스택의 삽입 삽입 알고리즘 Top(head) data link temp Void stack_push(i, item) /* i 번째 스텍에 데이터 삽입 */ int i, item; { struct stack_node *temp; Temp = getNode(); /*새 노드 생성 */ Temp->data = item; Top[i] = temp; Temp->link = top[I]; }

연결리스트 스택의 삭제 int stack_pop(int i, int item) struct stack_node *temp; { if(top[i] == NULL) then printf("Stack Empty"); else{ temp = top[i]; item = top[i]->data; top[i] = top[i]->link; Free(temp); } return item;

스택의 활용 1 프로그램의 실행 중 필요한 정보의 저장 함수들 사이의 호출 관계와 복귀 주소 관계[그림4.7] void main() { ⋮ fun_A() a: return; } int fun_A() fun_B() b: float fun_B() fun_C() c: void fun_C() 호출 복귀 함수의 호출과 복귀

스택의 활용 1 1 2 3 4 위치 5 top (1) 초기상태 (2) fun_C() 실행 a s b c top (1) 초기상태 (2) fun_C() 실행 a s b c (3) fun_B() 실행 (4) fun_A() 실행 (5) main() 실행

스택의 활용 2 스택을 활용한 수식의 연산과 처리 수식의 표기법 중위표기법(infix notation) 전위표기법(prefix notation) 후위표기법(postfix notation)

중위 표기법 피연산자와 피연산자 사이에 연산자 표현 가장 일반적인 표기법 표현 예 A / B + C – D * E + A * C

전위 표기법 피연산자들 앞에 연산자 표현 중위 표기식의 전위 표기식 변환 중위 표기식을 연산 순서에 따라 괄호를 이용하여 묶어준다. ( ( ( ( A / B ) + C ) - ( D * E ) ) + ( A * C ) ) 연산 순서에 따라 해당 연산자를 괄호 앞으로 이동하여 표기한다. + ( - ( + ( / ( A B ) C ) * ( D E ) ) * ( A C ) ) 괄호를 제거하여 식을 정리한다. + - + / A B C * D E * A C

후위 표기법 피연산자들 뒤에 연산자 표현 중위 표기식의 후위 표기식 변환 중위 표기식을 연산 순서에 따라 괄호를 이용하여 묶어준다. ( ( ( ( A / B ) + C ) - ( D * E ) ) + ( A * C ) ) 연산 순서에 따라 해당 연산자를 괄호 앞으로 이동하여 표기한다. ( ( ( ( A B ) / C ) + ( D E ) * ) - ( A C ) * ) + 괄호를 제거하여 식을 정리한다. A B / C + D E * - A C * +

스택을 이용한 수식의 연산 중위 표기식으로 표현된 수식의 연산 후위 표기식으로 표현된 수식의 연산 두개의 스택을 활용 알고리즘 후위 표기식으로 표현된 수식의 연산 한 개의 스택을 활용한 알고리즘 중위 표기식의 후위 표기식 변환 알고리즘 괄호가 없는 중위 표기식 괄호를 포함한 중위 표기식

중위 표기식으로 표현된 수식의 연산 A / top 피연산자 스택 연산자 스택 B C - D * E + @ 

중위 표기식으로 표현된 수식의 연산 top 피연산자 스택 연산자 스택 / B C - D * A E + @ 

중위 표기식으로 표현된 수식의 연산 R1 + top 피연산자 스택 연산자 스택 / B C - D * A E @  R1=A/B

중위 표기식으로 표현된 수식의 연산 top 피연산자 스택 연산자 스택 / B C - D * A E + @  R1

중위 표기식으로 표현된 수식의 연산 / B C D * A E + @  R2=R1+C - 피연산자 스택 연산자 스택 top

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R2=R1+C 피연산자 스택 연산자 스택 top

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R2=R1+C 피연산자 스택 연산자 스택 E - D top E top R2 - D *

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R3=D * E 피연산자 스택 연산자 스택 top

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R4=R2-R3 피연산자 스택 연산자 스택 top

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R4=R2-R3 피연산자 스택 연산자 스택 top

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  * R4=R2-R3 C 피연산자 스택 연산자 스택 top C top R4 + A *

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R5=A * C 피연산자 스택 연산자 스택 top

중위 표기식으로 표현된 수식의 연산 / B C - D * A E + @  R6=R4+R5 피연산자 스택 연산자 스택 top

후위 표기식으로 표현된 수식의 연산 A top 스택 B / + D E * - C ＼0 

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  X = A Y = B top

후위 표기식으로 표현된 수식의 연산 top 스택 B / + D E * A - C ＼0  A/B

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  C top A/B

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  X = A / B Y = C top

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top (A/B)+C

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top D (A/B)+C

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top E D (A/B)+C

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  X = D Y = E top (A/B)+C

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top D*E (A/B)+C

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  X = (A/B)+C Y = D*E top

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top ((A/B)+C)-(D*E)

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top A ((A/B)+C)-(D*E)

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top C A ((A/B)+C)-(D*E)

후위 표기식으로 표현된 수식의 연산 B / + D E * A - C  X = A Y = C ((A/B)+C)-(D*E) 스택 ＼0  X = A Y = C top ((A/B)+C)-(D*E)

후위 표기식으로 표현된 수식의 연산 스택 B / + D E * A - C ＼0  top A*C ((A/B)+C)-(D*E)

후위 표기식으로 표현된 수식의 연산 B / + D E * A - C  X =((A/B)+C)-(D*E) Y = A*C 스택 ＼0  X =((A/B)+C)-(D*E) Y = A*C top

후위 표기식으로 표현된 수식의 연산 B / + D E * A - C  (((A/B)+C)-(D*E))+(A*C) 스택 top ＼0  top (((A/B)+C)-(D*E))+(A*C)

후위 표기식으로 표현된 수식의 연산 B / + D E * A - C  결과 = (((A/B)+C)-(D*E))+(A*C) 스택 B / + D E * A - C ＼0  top 결과 = (((A/B)+C)-(D*E))+(A*C)

중위, 후위 표기식 변환 알고리즘 중위 표기식 : A – B * C + D 단계 토큰 스택변화 후위 표기식 출력결과 1 2 3 4 5 6 7 8 none A - B * C + D done @ @- @-* @+ AB ABC ABC*- ABC*-D ABC*-D+ @ : 스택의 bottom을 의미 괄호가 없는 중위 표기식

중위, 후위 표기식 변환 알고리즘 중위 표기식 : A * (B + C) / D 단계 토큰 스택변화 후위 표기식 출력결과 1 2 3 4 5 6 7 8 9 10 none A * ( B + C ) / D Done @ @* @*( @*(+ @/ AB ABC ABC+ ABC+* ABC+*D ABC+*D/ @ : 스택의 bottom을 의미 괄호를 포함하는 중위 표기식

큐의 정의와 성질 큐(queue)는 리스트의 한쪽 끝에서 원소들이 삽입되고, 다른 한쪽 끝에서 삭제되는 선형리스트(linear list)이다. 큐는 데이터의 삽입과 삭제가 서로 다른 곳에서 이루어지기 때문에 그 위치를 가리키는 front와 rear라는 포인터를 이용한다. 큐는 삽입되는 순서에 따라 출력되는 데이터의 순서가 결정된다. 즉, 가장 먼저 입력된 데이터가 가장 먼저 출력된다.(선입선출:first-in first-out)

큐의 삽입, 삭제 큐에 새로운 원소가 삽입될 때는 rear 포인터가 가리키는 한쪽 끝에서만 삽입이 일어나 rear포인터가 증가하고, 큐의 특정 원소가 삭제될 때는 front 포인터에서 삭제가 수행되어 front 포인터가 증가한다. 따라서 원소들의 삽입과 삭제시에 포인터의 값이 증가한게 된다.

큐의 동작구조 front rear A B C D 삭제 삽입

큐의 삽입,삭제 과정 front rear -1 0 1 2 3 4 (a)큐가 비어있는 상태(front = rear) front(Q) = -1 (초기조건:front = -1) rear(Q) = -1 (초기조건:front = -1) front(Q) == rear(Q)

큐의 삽입,삭제 과정 A (b)큐의 rear로 A삽입 front(Q) = -1 rear(Q) = 0 Q[rear] = ‘A’ -1 0 1 2 3 4 (b)큐의 rear로 A삽입 front(Q) = -1 rear(Q) = 0 Q[rear] = ‘A’

큐의 삽입,삭제 과정 front rear A B 삽입 -1 0 1 2 3 4 (c)큐의 rear로 B삽입 front(Q) = -1 rear(Q) = 1 Q[rear] = ‘B’

큐의 삽입,삭제 과정 front rear A B 삭제 -1 0 1 2 3 4 (d)큐의 front에서 A 삭제 front(Q) = 0 rear(Q) = 1 data = Q[front]

큐의 삽입,삭제 과정 front rear B C 삽입 -1 0 1 2 3 4 (e)큐의 rear에서 C 삽입 front(Q) = 0 rear(Q) = 2 Q[rear] = ‘C’

큐의 삽입,삭제 과정 front rear B C D 삽입 -1 0 1 2 3 4 (f)큐의 rear에서 D 삽입 front(Q) = 0 rear(Q) = 3 Q[rear] = ‘D’

큐의 삽입,삭제 과정 front rear B C D 삭제 -1 0 1 2 3 4 (g)큐의 front에서 B 삭제 front(Q) = 1 rear(Q) = 3 data = Q[front]

큐의 삽입,삭제 과정 front rear C D 삭제 -1 0 1 2 3 4 (h)큐의 front에서 C 삭제 front(Q) = 2 rear(Q) = 3 data = Q[front]

큐의 삽입 알고리즘 A front rear -1 0 1 2 3 4 큐의 rear로 A삽입 front(Q) = -1 rear(Q) = 0 Q[rear] = ‘A’ 삽입 void insert_Q(queue[], item, n, front, rear) int front, rear, n;/*배열 큐(queue[])의 front, rear 포인터와 큐의크기 n*/ char queue[], item; /* 큐의 rear에 삽입될 데이터 변수 item */ { int front, rear; /* 선언 */ if(rear == n-1) printf(“ Queue full “); /* 큐의 overflow */ else{ rear++; /* rear 포인터 증가 */ queue[rear] = item; /* 큐의 증가된 rear 포인터에 데이터 저장 */ } } 이한출판사

큐의 삭제 알고리즘 A B front rear -1 0 1 2 3 4 큐의 front에서 A 삭제 front(Q) = 0 rear(Q) = 1 data = Q[front] 삭제 Char delete_Q(queue[], item) char queue[], item; /* 큐의 rear에 삽입될 데이터 변수 item */ { int front, rear; /*배열 큐(queue[])의 front, rear 포인터 선언 */ if(front == rear) printf(“ Queue Emply “); /* 큐의 underflow */ else{ front++; /* front 포인터 증가 */ item = queue[front];/*큐의 증가된 front 포인터에 데이터 저장*/ return item; } } 이한출판사

큐의 오버플로우 해결방법 큐의 오버플로우 상태 B C D E F 큐의 크기: 10 front = 4 rear = 9 -1 0 1 2 3 4 5 6 7 8 9 B C D E F 큐의 크기: 10 front = 4 rear = 9 front rear 큐의 오버플로우 해결(왼쪽 이동) -1 0 1 2 3 4 5 6 7 8 9 B C D E F 큐의 크기: 10 front = -1 rear = 4 front rear 문제점:사용 가능한 기억공간을 만들기 위해 많은 원소들을이동시켜야 하기때문에 많은 시간적 손실을 초래한다.

큐의 단점과 해결책 큐의 단점 *rear가 배열의 마지막 원소를 가리키는 경우(r == n-1) 반드시 n개의 항목이 차 있는 것을 의미하지 않음. *f == -1, r == n-1이면 오버플로우 *front가 -1보다 크면 데이터 항목이 삭제된 것이므로 큐에 빈 공간이 남아 있음. *계속 항목을 삭제하면 rear pointer와 front pointer가 만나게 되고 공백 큐가 되는데도 오버플로우 발생. 해결책 *큐 전체를 왼쪽으로 옮기고 front를 -1로 하고 rear값을 조정. *원형 큐를 사용.

원형 큐 큐의 이동방식이 갖는 단점을 보완하기 위한 방법 큐의 크기가 n인 1차원 배열의 처음과 끝을 연결해서 원형(Circular)으로 구성 오버플로우가 발생 했을 때 큐의 구조가 원형으로 구성되어 있으므로 데이터의 삽입 시에 rear 포인터 값을 증가시켜 계속 새로운 가용공간을 확보할 수 있어서 원소들을 이동시킬 필요가 없게 된다. 삽입과 삭제시의 배열의 위치는 나머지연산(% 연산)을 이용하여 계산한다.

원형 큐의 개념적 구조 . . . . . . (a)front = 0, rear = 3 [3] [n-2] [3] [n-2] a3 a9 a2 [2] [2] [n-1] [n-1] a11 a10 a1 [1] [0] [1] [0] (a)front = 0, rear = 3 (a)front = n-2, rear = 1

원형 큐의 삽입,삭제 과정 front = 0, rear = 0 (a)원형 큐의 초기상태 front rear 0 1 2 3 4 5 6 front = 0, rear = 0 (a)원형 큐의 초기상태

원형 큐의 삽입,삭제 과정 front rear A 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 0, rear = 1 (b)원형 큐의 A 삽입

원형 큐의 삽입,삭제 과정 front rear A B 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 0, rear = 2 (c)원형 큐의 B 삽입

원형 큐의 삽입,삭제 과정 front rear A B C 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 0, rear = 3 (d)원형 큐의 C 삽입

원형 큐의 삽입,삭제 과정 front rear A B C D 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 0, rear = 4 (e)원형 큐의 D 삽입

원형 큐의 삽입,삭제 과정 front rear A B C D 0 1 2 3 4 5 6 front = (front + 1) % 7 front = 1, rear = 4 (f)원형 큐의 A 삭제

원형 큐의 삽입,삭제 과정 front rear B C D E 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 1, rear = 5 (g)원형 큐의 E 삽입

원형 큐의 삽입,삭제 과정 front rear B C D E 0 1 2 3 4 5 6 front = (front + 1) % 7 front = 2, rear = 5 (h)원형 큐의 B 삭제

원형 큐의 삽입,삭제 과정 front rear C D E F 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 2, rear = 6 (i)원형 큐의 F 삽입

원형 큐의 삽입,삭제 과정 front rear C D E F 0 1 2 3 4 5 6 front = (front + 1) % 7 front = 3, rear = 6 (j)원형 큐의 C 삭제

원형 큐의 삽입,삭제 과정 rear front G D E F 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 3, rear = 0 (k)원형 큐의 G 삽입

원형 큐의 삽입,삭제 과정 rear front G H D E F 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 3, rear = 1 (l)원형 큐의 H 삽입

원형 큐의 삽입 알고리즘 A rear = (rear + 1) % 7 front = 0, rear = 1 원형 큐의 A 삽입 void insert_cir_Q(item, gueue[], n, front, rear) char item, queue[]; int front, rear; { if(tag == 1) printf(“ Queue_Full “); else{ rear = (rear + 1) % n; if(rear == front) tag = 1; else queue[rear] = item; } } front rear A 0 1 2 3 4 5 6 rear = (rear + 1) % 7 front = 0, rear = 1 원형 큐의 A 삽입

원형 큐의 삭제 알고리즘 char delete_cir_Q(queue[], n, front, rear) { char item; if(rear == front && tag == 0) printf(“Queue_Empty”); else{ front = (front + 1) % n; if(rear == front) tag = 0; else item = queue[front]; } return item; } front rear A B C D 0 1 2 3 4 5 6 front = (front + 1) % 7 front = 1, rear = 4 원형 큐의 A 삭제

연결 리스트의 큐 오버플로우의 해결을 위해 기억공간의 확보를 위한 이동이나 원형 큐의 꽉 찬 상태에 관계없이 기억 공간만 존재한다면 큐의 오버플로우를 쉽게 해결할 수 있다.

연결리스트 큐의 표현 단순 연결 리스트의 시작 위치를 가리키는 헤드 포인터를 큐의 front 포인터로 정의 마지막 노드를 rear 포인터로 하여금 가리키게 하여 삽입과 삭제가 양 쪽 끝에서 일어나도록 함 data link … front rear

큐 노드의 정의 큐 노드의 정의 struct queue_node{ int data; struct stack_node *link }; 큐의 포인터 정의 front[i]: n개의 큐에서 i 번째 큐의 front포인터, 1≤i≤ rear[i]: n개의 큐에서 i번째 큐의 rear포인터, 1≤i≤n 초기조건 front[i] = NULL, 1≤i≤n : 큐가 존재하지 않음 경계조건 front[i] = NULL : i번째 큐가 비어 있음

큐의 삽입과 삭제 과정 (연결리스트로 구현) A A B A B C B C B C D C D D rear front A삽입 큐의 삽입과 삭제 과정 (연결리스트로 구현) rear front A A삽입 rear A B B삽입 rear A B C C삽입 rear B C A삭제 rear D삽입 B C D C D rear B삭제 D rear C삭제

연결 리스트 큐의 삽입 알고리즘 void insert_linkQ(i, item) /* i번째 큐에 item의 데이터 삽입 */ int i, item; { struct queue_node *temp; temp = getNode(); /* 새로운 노드 생성 */ temp->data = item; /* 데이터를 생성 노드의 데이터 필드에 저장 */ temp->link = NULL; /* 삽입되는 노드의 링크 필드에 rear이 가리키는 노드의 주소 저장 */ if(front[i] == NULL) /* 큐가 비어 있는 경우 처리 */ front[i] = temp; rear[i] = temp; else{ /* 연결된 노드를 갖고 있는 경우 처리 */ rear[i]->link = temp; /* 현재 rear 포인터가 가리키고 있는 노드의 링크 필드에 삽입 노드의 주소 저장 */ rear[i] = temp; /* rear 포인터를 삽입 노드의 주소로 변경 */ }

연결 리스트 큐의 삭제 알고리즘 int delete_linkQ(i, item) int i, item; { struct stack_node *temp if(front[i] == NULL) then printf(“Queue empty”); else{ temp = front[i]; /* front의 삭제 노드를 temp 포인터에 저장 */ item = temp->data; /* 삭제 노드의 데이터 필드 값을 저장 */ front[i] = temp->link; /* front 포인터를 삭제되는 다음 노드를 가리키게 함 */ free(temp); /* 가용 공간으로 삭제 노드 반환 */ } return item; /* 삭제 노드의 데이터 반환 */

데크(Deque)의 기본개념 데크는 Double ended Queue의 약자로서 원소의 삽입과 삭제가 리스트의 양쪽 끝에서 모두 허용되는 선형 리스트이며, 이는 스택과 큐를 혼합한 형태이며 2개 스택의 bottom부분이 서로 연결된 형태이다. 데크를 표현하는 방법에는 1차원 배열 형태인 스택을 이용하는 방법과 단순 연결리스트나 이중 연결 리스트를 사용하여 표현하는 방법이 있다. 하지만 연결 리스트를 이용한 구현은 연결 구조를 위한 포인터 기억 공간을 더 요구하게 된다. 데크는 리스트의 양쪽 끝에서 삽입과 삭제가 일어남으로 항상 두 개의 포인터(end1, end2)를 필요로 한다.

데크(Deque)의 기본개념 스택을 이용하는 경우 *두개의 스택을 연결. *스택들이 뚜렷한 경계가 있거나, 스택의 마지막 원소의 위치를 저장해 놓을 수 있다면 스택들이 같은 기억장소 공유가능. *기억장소 오버플로우 발생 *양쪽 끝에서 삽입, 삭제가 가능하기 때문에 두개의 포인터(left, right또는 top, bottom)필요. 연결 리스트를 이용하는 경우 *한 데이터 항목을 첨가해야 할 때 사용 가능한 기억 공간을 확보해 주는 함수 이용. *원소가 삭제될 때에는 기억장소 관리 함수를 이용하여 반환.

데크의 구조 표현 end1 end2 삽입 삭제 A B C D 삭제 삽입

데크에서 원소의 삽입, 삭제 동작 B A end1 end2 end1 end2 null null 3 4 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 B A (a) 데크의 빈 상태 (b) end1에서 B 삽입 end2에서 A 삽입

데크에서 원소의 삽입, 삭제 동작 C C B B A A D end1 end2 end1 end2 2 4 2 5 1 2 3 4 5 6 1 2 3 4 5 6 C C B B A A D (c) end1에서 C 삽입 (d) end2에서 D 삽입

데크에서 원소의 삽입, 삭제 동작 E B B A A D end1 end2 end1 end2 3 5 2 4 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 E B B A A D (e) end2에서 C 삭제 (f) end1에서 E 삽입 end2에서 D 삭제

(i) end1으로 삽입을 위해 한자리 씩 이동 후 H 삽입 데크에서 원소의 삽입, 삭제 동작 end1 end2 end1 end2 end1 end2 2 5 1 4 1 5 G 이동 H 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 E E G B B E A A B F A (g) end2에서 F 삽입 (h) end1에서 G 삽입 end2에서 F 삭제 (i) end1으로 삽입을 위해 한자리 씩 이동 후 H 삽입

데크의 종류와 동작 데크의 양쪽 끝에서 원소들의 삽입과 삭제에 제한을 두어 리스트의 어느 한쪽 끝에서 삽입과 삭제가 가능하도록 할 수 있다. 이때 새로운 원소의 삽입이 리스트의 한쪽 끝에서만 가능하도록 제한한 것을 ‘입력 제한 데크’(input restricted deque) 또는 스크롤(scroll)이라 하며, 특정 원소의 삭제를 리스트의 한쪽 끝에서만 가능하도록 제한한 것을 출력 제한 데크(output restricted deque)혹은 셀프(shelf)라고 한다.

입력 제한 데크의 구조 새로운 원소의 삽입이 리스트의 한쪽 끝에서만 가능하도록 제한 스크롤(scroll) A B C D end1 end2 삭제 A B C D 삭제 삽입

출력 제한 데크의 구조 특정 원소의 삭제를 리스트의 한쪽 끝에서만 가능하도록 제한 셀프(shelf) A B C D end1 삽입 삽입