3 장 stack and queue

3.1 스 택 정의 선형리스트 구조의 특별한 형태로 데이타의 삽입과 삭제가 한쪽 끝(top)에서만 일어나는 구조 push down 리스트 또는 LIFO(Last In First Out) 리스트 데이타의 삽입과 삭제가 한쪽 끝에서만 일어나므로 가장 나중에 삽입한 데이타가 제일 먼저 삭제 사용분야 서브루틴의 복귀주소 (return address)를 저장할 경우 수식 계산 a2 top 입력 (삽입) a1 출력 (삭제) a0 스택의 동작구조

스택의 표현과 연산 프로그램 실행 시작시 ’top’이 초기치 ’-1’을 가리킴 삽입할 자료가 발생하면 위치를 하나씩 증가 삭제시 위치가 하나씩 감소 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 LIFO(Last-In First-Out) 구조 스택의 연산 Create : 스택을 생성한다. Push : 스택에 ’top’이 가리키는 위치에 자료를 삽입한다. IsFull : top >= n-1일 경우 스택에 더 이상의 공간이 없음을 나타낸다. ( n은 스택의 크기) Pop : 스택의 ’top’이 가리키는 위치에 있는 자료를 삭제. IsEmpty : top < 0일 경우에 스택에 삭제할 자료가 없음을 나타낸다.

스택의 표현과 연산 스택 표현 D 4 C B A 1차원 배열 표현 - 스택이 포함할 수 있는 최대 크기를 알 수 있을 때 연결 리스트로 표현 - 스택의 최대 크기를 알 수 없을 때 top D 4 C B top D C B A A (b) (a)를 연결리스트로 표현 (a) 배열표현

(1) 스택 생성(Create) item 배열: 스택의 항목 top: 현 스택의 top 위치 #define STACK_SIZE 50 typedef struct { int value; } element; element stack[STACK_SIZE]; int top = -1; /* 초기 값 */

스택 생성(Create)

(2) 자료 삽입(PUSH) void push(int top, element item) { if(top >= (STACK_SIZE - 1)) { printf("stack is full\n"); return; } stack[++top] = item;

(3) 자료 삭제(POP) element pop(int top) { if(top == -1) { printf("stack is empty\n"); return; } else return stack[(top)--];

스택 오버플로우 처리 (1/2) 하나의 기억장소에 2개 스택을 보관 운영하는 방법 top : 입출력이 발생되는 스택의 끝 bottom : 스택의 시작 위치 STACK1 STACK2 좌우로 이동할 수 있음 STACK1 가용 공간 STACK2 bottom1 top1 top2 bottom2

스택 오버플로우 처리 (2/2) ··· 하나의 기억장소에 n개의 스택을 보관 운영하는 방법 topi = bottomi 이면 i 번째 스택의 empty topi = bottomi+1 이면 i 번째 스택의 포화 상태 topi > bottomi+1 이면 i번째 스택의 오버플로 기억 장소의 빈 공간을 찾아 기억 공간을 재압축(repacking) STACK1 STACK2 STACK3 ··· STACK4 bottom1 top1 top2 top3 topn-1 topn bottom2 bottom3 bottom4 bottomn 초기상태 bottom1 = top1 bottom2 = top2  bottomn = topn

3.2 큐(Queue) 정의 한쪽 끝에서 항목들이 삭제되고, 다른 한쪽 끝에서 항목들이 삽입되는 선형 리스트 FIFO(First-In First-Out) : 가장 먼저 삽입된 항목이 가장 먼저 삭제 응용 작업 스케줄링, 대기 행렬 이론(queueing theory) 삭제 삽입 -1 1 2 3 A B C D 프런트(front) 리어(rear)

큐의 배열 표현과 연산 (1/2) 큐의 표현 1차원 배열 : Queue[T] Queue = [Q0, Q1, Q2,...QT-1] front(Q) = Q0 rear (Q) = QT-1 front : 실제 큐의 front보다 하나 앞을 가리킴 rear : 실제 큐의 rear 큐가 빈 상태 : front = rear 큐의 초기조건 : front = rear = -1

큐의 배열 표현과 연산 (2/2) 큐의 삽입과 삭제 ··· A B C D ··· -1 1 2 3 front front rear 1 2 3 ··· A B C D ··· front front rear rear (삭제) (삽입)

(1) 큐 생성 #define QUEUE_SIZE 50 typedef struct { int value; } element; element queue[QUEUE_SIZE]; int rear = -1; int front = -1;

(2) 자료 삽입(Add) void add(int rear, element item) { if(rear == (QUEUE_SIZE - 1)) { printf("queue is full!\n"); return; } queue[++rear] = item;

(3) 자료 삭제(Delete) element delete(int front, int rear) { if(front == rear) { printf("queue is empty!\n"); return; } return queue[++front];

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

3.3 원형 큐(Circular Queue) (1/3) 원형 큐의 정의 큐의 배열(arrangement)을 원형으로 표현. 큐를 구성하는 배열의 처음과 끝을 이어놓은 형태의 큐. Front = 0; rear = 0; N개의 원소를 갖는 원형 큐 … … [n-4] I1 [4] [n-3] [4] [n-3] I4 I2 I3 [3] [n-2] [3] I3 [n-2] I2 I4 I1 [2] [n-1] I5 [2] [n-1] [1] [0] [1] [0] front = 0; rear = 4 front = n-5; rear = 0

3.3 원형 큐(Circular Queue) (2/3) (1) 자료 삽입(CQqadd) void CQadd(int front, int rear, element item) { rear = (rear + 1) % QUEUE_SIZE; if(front == rear) { printf("queue is full!\n"); return; } queue[rear] = item;

3.3 원형 큐(Circular Queue) (3/3) (2) 자료 삭제(CQdelete) element CQdelete(int front, int rear) { if(front == rear) { printf("queue is empty!\n"); return; } else { front = (front + 1) % QUEUE_SIZE; return queue[front];

3.4 데크(Deque : Double Ended Queue) 정의 삽입과 삭제가 양쪽 끝에서 모두 허용될 수 있는 선형 리스트 스택과 큐를 선형리스트 구조에 복합 시킨 형태. 두개의 스택의 bottom 부분이 서로 연결된 것. 삭제 A B C D 삽입 삽입 삭제 end1 end2

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

Deque의 종류 입력 제한 데크 출력 제한 데크 입력이 한쪽 끝에서만 일어나도록 제한 (스크롤(scroll)) 출력이 한쪽 끝에서만 일어나도록 제한 (셀프(shelf))

3.5 수식표현 (1/4) 연산자의 우선순위 연산에서 괄호가 없을 경우 또는 괄호 내에서 우선순위가 필요 연산자 우선 순위 단항연산자 -, ! 6 *, /, % 5 +, - 4 <, <=, >, >= 3 && 2 ∥ 1

수식표현 (2/4) 수식 표기법 중위(infix) 표기 방법 전위(prefix) 표기 방법 <피연산자-연산자-피연산자> 예) A + B 전위(prefix) 표기 방법 <연산자-피연산자-피연산자> 예) + A B 중위 표기 -> 전위 표기 방법으로의 전환 예) (((((-A) / B) * C) + (D * E)) - (A * C)) => - + * / - A B C * D E * A C 후위(postfix or reverse polish) 표기 방법 <피연산자-피연산자-연산자> 예) A B + 컴퓨터가 수식을 계산하기에 가장 적합한 방법 컴파일러 : 중위표기 수식을 후기 표기 방법으로 변환한 후 스택을 이용 수식 계산

수식표현 (3/4) 후위 표기식의 장점 후위 표기식 계산 알고리즘 괄호를 필요로 하지 않는다. 연산자들의 우선 순위가 필요 없게 된다. 스택을 사용하면 식을 왼쪽에서 오른쪽으로 읽어 가면서 쉽게 계산할 수 있다. 후위 표기식 계산 알고리즘 수식을 구성하는 원소(token)을 읽어서 그것이 피연산자이면 스택에 넣고, 연산자이면 필요한 수만큼의 피연산자를 꺼내어 연산을 수행하고 그 결과를 스택에 다시 넣는다

수식표현 (4/4) 스택을 이용한 후위 표기방식의 계산: 2 3 + 4 * ①’2’ 와 ‘3’을 스택에 삽입(push) 한다. ②’+’ 연산자를 만나면 스택에 있는 자료들을 꺼내어(pop) ’+’연산을 수행(5). ③’5’를 스택에 삽입(push) 한다. ④’4’를 스택에 삽입(push) 한다. ⑤’*’연산자를 만나면 스택에 있는 자료들을 꺼내어(pop) ’*’연산을 수행한다(20). ⑥’20’을 스택에 삽입(push) 한다. ⑦ 더 이상의 입력이 없으므로 스택의’top’에 있는’20’을 결과로 한다.

수식표현 (4/4) 중위 표기식을 후위 표기식으로의 변환 알고리즘 중위 표기실을 연산자들의 우선순위에 따라 완전한 괄호를 포함하는 식으로 표현 모든 연산자들을 그와 대응하는 오른쪽 괄호의 밖으로 옮김 괄호를 모두 제거

수식표현 (4/4) 중위에서 후위 표기식으로 변환 시 스택 이용 ① 피연산자는 즉시 출력한다. ② 스택의’top’에 있는 연산자의 우선 순위(precedence hierarchy)가 스택에 들어올 연산자보다 작으면’push’한다. 예) x + y * z

수식표현 (4/4) 괄호가 있는 경우의 변환 ① 피연산자는 출력한다. ② 오른쪽 괄호가 나타날 때까지 연산자는’push’ 한다. ③ 오른쪽 괄호가 나타나면 왼쪽 괄호까지 연산자는 ‘pop’ 하고 왼쪽 괄호는 삭제한다. ④ 새 연산자가 스택의’top’ 에 있는 연산자보다 우선 순위가 높으면 ‘push’하고, 아니면 ‘pop’ 한다.

수식표현 (4/4) 예) a * (b + c) * d