Chapter 3. STACKS AND QUEUES

지환·2022년 4월 8일
DS - Horowitz
0

computer science 에서 자주 사용되는 두가지 data type
1. Stack
2. Queue

3.1 Stack

Last-In-First-Out (LIFO)

System stack

run-time때 program이 함수를 process하기위해 사용하는 System stack이 그 예시다.
함수가 호출되면 activation record 혹은 stack frame 이라 불리는 structure가 만들어져서 system stack에 추가된다.
처음에 이 stack frame은 이전 stack frame을 가리키는 포인터와 return adress를 포함한다. (return adress는 함수 반환후 돌아갈 위치를 저장한다.)
A 함수 내에서 B 함수를 호출한다면, A 함수의 stack frame에는 local variable(not static)이나 parameter 같은 정보들이 A의 stack frame에 추가된다.
그리고 B 함수의 stack frame이 system stack에 추가된다.

모든 함수가 이런식으로 쌓이며, recursive의 경우도 마찬가지다.
하지만 recursive는 많은 양의 system stack memory를 필요로 할 수 있다.(심하면 싹다..)

Stack ADT

자세한건 p.110
Functions엔 (1)Create, (2)IsFull, (3)IsEmpty, (4)Push, (5)Pop 이 있다.

Stack using Arrays

간단하게 1차원 배열로 구현할 수 있다.
(element structure의 member 원하는대로 바꾸고 추가해서 쓰면 됨.)

#define MAX_STACK_SIZE 100
typedef struct {
	int key;
    /*other fields*/
} element;
element stack[MAX_STACK_SIZE];
int top = -1;

top이 제일 위 element를 가리킨다.

3.2 STACKS USING DYNAMIC ARRAYS

(이 방법으로 해야 knk에서처럼 instance도 만들고 하지)
(여기선 그게 중점이 아니긴 하지만)

typedef struct {
	int key;
    /*other fields*/
} element;

element *stack;
MALLOC(stack, sizeof(*stack))
int capacity = 1;
int top = -1;

초기 capacity는 1이다.
일반 array 버전과 다르게, stackFull 이어도 그냥 종료해버리지 않고 capacity를 2배로 늘린다.(REALLOC)

이렇게 doubling하는게 시간이 꽤 걸리는 작업으로 보일 수 있지만 예상보다 빠르다.
memory 할당하는데 O(1)이라 가정하고, element 하나 옮기는데 O(1)이라 가정하면 전체 doubling하는데 드는 시간은 O(capacity)이다.(capacity 만큼의 element가 있을테니 O(1*capacity))
즉, 한번의 push에 대해선 O(capacity) 이다.

좀 더 일반화해서,
capacity가 2k2^k(두배씩 늘어나니까)인 경우 time은 ∑i=1k2i\displaystyle\sum_{i=1}^k 2^i이므로, O(2^k) 가 된다.
여기서 push하는 횟수인 n은 적어도 2k−12^{k-1}보다 크므로(capacity가 2^k까지 늘어나려면 당연),
O(n) 이다. (생각보다 그렇게 오래 걸리진 않음)

n > 2^(k-1) 이므로 2n > 2^k 이다. 따라서 O(n)..

3.3 QUEUES

add 되는 곳을 rear, delete 되는 곳을 front라고 한다.
First-In-First-Oout (FIFO)

Queue ADT

자세한건 p.115
functions엔 (1)Create, (2)IsFull, (3)IsEmpty, (4)Add, (5)Delete 이 있다.

Queue Using Arrays

front, rear 변수 두개 있는거 말곤 stack이랑 다를게 없음. (front는 front위치, rear는 rear위치 정직하게 가리킴. 둘의 initial value는 -1)
Pass.

Example 3.2 (Job scheduling)

queue를 사용하는 예시 중 OS의 job queue가 있다.
priority를 사용하지 않는다면, 입력된대로 처리되기때문에 queue를 이용한다.

queue를 그냥 1차원 배열에 넣고 쓰면, queue가 꽉 찼을때 다시 제일 왼쪽으로 이동시켜야 한다.

이런 불필요한 소모를 줄이기위해 queue를 원형으로(circular queue) 만들 수 있다.
Circular queue에선 front가 front 앞의 위치를 가리킨다.(코드 간단하게 하기위해)

시계 방향으로 돌아가기 때문에 array의 MAX_QUEUE_SIZE-1 위치 다음은 0이다.
따라서 front나 rear를 증가시킬때 이를 고려해야한다.
(rear+1)%MAX_QUEUE_SIZE;

Empty와 Full 둘다 front == rear 라서 주의해서 구분해야한다. queue가 다 차기 직전에 size를 증가시키거나(다 채워놓고나서 full인지 empty인지 구분할 순 없음),
lastOperationIsAddq 변수나 size 변수를 선언해 확인하는 방법이 있다.(후자는 ppt에 나오네)

2.4 CIRCULAR QUEUES USING DYNAMICALLY ALLOCATED ARRAYS

꽉차기 직전에 stack처럼 그냥 doubling 해버리면 안된다.
우리가 circular로 생각을 하는 것뿐이지 실제 메모리엔 1차원배열처럼 저장되기 때문에, 이 경우(c)를 조심해야 한다.

그래서
(1)doubling한 뒤 원래 queue의 오른쪽 부분을 doubling된 queue의 제일 오른쪽으로 옮기거나
(2)두배 크기의 새로운 memory를 따로 할당받아서 자리에 맞게 옮겨야 한다.

(1)의 경우 2*capacity - 2 elements를 복사해야 한다. 이유
(2)의 경우 capacity - 1 elements를 복사해야 한다.(1보다 fast)
2배 크기 memory를 따로 할당받고(newQueue), queue[front+1] ~ queue[capacity-1]까지 newQueue[0]부터로 옮긴다.
그리고 queue[0] ~ queue[rear]까지 newQueue[capacity-front-1]부터로 옮긴다.(뒤에 그대로 붙임)
이전 queue는 free.

realloc할때 공간크기 충분하면 굳이 옮기지 않는다고 배웠는데,
여기선 worst case를 생각하는거라 다 옮긴다고 보는듯

(2) 구현

void queueFull() {
	element *newQueue;
    MALLOC(newQueue, 2 * capacity * sizeof(*queue))
    
    int start = (front+1) % capacity;
    if (start < 2)  //no wrap around
    	copy(queue + start, queue + start + capacity - 1, newQueue);
    else {  //queue wraps around
    	copy(queue + start, queue + capacity, newQueue);
        copy(queue, queue + rear + 1, newQueue + capacity - start);
    }
    
    front = capacity * 2 - 1;
    rear = capacity - 2;
    capacity *= 2;
    free(queue)
    queue = newQueue;
}
copy 함수는 (첫번째인자)~(두번째인자-1) 주소에 있는 값을 세번째 인자에 copy

3.5 A MAZING PROBLEM

maze 길 찾는 프로그램(처음엔 꼭 옳은 길로만 가진 않지만, 한번 찾아두면 그 다음부턴 그걸 써먹을 수 있다.)

maze representation
2차원 배열을 이용해 0은 길을, 1은 벽을 나타내도록 한다.
경계의 조건을 따로 체크하는 것 보다 maze를 1로 둘러싸버린다.
즉 전체 크기는 (가로+2)×(세로+2)가 된다.

가능한 방향은 N, NE, E, SE, S, SW, W, NW 8개이다.
편리를 위해 각 방향은 0~7의 숫자로 나타내고(array), 각 방향에대한 horizontal/vertical 이동정보를 구조체에 저장해두자.
(나중에 방향별로 어떻게 이동할지 switch문 같은거 쓰는거보다 훨씬 편리)

typedef struct {
	short int vert;
    short int horiz;
} offsets;
offsets move[8];

move[0].vert = -1;  move[0].horiz = 0;
.
.
move[7].vert = -1;  move[7].horiz = -1;

탈출
N부터 시계방향으로 길을 가본다.
가본 길은 stack에 저장하고, 만약 갔던 길이 모두 막혀있으면 pop해서 이전 위치로 돌아간 뒤 탐색했던 곳 다음 방향으로 가본다.
갔던 곳을 표시하기위해 mark 2차원 배열을 같이 사용한다.(모두 0으로 초기화, 갔던 곳은 1)

stack은 row, col, dir 정보를 저장한다.(dir은 다음으로 가야할 방향을 저장해준다.)

typedef struct {
	short int row;
    short int col;
    short int dir;
} element;

stack size는 maze의 0 개수만큼만 크면된다.(벽은 갈일이 없고, 간 길은 다시 가지 않음)
0은 최대 '가로×세로'개 있다.

path 함수

EXIT_ROW, EXIT_COL는 출구를, found는 출구발견 유무를 나타낸다.
(+위에서 말한 정보들 모두 선언됐다고 가정)

void path(void) {
    element curPos;
    element newPos;
    
    stack[0].row = 1; stack[0].col = 1; stack[0].dir = 2; top = 0; //초기 위치 stack에 저장
    //dir은 어차피 2(East)부터 봐야되니까 2 저장해도되지않나..? 책도 1인데뭐
    mark[1][1] = 1;
    
    while (top > -1 && !found) {
    	curPos = pop();  //8방향 다 돌았는데 갈곳이 없어야지만 pop
        while (curPos.dir < 8  && !found) {
        	newPos.row = curPos.row + move[curPos.dir].hori;
            newPos.col = curPos.col + move[curPos.dir].vert;
            newPos.dir = 0;
            
            curPos.dir++;  //해당 방향으로 가봤으니 ++해준다.
            
            if (newPos.row == EXIT_ROW && newPos.col == EXIT_COL) //출구!
            	found = TRUE;
            else if (!mark[newPos.row][newPos.col] && !maze[newPos.row][newPos.col]){
            	//갔던 곳도 아니고 벽도 아니면 그리로 간다(물론 출구도 아니고..)
            	mark[newPos.row][newPos.col] = 1;
            	push(curPos);  //빼와서 썼던 curPos는 다시 push
                curPos = newPos;  //혹은 멤버 하나하나 assign, 책에선 하나하나 assign하네
            }
        }
    }
    
    if (found) {
    	//서식 이쁘게해서 경로 출력
    }
    else
    	printf("The maze does not have a path.\n");
}

Analysis (path)
O(m*p) (m : number of row, p : number of column)

row, col 같은 변수를 따로 선언해서 쓰길래 일단 난 없이하는게 더 간단할거 같아서 저렇게 적음.
구조체에 직접 접근하는건 안좋을 수 있고, 변수 재활용성때문에 그렇게 한다고 하네들..
일단 위 코드도 잘 작동하긴함.

3.6 EVALUATION OF EXPRESSIONS

3.6.1 Expressions

CS 분야에서 expression의 표현법과 계산법에 관심이 많다.

3.6.2 Evaluating Postfix Expressions

대부분은 infix notation을 많이 쓴다.(1+2×3)
하지만 compiler는 괄호가 필요없는 postfix notation을 주로 사용한다.
postfix notation에선 피연산자들 옆에 연산자를 작성한다.
ex. 1+2×3 = 12+3×

postfix를 계산하는게 infix보다 훨씬 편하다.
posftfix 계산법
(1)왼쪽에서 오른쪽으로 scan하다가
(2)operand가 나오면 stack에 넣고,
(3)operator가 나오면 stack에서 두개를 pop해서 계산 한 뒤, 다시 stack에 push한다.
(4)이 과정을 expression이 끝날때까지 반복하면 stack에는 결과가 남게된다.

자세한 코드는 생략(p.133)
: operand는 한자리 숫자로 제한, operator 종류도 binary로만 제한해서 간단하게 했다.
enumeration을 통해 operator(plus, minus, ...)와 operand를 표시할 수 있는 type을 만들어준다.
getToken이란 함수를 따로 만들어서 character 하나씩 읽어오고 어떤 종류(enumeration)인지 switch로 분류하는 작업을 해준다.
getToken 호출한 뒤 token 종류에 맞는 작업을 수행한다.(push or pop)
operand는 -'0'을 해서 숫자로 변환해준다.

enumeration이나 getToken을 따로 만든게 좀 과해보이긴한데 
infix to postfix 함수도 같이 생각하면 따로 빼두면 좋은 기능이다.

3.6.3 Infix to Postfix

아래와 같은 방식으로 infix -> postfix로 바꿀 수 있다.
1. 싹다 괄호 친다.
2. binary operator는 해당 오른쪽 괄호 위치에 오도록 한다.(replace)
3. 모든 괄호를 제거한다.
하지만 이건 손으로 할때나 쉽지 구현하긴 쉽지 않다.

infix나 postfix나 operands의 순서는 같다.
그 점을 이용해서
1. 왼쪽부터 scan하며 operands는 순서대로 적고,
2. operator를 precedence에 의거해 작성한다.

operator 적는 법

operator를 적는 법이 좀 골치아픈데,
다음 오는 operator의 precedence가 같거나 낮으면 원래 있던 애(같거나 낮은 애 전부)를 pop해서 그 위치에 작성, 다음에 오는 operator는 push한다.
높으면 해당 operator도 일단 push해서 저장해둔다.
식의 끝에서도 모두 pop해서 작성한다.

이해를 위한 예시)
a+b×c
모두 괄호치면, (a+(b×c)) 가 된다.
여기서 우측괄호 위치로 operator를 옮기면 되는데, 오른쪽 괄호의 위치는 (binary operator라고 제한했으니) 다음 operator 위치 or 식의 끝이다.
근데 이전 operator보다 precedence가 높으면 그곳은 오른쪽 괄호가 아니기때문에 stack에 push 해두는 것이다.
((a+(b×c))에서 × 자리엔 오른쪽 괄호가 없다.)
이전 operator보다 precedence가 낮으면 그곳은 오른쪽 괄호이기 때문에 stack에서 pop하고 적어주고, 해당 operator는 push한다.
(((a×b)+c)에서 + 자리엔 오른쪽 괄호가 있다.)

괄호가 나오면, 좌측괄호는 일단 stack에 쌓는다.
그러다가 같거나 낮은 precedence operator가 나오면 하던대로 하면 되지만, 우측 괄호가 나오면 좌측 괄호가 나올때까지 모두 pop해서 작성한다.
즉, 괄호 안도 작은 expression인 셈이고, 우측 괄호가 나오면 식의 끝이니까 똑같이 해주는거다.

왼쪽 괄호 다음 operator도 일단 들어오긴 해야되기때문에,
왼쪽 괄호는 stack 밖에 있을땐 가장 높은 precedence여야하고,
stack 내에 있을땐 가장 낮은 precedence여야한다.
따라서 precedence 배열을 두개 만들어서 진행해야한다.
(위에서 만든 precedence enumeration type을 그대로 사용하기엔, 우선순위를 명확히 하기 힘들다.)

자세한 code 생략(p.137)

3.7 MULTIPLE STACKS AND QUEUES

한 memory 공간에 여러 개의 stack을 넣자.

2개 stack)
하나는 stack[0]부터, 하나는 stack[MEMORY_SIZE - 1]부터 stack을 만들 수 있다.
전자는 top이 증가하지만, 후자는 top이 감소한다.

n개 stack)
사전 정보가 있다면 그에 맞게 memory를 나누면 되지만, 보통은 n개의 memory를 같게 나눈다.
보통 boundary[] 배열은 각 구간의 첫부분 element 왼쪽을 가리키게해서 구간을 나누고, top[] 배열도 선언해서 각자 top을 만들어준다.
boundary[0] = top[0] = -1;로 해두고, 나머지는 반복문으로 초기화한다.
boundary[n] = MEMORY_SIZE - 1;로 해줘서 마지막 stack도 경계를 구분해준다.(일반화)

boundary[i] == top[i]이면 empty
top[i] == boundary[i+1]이면 full

stackFull
여기선 어떤 stack i가 꽉차도 모든 memory가 꽉 찬게 아니다.
중간중간 비는 공간이 있을 수 있는데, 이를 활용하는 방법은 다음과 같다.
1. 해당 stack(i) 기준 오른쪽 stack 중에 비는 stack j가 있다면(i<j<n),
i, i+1,...,j를 한칸씩 오른쪽으로 옮긴다.
2. 해당 stack 기준 왼족에 ~~
3. 오른쪽 왼쪽 둘다 없다면 memory가 꽉 찬것이다. error message 출력 후 종료.

profile
지환
이전 포스트

Chapter 2. ARRAYS AND STRUCTURES

다음 포스트

Chapter 4. Linked Lists

0개의 댓글