스택 (1) 스택(stack)과 큐(queue) 스택(stack) 순서 리스트(ordered list)의 특별한 경우

Presentation on theme: "스택 (1) 스택(stack)과 큐(queue) 스택(stack) 순서 리스트(ordered list)의 특별한 경우"— Presentation transcript:

1 스택 (1) 스택(stack)과 큐(queue) 스택(stack) 순서 리스트(ordered list)의 특별한 경우
순서 리스트: A=a0, a1, …, an-1, n  0 ai : 원자(atom) 또는 원소(element) 널 또는 공백 리스트 : n = 0인 리스트 스택(stack) 톱(top)이라고 하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트 스택 S=(a0,....,an-1): a0는 bottom, an-1은 top의 원소 ai는 원소 ai-1(0<i<n)의 위에 있음 후입선출(LIFO, Last-In-First-Out) 리스트

2 스택 (2) 원소 A,B,C,D,E를 삽입하고 한 원소를 삭제하는 예

3 스택 (3) 시스템 스택 프로그램 실행시 함수 호출을 처리
함수 호출 시 활성 레코드 (activation record) 또는 스택 프레임(stack frame) 이라는 구조를 생성하여 시스템 스택의 톱에 둔다. 이전의 스택 프레임(호출한 함수의 스택프레임)에 대한 포인터 복귀 주소 (함수가 종료된 후 실행되어야 할 명령문 위치) 지역 변수 (static 변수 제외) 호출한 함수의 매개 변수 함수가 자기자신을 호출하는 순환 호출도 마찬가지로 처리 순환 호출시마다 새로운 스택 프레임 생성 최악의 경우 가용 메모리 전부 소모

4 스택 (4) 주 함수가 함수 a1을 호출하는 예 (a) 함수 a1이 호출되기 전의 시스템 스택
(b) 함수 a1이 호출된 후의 시스템 스택 fp : 현재 스택 프레임에 대한 포인터 스택 포인터 sp는 별도로 유지 함수 호출 뒤의 시스템 스택

5 스택 (5) 스택 ADT 구현 일차원 배열 stack[MAX_STACK_SIZE] 사용
i번째 원소는 stack[i-1]에 저장 변수 top은 스택의 최상위 원소를 가리킴 (초기 : top = -1, 공백 스택을 의미함)

6 스택 (6) 스택 ADT (Abstract Data Type) ADT Stack
objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 stack∈ Stack, item∈ element, maxStackSize∈ positive integer Stack CreateS(maxStackSize) ::= 최대 크기가 maxStackSize인 공백 스택을 생성 Boolean IsFull(stack, maxStackSize) ::= if (stack의 원소수 == maxStackSize) return TRUE else return FALSE Stack Push(stack, item) ::= if (IsFull(stack)) stackFull else stack의 톱에 item을 삽입하고 return Boolean IsEmpty(stack) ::= if (stack == CreateS(maxStackSize)) return TRUE Element Pop(stack) ::= if (IsEmpty(stack)) return else 스택 톱의 item을 제거해서 반환

7 스택 (7) CreateS와 stackFull의 구현 Stack CreateS(maxStackSize) ::=
#define MAX_STACK_SIZE 100 /* 스택의 최대 크기 */ typedef struct { int key; /* 다른 필드 */ } element; element stack[MAX_STACK_SIZE]; int top = -1; Boolean IsEmpty(Stack) ::= top < 0; Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE-1; void stackFull() { fprintf(stderr, “Stack is full, cannot add element”); exit(EXIT_FAILURE); }

8 스택 (8) Push와 Pop 연산 구현 void push(element item)
{/* 전역 stack에 item을 삽입 */ if (top >= MAX_STACK_SIZE-1) stackFull(); stack[++top] = item; } 스택에 원소 삽입 element pop() {/* stack의 최상위 원소를 삭제하고 반환 */ if (top == -1) return stackEmpty(); /* returns an error key */ return stack[top--]; } 스택으로부터 삭제

9 동적 배열을 사용하는 스택 (1) 동적 배열을 이용
스택의 범위(MAX_STACK_SIZE)를 컴파일 시간에 알아야 하는 단점 극복 원소를 위해 동적으로 할당된 배열을 이용하고, 필요 시 배열의 크기를 증대시킴 Stack CreateS() ::= typedef struct { int key; /* 다른 필드 */ } element; element *stack; MALLOC(stack, sizeof(*stack)); int capacity = 1; int top = -1; Boolean IsEmpty(Stack) ::= top < 0; Boolean isFull(Stack) ::= top >= capacity-1; 초기 크기가 1인 동적할당 배열 stack을 사용

10 동적 배열을 사용하는 스택 (2) 스택 만원에 대한 새로운 검사 이용 MAX_STACK_SIZE를 capacity로 대체
함수 push 변경 함수 stackFull 변경 배열 stack의 크기를 확장시켜서 스택에 원소를 추가로 삽입할 수 있도록 함 배열 배가(array doubling) : 배열의 크기를 늘릴 필요가 있을 시 항상 배열의 크기를 두 배로 만든다. void stackFull() { REALLOC(stack, 2*capacity*sizeof(*stack)) capacity *= 2; } 배열 배가를 사용하는 stackFull

11 큐 (1) 큐 (queue) 한쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트
새로운 원소가 삽입되는 끝 – rear 원소가 삭제되는 끝 – front 선입선출(FIFO, First-In-First-Out) 리스트 원소 A, B, C, D, E를 순서대로 큐에 삽입하고 한 원소를 삭제하는 예

12 큐 (2) Queue 추상 데이터 타입 ADT Queue objects: 0개 이상의 원소를 가진 유한 순서 리스트
functions: 모든 queue Queue, item element, maxQueueSize positive integer Queue CreateQ(maxQueueSize) ::= 최대 크기가 maxQueueSize인 공백 큐를 생성 Boolean IsFullQ(queue, maxQueueSize ) ::= if (queue의 원소 수 == maxQueueSize) return TRUE else return FALSE Queue AddQ(queue, item) ::= if (IsFull(queue)) queueFull else queue의 뒤에 item을 삽입하고 이 queue를 반환 Boolean IsEmptyQ(queue) ::= if (queue == CreateQ(maxQueueSize)) return TRUE Element DeleteQ(queue) ::= if (IsEmpty(queue)) return else queue의 앞에 있는 item을 제거해서 반환

13 큐 (3) 큐를 순차 기억 장소로 표현 스택보다 더 어려움 1차원 배열과 두 변수 front, rear 필요
CreateQ, IsEmptyQ, IsFullQ의 구현 Queue CreateQ(maxQueueSize) ::= #define MAX_QUEUE_SIZE 100 /* 큐의 최대 크기 */ typedef struct { int key; /* 다른 필드 */ } element; element queue[MAX_QUEUE_SIZE]; int rear = -1; int front = -1; Boolean IsEmptyQ(queue) ::= front == rear Boolean IsFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1

14 큐 (4) addq와 deleteq 연산의 구현 void addq(element item)
{/* queue에 item을 삽입 */ if (rear == MAX_QUEUE_SIZE-1) queueFull(); queue[++rear] = item; } 큐에서의 삽입 element deleteq() {/* queue의 앞에 있는 원소를 삭제 */ if (front == rear) return queueEmpty(); /* returns an error key */ return queue[++front]; } 큐에서의 삭제

15 큐 (5) 작업 스케줄링 운영체제에 의한 작업 큐 (job queue) 생성 시스템에 들어간 순서대로 처리
큐를 순차 표현으로 구현할 때의 문제점 front rear Q[0] Q[1] Q[2] Q[3] Comments -1 1 2 J1 J J2 J J J3 J J3 J3 queue is empty job 1 is added job 2 is added job 3 is added job 1 is deleted job 2 is deleted 순차 큐에서의 삽입과 삭제 큐는 점차 오른쪽으로 이동 결국, rear 값이 MAX_QUEUE_SIZE-1과 같아짐 (큐는 만원) queueFull은 전체 큐를 왼쪽으로 이동시켜야 함 첫번째 원소가 q[0]에 오도록 조정, front = -1로 조정, rear도 다시 조정 배열 이동 시간이 많이 든다 최악의 경우 복잡도 : Q(MAX_QUEUE_SIZE)

16 큐 (6) 원형 큐(Circular queue) 를 사용하여 개선 큐가 배열의 끝을 둘러싸도록 함
변수 front는 큐에서 첫 원소의 위치로부터 시계 반대 방향으로 하나 앞 위치를 가리킴 rear rear rear C C D C D B B B A A front front front (a) 초기 (b) 삽입 (c) 삭제

17 큐 (7) 원형 큐 배열의 모든 위치는 다음과 앞 위치를 가짐
MAX_QUEUE_SIZE-1의 다음 위치 = 0 0의 앞 위치 = MAX_QUEUE_SIZE-1 원형 큐의 동작을 위해 front와 rear를 다음위치(시계 방향) 으로 이동시킴 if(rear == MAX_QUEUE_SIZE-1) rear=0; else rear++; // (rear+1) % MAX_QUEUE_SIZE와 동등 큐의 공백 조건 : front == rear 큐의 포화와 공백을 구분하기 위해 만원이 되기 전에 큐의 크기를 증가시킨다. front==rear가 포화인지 공백인지 구분하기 위해, 최대 원소 수를 MAX_QUEUE_SIZE가 아니라 MAX_QUEUE_SIZE -1로 한다

18 큐 (8) 멤버 함수 addq와 deleteq의 구현 void addq(element item)
{ /* queue에 item을 삽입 */ rear = (rear+1)%MAX_QUEUE_SIZE; if (front == rear) queueFull(); /* error를 프린트하고 끝낸다 */ queue[rear] = item; } 원형 큐에서의 삽입 element deleteq() { /* queue의 앞 원소를 삭제 */ element item; if (front == rear) return queueEmpty(); /* 에러 키를 반환한다 */ front = (front+1) % MAX_QUEUE_SIZE; return queue[front]; } 원형 큐에서의 삭제

19 동적 할당 배열을 이용하는 원형 큐 (1) 동적 할당 배열 사용 capacity : 배열 queue의 위치 번호
원소 삽입 시, 배열 크기 확장해야 함 함수 realloc 배열 배가 방법 사용 queue [0] [1] [2] [3] [4] [5] [6] [7] C D C D E F G A B B E front = 5, rear = 4 (b) 만원이 된 원형 큐를 펼쳐 놓은 모양 A F G [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13][14][15] C D E F G A B front = 5, rear = 4 front = 5 rear = 4 (c) 배열을 두 배로 확장한 뒤의 모양 (realloc을 이용하여 확장) (a) 만원이 된 원형 큐

20 동적 할당 배열을 이용하는 원형 큐 (2)  최대 복사 원소 수 : 2*capacity-2
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13][14][15] C D E F G A B front = 13, rear = 4 (d)세그먼트를 오른쪽으로 이동한 뒤의 모양  최대 복사 원소 수 : 2*capacity-2 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13][14][15] A B C D E F G front = 15, rear = 6 (e) 같은 내용의 다른 모양 최대 복사 원소 수 capacity-1로 제한 (1) 크기가 두배 되는 새로운 배열 newQueue를 생성한다. (2) 두번째 부분(즉, queue[front+1]과 queue[capacity-1] 사이에 있는 원소들)을 newQueue의 0에서부터 복사해 넣는다. (3) 첫번째 부분(즉 queue[0]와 queue[rear]사이에 있는 원소들)을 newQueue의 capacity-front-1에서부터 복사해 넣는다.

21 미로 문제(1) 미로(maze)는 1im이고 1jp인 이차원 배열 maze[m][p]로 표현 1 : 통로가 막힌 길 0 : 통과할 수 있는 길 입구 maze[1][1] 출구 maze[m][p] 예제 미로 (경로를 찾을 수 있는가?)

22 미로 문제(2) 현재의 위치 x : maze[i][j]
NW N NE [ i-1][j-1] [ i-1][j] [ i-1][j+1] W [ i][j-1] X [ i][j+1] E [ i] [j] [ i+1][j-1] [ i+1][j] [ i+1][j+1] SW S SE 가능한 이동 i=1이거나 m 또는 j=1이거나 p인 경계선에 있는 경우 가능한 방향은 8방향이 아니라 3방향만 존재 경계 조건을 매번 검사하는 것을 피하기 위해 미로의 주위를 1로 둘러쌈 배열은 maza[m+2][p+2]로 선언되어야 함

23 미로 문제(3) 이동할 수 있는 방향들을 배열 move에 미리 정의하는 방법
여덟 개의 가능한 이동 방향 : 0~7의 숫자로 표시 typedef struct { short int vert; short int horiz; } offsets; offsets move[8]; /* 각 방향에 대한 이동 배열 */ Name Dir move[dir].vert move[dir].horiz N NE E SE S SW W NW 현재 위치 : maze[row][col] 다음 이동할 위치 : maze[nextRow][nextCol] nextRow = row + move[dir].vert; nextCol = col + nove[dir].horiz; 이동 테이블

24 미로 문제(4) 이동할 수 있는 방향들을 배열 move에 미리 정의하는 방법 미로 이동 시, 현 위치 저장 후 방향 선택
잘못된 길을 갔을 때 되돌아와서 다른 방향을 시도할 수 있게 함 시도했던 길을 2차원 배열 mark에 기록해서 유지 한번 시도한 경로의 재시도 방지 위해 사용 maze[row][col] 방문  mark[row][col] = 1

25 미로 문제(5) initiallize a stack to the maze's entrance coordinates and direction to north; while (stack is not empty) {    /* 스택의 톱에 있는 위치로 이동*/    <rol, col, dir> = pop from top of stack;     while (there are more moves from current position) {        <nextRow, nextCol> = coordinate of next move;        dir = direction of move;        if ((nextRow == EXIT_ROW) && (nextCol == EXIT_COL))           success;        if (maze[nextRow][nextCol] == 0) && mark[nextRow][nextCol] == 0) {        /* 가능하지만 아직 이동해보지 않은 이동 방향 */            mark[nextRow][nextCol] = 1;           /* 현재의 위치와 방향을 저장 */           push<row, col, dir> to the top of the stack;           row = nextRow;           col = nextCol;           dir = north;        }    } } printf("No path found\n"); 초기 미로 알고리즘

26 미로 문제(6) 경로 유지 이한 스택 이용 시 element 재정의 스택 크기 최대 한계 결정해야 함
긴 경로를 가진 미로 예 경로 유지 이한 스택 이용 시 element 재정의 스택 크기 최대 한계 결정해야 함 미로에 있는 0의 수만큼만 크면 됨 m x p 미로에서 0의 최대 개수 : mp개 element 재정의 typedef struct { short int row; short int col; short int dir; }element;

27 미로 탐색 함수 최악의 경우 연산 시간 : O(mp) void path(void)
{/* 미로를 통과하는 경로가 있으면 그 경로를 출력한다. */ int i, row, col, nextRow, nextCol, dir, found=FALSE; element position; mark[1][1]=1; top=0; stack[0].row=1; stack[0].col=1; stack[0].dir=1; while (top>-1 && !found) { position = pop(&top); row = position.row; col = position.col; dir = position.dir; while (dir<8 && !found) { /* dir 방향으로 이동 */ nextRow = row + move[dir].vert; nextCol = col + move[dir].horiz; if (nextRow==EXIT_ROW && nextCol==EXIT_COL) found = TRUE; else if ( !maze[nextRow][nextCol] && !mark[nextRow][nextCol]) { mark[nextRow][nextCol]) = 1; position.row = row; position.col = col; position.dir = ++dir; add(&top, position); row = next.row; col = next.col; dir = 0; } else ++dir; if (found) { printf("The path is:\n"); printf("row col\n"); for (i=0; i<=top; i++) printf("%2d%5d", stack[i].row, stack[i].col"); printf("%2d%5d\n", row, col); printf("%2d%5d\n", EXIT_ROW, EXIT_COL); else printf("The maze does not have a path\n"); 미로 탐색 함수 최악의 경우 연산 시간 : O(mp)

28 수식의 계산(1) 수식 복잡한 수식 복잡한 지정문 피연산자, 연산자 및 괄호로 구성
(rear+1==front)||((rear==MAX_QUEUE_SIZE-1)&&!front)) -- (1) 복잡한 지정문 x=a/b-c+d*e-a*c (2) 피연산자, 연산자 및 괄호로 구성 수식이나 명령문의 의미를 이해하기 위해 연산의 수행 순서를 파악해야 함 e.g. a=4, b=c=2, d=e=3일 때 명령문 (2)에서 x값을 계산 ((4/2)-2)+(3*3)-(4*2) = = (o) (4/(2-2+3))*(3-4)*2 = (4/3)*(-1)*2 = (x) 연산자의 연산 순서를 결정하는 우선순위 계층(precedence hierarchy)를 가지고 있음

29 수식의 계산(2) C 언어의 우선순위 계층 토큰 연산자 우선순위 결합성 () [] . function call
array element struct or union member 17 left-to-right -- ++ increment, decrement2 16 left-to-right -- ++ ! - - + & * sizeof decrement, increment3 logical not one’s complement unary minus or plus address or indirection size (in bytes) 15 right-to-left (type) type cast 14 right-to-left * / % multiplicative 13 left-to-right + - binary add or subtract 12 left-to-right << >> shift 11 left-to-right > >= < <= relational 10 left-to-right == != equality 9 left-to-right & bitwise and 8 left-to-right ^ bitwise exclusive or 7 left-to-right

30 수식의 계산(3) C 언어의 우선순위 계층 (계속) 토큰 연산자 우선순위 결합성 | bitwise or 6
left-to-right && logical and 5 left-to-right || logical or 4 left-to-right ?: conditional 3 right-to-left = += -= /= *= %= <<= >>= &= ^= |= assignment 2 right-to-left , comma 1 left-to-right

31 후위 표기식의 연산 (1) 중위 표기법(infix notation) 후위 표기법(postfix notation)
가장 보편적인 수식 표기법 두 피연산자 사이에 이항(binary) 연산자가 위치 후위 표기법(postfix notation) 괄호를 사용하지 않는 표기법 연산자가 피연산자들 뒤에 옴 중위 표기 후위 표기 2+3*4 a*b+5 (1+2)*7 a*b/c ((a/(b-c+d))*(e-a)*c a/b-c+d*e-a*c 2 3 4*+ ab*5+ 1 2+7* ab*c/ abc-d+/ea-*c* ab/c-de*+ac*- 중위 표기와 후위 표기

32 후위 표기식의 연산 (2) 후위 표기식의 연산: 수식을 왼쪽에서 오른쪽으로 스캔 연산자를 만날 때까지 피연산자를 스택에 저장
연산자를 만나면 연산에 필요한 만큼의 피연산자를 스택에서 가져와 연산 연산 결과를 다시 스택에 저장 식의 끝에 도달할 때까지 위의 과정 반복 스택의 톱에서 해답을 가져온다 Token Stack [0] [1] [2] Top 후위 표기식의 연산 입력이 9개의 문자 스트링 6 2/3-4 2*+일 때 6 2 / 3 - 4 * + 6 6/2 6/ 6/2-3 6/ 6/ 6/ *2 6/2-3+4*2 1 2

33 후위 표기식을 계산하는 함수 int eval(void) { /* 전역 변수로 되어있는 후위 표기식 expr을 연산한다.
‘ \0’ 은 수식의 끝을 나타낸다. stack과 top은 전역 변수이다. 함수 getToken은 토큰의 타입과 문자 심벌을 반환한다. 피연산자는 한 문자로 된 숫자임을 가정한다. */ precedence token; char symbol; int op1,op2; int n = 0; /* 수식 스트링을 위한 카운터 */ int top = -1; token = getToken(&symbol, &n); while (token != eos) { if (token == operand) push(symbol-'0'); / *스택 삽입 */ else { /* 두 피연산자를 삭제하여 연산을 수행한 후, 그 결과를 스택에 삽입함 */ op2 = pop(); /* 스택 삭제 */ op1 = pop(); switch(token) { case plus: push(op1+op2); break; case minus: push(op1-op2); break; case times: push(op1*op2); break; case divide: push(op1/op2); break; case mod: push(op1%op2); } return pop(); /* 결과를 반환 */ 후위 표기식을 계산하는 함수 연산자들을 열거한 열거타입 (enumerated type)의 precedence 를 정의하면 편리함 typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand} precedence;

34 후위 표기식의 연산 (3) 보조 함수 getToken 수식 스트링으로부터 토큰을 얻기 위해 사용
precedence getToken(char *symbol, int *n) { /* 다음 토큰을 취한다. symbol은 문자 표현이며, token은 그것의 열거된 값으로 표현되고, 명칭으로 반환된다. */ *symbol = expr[(*n)++]; switch (*symbol) { case '(' : return lparen; case ')' : return rparen; case '+' : return plus; case '-' : return minus; case '/' : return divide; case '*' : return times; case '%' : return mod; case ' ' : return eos; default : return operand; /* 에러 검사는 하지 않고 기본 값은 피연산자 */ } 입력 스트링으로부터 토큰을 가져오는 함수

35 중위 표기에서 후위 표기로의 변환(1) 중위 표기식을 후위 표기식으로 변환하는 알고리즘 (1) 식을 모두 괄호로 묶는다.
(2) 이항 연산자들을 모두 그들 오른쪽 괄호와 대체시킨다. (3) 모든 괄호를 삭제한다. 예) 수식 a/b-c+d*e-a*c.  ((((a/b)-c)+(d*e))-(a*c))  ab/c-de*+ac*- Note : 피연산자의 순서는 불변

36 중위 표기에서 후위 표기로의 변환(2) 예) a+b*c로부터 abc*+를 생성
우선순위가 높은 연산자는 낮은 연산자보다 먼저 출력 스택의 톱에 있는 연산자의 우선순위가 스택에 들어올 연산자 보다 작을 때 이 연산자는 스택에 삽입 Stack [0] [1] [2] + * Top -1 1 Token a b * c eos Output ab abc abc*+

37 중위 표기에서 후위 표기로의 변환(3) 예) [괄호가 있는 수식] a*(b+c)*d로부터 abc+*d*를 생성 Stack
[0] [1] [2] * * ( * ( Top -1 1 2 Token a ( b + c ) d eos Output ab abc abc+ abc+* abc+*d abc+*d*

38 중위 표기에서 후위 표기로의 변환(4) 스택킹(stacking)과 언스택킹(unstacking)을 수행
우선 순위를 기반으로 하는 기법 ‘(‘ 괄호 때문에 복잡해짐 스택 속에 있을 때는 낮은 우선순위의 연산자처럼 동작 그 외의 경우 높은 우선순위의 연산자처럼 동작 해결 방법 : 두 가지 종류의 우선순위 사용 isp(in-stack precedence)와 icp(incoming precedence) 사용 스택 속의 연산자 isp가 새로운 연산자의 icp보다 크거나 같을 때만 스택에서 삭제됨 precedence stack[MAX_STACK_SIZE]; /*isp와 icp 배열 – 인덱스는 연산자 lparen, rparen, plus, minus, times, divide, mod, eos의 우선순위 값 */ static int isp[] = {0,19,12,12,13,13,13,0}; static int icp[] = {20,19,12,12,13,13,13,0};

39 postfix의 분석 : 토큰의 수가 n일 때 복잡도 Θ(n) void postfix(void)
{/* 수식을 후위 표기식으로 출력한다. 수식 스트링, 스택, top은 전역적이다. */    char symbol;    precedence token;    int n = 0;    int top = 0; /* eos를 스택에 삽입한다. */    stack[0] = eos;    for (token==getToken(&symbol,&n); token!=eos; token==getToken(&symbol,&n)) {       if (token == operand)          printf("%c", symbol);       else if (token == rparen) {          /* 왼쪽 괄호가 나올 때까지 토큰들을 제거해서 출력시킴 */          while (stack[top] != lparen)             printToken(pop(&top));          pop(&top); /* 왼쪽 괄호를 버린다 */       }       else          /* symbol의 isp가 token의 icp보다 크거나 같으면 symbol을 제거하고 출력          시킴 */          while (isp[stack[top]] >= icp[token])          add(&top, token);    }    while ((token=pop(&top)) != eos)       printToken(token);    printf("\n"); } postfix의 분석 : 토큰의 수가 n일 때 복잡도 Θ(n) 중위 표기식을 후위 표기식으로 변환

40 다중 스택 (1) 같은 배열 내에 두 개 이상의 스택을 구현 n개의 스택 각 스택의 최 하단 원소를 위한 고정점이 없음
스택의 예상 크기를 아는 경우 그 크기에 따라 나눔 스택의 예상 크기를 모를 경우 똑같은 크기로 나눔 #define MEMORY_SIZE 100 /* memory의 크기 */ #define MAX_STACKS 10 /* (가능한 스택의 최대 수)+1 */ /* 전역적 메모리 선언 */ element memory[MEMORY_SIZE]; int top[MAX_STACKS]; int boundary[MAX_STACKS]; int n; /* 사용자가 입력한 스택의 수 */

41 다중 스택 (2) 배열을 거의 같은 크기의 세그먼트로 나누는 코드 memory[m]에 있는 n 스택에 대한 초기 구성
top[0] = boundary[0] = -1; for (i=1; i<n; i++) top[i] = boundary[i] = (MEMORY_SIZE/n)*i; boundary[n] = MEMORY_SIZE-1; memory[m]에 있는 n 스택에 대한 초기 구성 m-1 boundary[0] boundary[1] boundary[n] top[0] top[1]

42 다중 스택 (3) 스택 i와 스택 i+1이 만났지만 메모리는 만원이 아닌 상태
void push(int i, element item) {/* item을 i번째 스택에 삽입 */ if (top[i] == boundary[i+1]) stackFull(i); memory[++top[i]] = item; } element pop(int i) {/* i번째 스택에서 톱 원소를 제거 */ if (top[i] == boundary[i]) return stackEmpty(i); return memory[top[i]--]; } 스택 i에 item 삽입 스택 i에서 item 삭제 스택 i와 스택 i+1이 만났지만 메모리는 만원이 아닌 상태 b[0] t[0] b[1] t[1] b[i] t[i] t[i+1] t[j] b[j+1] b[n] b[i+1] b[i+2] b = boundary, t = top

43 다중 스택 (4) 에러복구 함수 stackFull 메모리 내의 빈 공간이 있는 가를 결정
사용할 수 있는 자유 공간이 있다면 만원인 스택에 그 자유 공간을 할당하도록 다른 스택들을 이동시킴 (1) 스택 j와 j+1사이에 빈 공간이 있는, 즉 top[j]<boundary[j+1] (i<j<n)을 만족하는 최소의 j를 찾음 그러한 j가 있다면 스택 i+1, i+2, ..., j를 오른쪽으로 한 자리씩 이동시켜 스택 i와 i+1 사이에 하나의 공간을 만든다. (2) (1)에서 j를 찾지 못하면, 스택 i의 왼쪽을 조사 스택 j와 스택 j+1 사이에 빈 공간이 있는, 즉 top[j]<boudary[j+1] (1<j<i)를 만족하는 최대 j를 찾음 그러한 j가 있다면 스택 j+1, j+2,...,i를 왼쪽으로 한자리씩 이동시켜 스택 i와 i+1사이에 하나의 빈 공간을 만든다. (3) (1), (2)에서 j를 못 찾으면 빈 공간은 없음. 에러 메시지와 함께 종료