자료구조[3] Stack

‍박성령·2024년 10월 1일

자료구조

목록 보기

3/12

Stack

기본 개념

스택이란 동종 아이템들의 그룹이다.
제거(pop)과 추가(push)는 스택의 윗 부분에서 일어난다.

스택은 기본적으로 LIFO ("Last In First Out") 구조이다.
보통 우리가 사용하는 "ctrl + z" 나 browser의 뒤로가기 등의 직전의 상태를 기억하는 일에 활용한다.

스택 정의

다음은 스택의 정의이다.

class StackType
{
public:
    
    StackType();
    void push(ItemType item);
    ItemType pop();

    bool size() const;
    bool isFull() const;
    bool isEmpty() const;
    
    void printStack();
    
private:
    int top;
    ItemType data[MAX_ITEMS];
};

const는 관찰자의 의미로 멤버 변수를 수정할 수 없다는 뜻이다.

스택에 아무 Item도 없을 때 top은 -1로 지정한다. 스택은 array로 만드는데 array의 index 0번에 첫번째 Item이 들어오고 이것이 top이 되며 top이 0으로 지정되기 때문이다.

함수 정의

StackType::StackType()
{
    top = -1;
}

bool StackType::size() const
{
    return (top + 1);
}

bool StackType::isEmpty() const
{
    return (top == -1);
}

bool StackType::isFull() const
{
    return (top ==  MAX_ITEMS - 1);
}

void StackType::push(ItemType newItem)
{
    if(isFull()){
        return;
    }
        
    top++;
    data[top] = newItem;
}

ItemType StackType::pop()
{
    if( isEmpty() ){
        return temp;
    }
    
    ItemType result = data[top];
    top--;
    
    return result;
}

스택의 size나 isEmpty는 top을 기준으로 판단한다.
push는 list의 append와 비슷하고 pop은 그냥 top -1 로 구현한다.

Class Template

C++ 객체지향 수업에서 배운 개념으로 다양한 Type을 지원하는 class를 만들고 싶은데 이를 일일이 다 작성하기 번거로우니까 나온 개념임

class를 작성할 때 다음과 같이 작성한다.

template <class T>
class Test{
private:
	T x;
    T y;
public:
	Test();
	T TestFunc2();
    void TestFunc1(T val);
};

class의 함수를 정의 할 땐 함수 전부 위에다 template<class T>를 작성해주어야 한다.

그리고 사용할 땐 다음과 같이 작성한다.

int main(){
	Test<int> A(10, 10);
    return 0;
}

또한 template를 사용할 시 헤더파일(.h)에 .cpp 내용까지 전부 작성해야한다. (파일 분리를 하면 안된다.)

Pointer

포인터란 메모리 주소를 저장 하고있는 변수이다.
포인터는 다음과 같이 정의한다.

int *ptr; // int형 pointer
char *q; // char형 pointer

포인터가 가리키는 값을 역참조 할때는 포인터 앞에 *을 붙인다.

int x;
x = 12;
int *ptr;
ptr = &x; // x의 주소 값 할당

cout << ptr << endl; // x의 주소 값
cout << *ptr << endl; // x 값
cout << &ptr << endl; // ptr의 주소 값

*ptr = 5; // x값을 5로 변경

Pointer equal 관계
Pointer끼리의 equal관계는 뒤에 있는 pointer가 앞에 있는 pointer를 가리키는 것이 아니고 앞에 있는 pointer가 가리키는 값을 가리키는 것임

Null Pointer
의미 없는 값 0을 갖고 있는 pointer 아무것도 가리키지 않는다. (주소값 0을 가리키는 것이 아님)

NULL과 nullptr을 잘 구분해야함 NULL이 Pointer느낌이 강하긴 하지만 상수 0으로 정의 되어있기 때문에 function overloading시 애매한상태가 된다.
그러므로 NULL과 nullptr을 구분해서 사용하도록 하자.

Memory Allocation Types

CODE segment

맨 위의 코드 영역은 프로그램의 실행 가능한 코드를 포함하고 있다.
그렇다면 변수들은 어디에 할당될까?

STACK segment

다음 코드를 살펴보자.

int add(int c, int d){
	int e = c + d;
    return e;
}

int add_interface(int a, int b){
	int temp_a = a;
    int temp_b = b;
    int ret = add(temp_a, temp_b);
    return ret;
}

int main(){
	int main_ret = add_interface(3, 5);
    return 0;
}

함수의 Call 순서는 main() -> add_interface() -> add() 이다.
함수의 종료 순서는 add() -> add_interface() -> main() 이다.

stack에서 보았던 LIFO구조와 동일한 것을 알 수 있다.

그러므로 call된 함수들은 메모리 맵의 stack이라는 곳에 push된다.
여기에 추가로 함수들의 지역 변수까지 모두 stack에 같이 들어가게 된다.
함수가 종료될 때에는 stack에서 pop한다.

그리고 이렇게 Stack에 쌓인 것들을 Activation Record라 부르고 이 Activation Record 안에는 지역변수와 프로그램 수행에 필요한 정보들을 포함하고 있다.

이를 Automatic Allocation이라 부른다.

모든 지역 변수들은 컴파일할 때 크기가 정해져서 stack에 할당 되도록 한다.

HEAP segement

다음 코드를 살펴보자.

void make_array(){
	int cnt = 0;
    cin >> cnt;
    int temp_array[cnt];
}

위 처럼 코드를 작성하면 컴파일 되지 않는다. 지역 변수의 크기는 컴파일 할 때 정해져야 하기 때문이다. 이러한 동적 할당을 하기위해서 new라는 문법이 도입됐다.

void make_array(){
	int cnt = 0;
    cin >> cnt;
    int *temp_array;
    temp_array = new int[cnt];
}

위 처럼 코드를 작성하면 런타임 중에 메모리에 동적으로 할당되게 된다.
이는 HEAP이라는 공간에 할당되게 된다. stack과 독립적인 공간이며, 모든 함수가 HEAP을 공유하여서 함수가 종료돼도 변수가 살아있다.

그렇기 때문에 할당 해제를 하지않으면 HEAP에는 동적 할당된 메모리 공간이 있는데 이를 가리킬 Pointer가 stack 영역에서 함수 종료와 동시에 사라지기 때문에 메모리 누수가 발생하는 것이다. (HEAP공간에 접근 할 방법이 없음)

이를 Dynamic Allocation이라 한다.

메모리 누수를 발생시키지 않기 위해선 첫 번째로 delete를 이용해 할당 해제를 해주는 것이다.
두 번째는 동적 할당에 접근할 수 있는 pointer를 return을 이용하여 살려두는 방법이다.

int *make_array(){
	int cnt = 0;
    cin >> cnt;
    int *temp_array;
    temp_array = new int[cnt];
    return temp_array;
}

세 번째는 pointer를 call by reference를 이용하여 살려두는 방법이다.

void make_array(int * & pt){
	int cnt = 0;
    cin >> cnt;
    int *temp_array;
    temp_array = new int[cnt];
    pt = temp_array;
}

int main(){
	int *pt_array;
    make_array(pt_array);
    return 0;
}

그리고 프로그램(프로세스)이 종료되었을 때에도 동적으로 할당된 메모리가 할당 해제되지 않을까?
답은 "할당 해제된다."이다.
프로그램을 1개 실행하면 위의 그림과 같이 Memory map을 1개 할당 해준다. 이 때 프로그램을 종료할 시 Memory map이 통째로 사라지므로 할당 해제되는 것이다.