3-1강 - Stack, Stack using Dynamic Arrays (스택, 동적 배열로 만든 스택)

cf> Ordered List

1> 정의

- Ordered List : A = {a_0, a_1, ..., a_n-1} (n >= 0)

- element : a_i 

- n=0이면 null list (empty list)

2> stack과 queue

stack과 queue(special data type)는 ordered list(general data type)의 특수한 경우이다.

 

1. Stack

1) 개념

S = {a_0, a_1, ..., a_n-1}

1> top에서 삽입과 삭제가 일어나는 ordered list

2> a0는 가장 아래(bottom)에 있는 원소, a_n-1은 가장 위에(top)에 있는 원소

3> LIFO(Last in First out) : 제일 마지막으로 들어온 것이 제일 먼저 삭제

2) System stack

1> 함수 호출을 처리하는데 사용

2> 초기(a) : 함수 호출 -> stack frame 생성 -> stack frame을 top에 둔다.

- 초기에는 old<previous> stack frame pointer와 return address만 가진다.

- old<previous> stack frame pointer는 호출한 함수의 stack frame을 가리킨다.

- return address는 함수가 종료된 후 실행되어야 할 명령문 위치를 가리킨다.

3> 어느 한 순간에는 하나의 함수만 수행되니 stack frame이 top에 있는 함수가 실행된다.

4> 함수 내부에서 다른 함수 호출 

이 함수(P)가 다른 함수(Q)를 호출 -> 지역 변수와 호출한 함수(P)의 매개변수가 기존 함수(P)의 stack frame에 추가

-> 호출된 함수(Q)의 stack frame이 생성 -> system stack의 top에 호출된 함수(Q)의 stack frame이 위치한다.

-> 호출된 함수(Q)가 종료되면 system stack에서 이 함수(Q)의 stack frame이 삭제

-> top에 있는 호출한 함수(P)의 수행이 계속된다.

5> 결론 : 이처럼 stack의 구조대로 맨 마지막에 들어온 함수부터 종료된다.

6> 순환 호출 (자기 자신을 호출)

- 순환 호출을 할 때마다 새로운 stack frame을 생성

- 하지만 순환 호출은 system stack에 할당된 메모리의 상당 부분을 사용한다. (최악의 경우 가용 메모리 전부 사용한다.)

 

3) ADT Stack

1> object : 0개 이상의 element를 가지는 finite ordered list

2> function

- Stack CreateS(maxStackSize) : 최대 크기가 maxStackSize인 empty stack 생성

- Boolean IsFull(stack, maxStackSize) : 원소의 개수가 maxStackSize이면 true, 아니면 false

- Stack Push(stack, item) :  IsFull로 비었는지(true) 확인하고, 비어있다면(false) item을 stack의 top에 삽입
- Boolean IsEmpty(stack) : stack이 CreateS로 만든 empty stack과 같으면 true, 아니면 false
- Element Pop(stack) : IsEmpty로 확인, 비어있다면 return으로 종결, 아니면 top에 있는 item을 삭제하고 return 

 

 

 

4) 구현

1> Stack CreateS(maxStackSize)

- element = integer field 하나를 가지는 구조체

- element array = stack

- 내부가 비어있으니 top을 -1로 설정

// Stack CreateS(maxStackSize)

#define MAX_STACK_SIZE 100 /* maximum stack size */
typedef struct 
{
	int key 
	/* other fields */
}element;

element stack[MAX_STACK_SIZE];
int top = -1; // top이 -1이면 empty stack이다.

// Boolean IsEmpty(stack) ::=top < 0
// Boolean IsFull(stack) ::=top >= MAX_STACK_SIZE-1

 

cf> 에러 메시지

1> void stackFull() : 해당 stack이 꽉 차 있는 경우에 error 메시지 출력

2> void stackEmpty() : 해당 stack이 전부 비어 있는 경우에 error 메시지 출력

void stackFull()
{
    fprint(stderr, "Stack is full, cannot add element.");
    exit(EXIT_FAILURE);
}

void emptyFull()
{
    fprint(stderr, "Stack is empty, cannot delete element.");
    exit(EXIT_FAILURE);
}

 

2> void push(element item)

- 해당 stack이 꽉 차 있는지 확인 (top이 MAX_STACK_SIZE-1 이상인지 확인 -> 크다면 stackFull())

- 그렇지 않다면 (top 증가 -> item 삽입)

• top을 1 증가시키고
• 해당 index(top)에 item을 추가한다.

void push(element item)
{/* add an item to the global stack */
    if (top >= MAX_STACK_SIZE-1) 
    	stackFull();
    stack[++top] = item; 
    // 증감 연산자를 앞에 사용해서 top을 먼저 증가시킨다. 
    // 그리고 item을 stack의 해당 index(top)에 push한다. 
}

- top의 의미는 현재 맨 위(top)에 위치한 element의 index를 의미

- 그래서 empty는 원소가 1개 있는 stack의 top인 0보다 1 적은 -1로 정의한다.

 

3> element pop()

- 해당 stack이 전부 비어 있는지 확인 (top이 -1이면 비어있다. -> stackEmpty()로 에러메시지 출력)

- 그렇지 않다면 (element 출력 -> top 감소(element 제거))

• top에 있는 원소를 출력하고
• top을 1 감소시킨다.

element pop()
{/* delete and return the top element from the stack */
    if (top == -1) 
    	return stackEmpty(); /* returns an error key */
    return stack[top--];
    // 먼저 stack에서 top(끝)에 있는 원소를 출력하고 
    // 증감연산자로 top을 1 감소시킨다
}

 

cf> 위의 구현은 정적 할당이기 때문에 스택이 어떤 범위를 가지게 될지 컴파일 시간에 알아야 한다는 단점이 있습니다.

 

---

2. Stack using Dynamic Arrays

1) 개념

1> 먼저 malloc을 이용해서 element 하나의 크기만큼 동적할당을 한다.

- capacity : 현재 원소의 개수 (초기에 1로 설정한다.)

2> 그리고 stack 내부가 꽉 찼을 때마다 realloc함수 동적 할당으로 메모리를 확장시킨다.

- realloc으로 2*capacity*sizeof(*stack)으로 2배씩 증가시킨다.

- 그리고 메모리가 확장되었으니 capacity도 2배로 증가시킨다.

 

2) 구현

1> stack CreateS()

#include <stdio.h>
#include <stdlib.h>

// Stack CreateS() ::=
typedef struct 
{
	int key;
	/* other fields */
} element;

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

// Boolean IsEmpty(stack) ::= top < 0;
// Boolean IsFull(stack) ::= top >= capacity-1;

2> void stackFull()

- realloc으로 2*capacity*sizeof(*stack)으로 2배씩 증가시킨다.

- 그리고 메모리가 확장되었으니 capacity도 2배로 증가시킨다.

void stackFull()
{
	realloc(stack, 2 * capacity * sizeof(*stack));
	capacity *= 2;
}