Chapter 3: Stack

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Stack

What is Stack?

▶ Logical (or ADT) level

 

Stack is a group of homogeneous items (elements).

Removal (pop) and addition (push) of stack items can only occur at the top of the stack.

 

A stack is a LIFO "Last In, First Out" structure.

e.g., Undo(무효로 하다, Ctrl + z), Back (browser 뒤로가기), Stack trace

 

※ stack trace: 프로그램에서 에러가 발생했을 때, 문제를 추적할 수 있도록 함수 호출 순서를 보여주는 로그이다.

 

Operations

▶ Logical Level

 

Definition

▶ Implementation Level

• const 함수: class 내에 있는 멤버 변수들(data, top)의 값을 변화시키지 못하는 함수이다. (observer에 적용 가능)

Stack Implementation Using Array

▶ Logical (or ADT) level

• top: top item의 index 보관해주는 역할을 한다.

Removal (pop) and addition (push) of stack items can only occur at the top of the stack(= at the end of the array).

 

Stack Constructor

▶ Logical (or ADT) level

▶ Implementation Level

 

size()

▶ Implementation Level

 

시간 복잡도: O(1)

 

isFull()

▶ Implementation Level

 

시간 복잡도: O(1)

 

※ 연산자 우선 순위: ++, --, !, &(주소 연산), *(간접지정 연산) -> *(곱셈), /, % -> +, - ->  ==, != -> &(AND), ^(XOR), | -> =, +=

 

isEmpty()

▶ Implementation Level

시간 복잡도: O(1)

 

push()

▶ Logical Level

▶ Implementation Level

시간 복잡도: O(1)

 

Similar to appendItem() of Unsorted List.

 

pop

▶ Logical Level

▶ Implementation Level

 

시간 복잡도: O(1)

 

이렇게 stack은 undo와 같이 최근의 상태를 기억해야 되는 특수한 목적으로 사용될 때,

모든 처리를 O(1)이라는 시간 안에 굉장히 빠르게 처리할 수 있는 자료 구조체이다.

Tracing Client Code

client code: class(자료구조)를 만들었을 때, 이를 사용하는 코드이다.

• e.g., 자료구조가 스택이라면, 이 스택을 사용하는 push, pop과 같은 함수들이 client code로 작성됨

▶ Tracing Client Code

Class Template

▶ This is an Integer-type stack.

 

What if I need a char-type stack?

▶ We need to edit "typedef" statement(명령).

 

typedef를 사용하면 자료 구조체의 데이터 타입을 한 번에 바꿔줄 수 있다.

 

What if I need both?

Class Template can help!

 

A class template allows the compiler to generate multiple versions of a class type by using type parameters.

즉, class template를 사용하면 하나의 자료 구조체를 여러 개의 타입에 대해 사용할 수 있다.

 

The formal parameter appears in the class template definition, and the actual parameter appears in the client code.

 

Both are enclosed(둘러싸인) in pointed brackets(뾰족한 괄호) < >.

 

Stack Definition using Class Templates

▶ Stack Definition

 

push() and pop() using Class Templates

▶ push() and pop()

 

Client Code using Class Template

▶ int Stack

▶ char Stack

▶ Stacks with Various Types

How to Use Class Template

The actual parameter to the template is a data type.

 

Any type can be used, either built-in or user-defined (struct or class). 

▶ User-defined (Custom) Class

 

When creating a Class Template:

• Have .h include .cpp file (NOT separate files)

일반적인 클래스에서는 .h 파일에 클래스 선언을, .cpp 파일에 함수 구현을 넣는다.

 

하지만 클래스 템플릿은 컴파일 타임에 인스턴스화되어야 하므로, 템플릿의 구현 부분을 .h 파일에 포함시키거나, .cpp 파일을 .h 파일 안에 포함해야 한다. 이렇게 하면 모든 컴파일 단계에서 템플릿의 정의와 구현에 접근할 수 있어, 링크 오류를 피하고, 템플릿이 올바르게 인스턴스화된다.

• 인스턴스화: 템플릿을 특정 타입에 대해 실제 코드로 변환하는 과정이다.
• 링크 오류: 필요한 함수나 변수 정의를 찾지 못해 발생하는 오류이다.

▶ Implementation

Class Templates allow you to have data type-independent ans flexible codes.

 

Pointer

Memory Allocation

▶ Memory Allocation of Array

• char msg[8];
• msg is a name of array and it means the base address.

▶ Memory Allocation of Variables

• When a variable is declared, enough memory space to hold a value is allocated at an unused memory space.

Obtaining Memory Addresses

▶ The address of a non-array variable can be obtained using "&".

Pointer Variable

A pointer variable is a variable whose value is the address of a location in memory.

즉, 포인트 자체도 int, float형의 변수들처럼 일종의 변수이다. (데이터 타입: 주소값 -> 주소를 보관하는 변수)

int * ptr; // ptr will hold the address of an int
char * q; // q will hold the address of a char

▶ To declare a pointer variable, you must specify the type of value that the pointer will point to.

• 포인터가 가리키는 데이터의 타입을 특정해야, 해당 데이터의 크기를  바탕으로 값을 제대로 읽어올 수 있다.

▶ Dereference Operator * - 1

• Because ptr holds the address of x, we say that "ptr points to x".
• The value pointed by ptr is denoted by *ptr.

포인터도 일종의 변수이기에 가르키는 값과 전혀 다른 주소로 메모리 할당이 이루어진다.

▶ Dereference Operator * - 2

 

ch_ptr2가 ch_ptr1을 가리키는 게 아니라 ch_ptr1가 가리키는 변수를 가리키는 것이니 주의하여야 한다.

NULL Pointer (nullptr)

• A pointer constant 0 is called the "NULL pointer".
• But NULL is NOT memory address 0.
• It means "a pointer points to nothing".

▶ It is an error to dereference a pointer whose value is NULL.

 

NULL vs. nullptr

• NULL pointer is the constant of 0.
  • #define NULL 0
• It is ambiguous for the compiler when it is used within function overloading.
  • 오버로딩은 같은 이름의 함수나 연산자를 여러 번 정의하되, 매개변수의 타입이나 개수로 구분하는 것이고, 오버라이딩은 상속받은 클래스에서 부모 클래스의 메서드를 재정의하여 사용하는 것임
• nullptr was introduced in C++11.

▶ NULL vs. nullptr

• NULL은 포인터를 위한 목적으로 만들어졌지만, 0으로 define 되어 있기에 int로 인식한다.

이를 해결하기 위해 아무것도 가리키지 않는 포인터 nullptr가 생겼는데,

nullptr은 NULL과 역할이나 목적은 똑같지만, 정수로 선언되는 NULL과는 달리 nullptr은 포인터로 처리된다.

Memory Allocation Types

Process Memory Map

▶ Process Memory Map

• 프로그램이 실행(프로세스)되어 메모리 공간에 로드가 되는 과정에서 만들어지는 구조로, 각 프로세스별로 존재하며,  이는 실제 메모리가 사용되는 모양이라고 볼 수 있다.

▶ CODE (TEXT) Segment(구역, 영역)

 

CODE segment contains executable codes of the program.

이러한 CODE segement는 새로 컴파일하여 새로운 프로그램을 만들기 전까지는 유지되어야 하기에, 크기 자체는 고정되어 있다.

 

CODE뿐만 아니라 프로그램에서 사용되는 모든 변수들은 기본적으로 메모리 할당이 이루어진다.

What about variables?

Automatic Allocation

▶ Automatic Allocation

• Function Call Order: main() -> add_interface() -> add()
  • 프로그램이 실행되면 main() 함수가 가장 먼저 실행된다.
• Function Termination Order: add -> add_interface() -> main()

Stack

• Last In, First Out
• Stack에 함수가 호출될 때마다, 그 함수와 관련된 정보들을 보관(push)한다.
• Stack에서 함수가 종료될 때마다, 그 함수와 관련된 정보들은 사라진(pop)다.

함수가 호출될 때 activation record와 함께 지역 변수가 할당이 되고 함수가 끝나면 지역 변수가 pop되어 사라진다.

-> 메모리의 효율적 관리

 

이렇게 함수가 호출될 때마다 자동적으로 할당이 되는 방식이기 때문에 자동 할당(automatic allocation)이라고 부른다.

 

Activation Record: 함수 실행에 필요한 정보를 저장하는 스택 프레임

• argv: argument value
• argc: argument count
• Return Address: 함수가 끝났을 때 돌아가야 하는 원래 위치로, 함수의 반환 후 실행 흐름을 제어하는 데 사용
• Previous SFP: 이전 함수의 Stack Frame Point를 가리키며, 스택의 상태를 복구하는 데 사용
• Local Variables: 함수 내에서 만들어지는 변수로, 함수 호출 시 할당되고, 함수 종료 시(함수가 pop되면) 해제(사라짐)

Dynamic Allocation

▶ codes 1

 

Codes compilable?

• NO (but for some cases)

※ 원칙적, 기본적으로는 위 코드는 컴파일이 안 돼야 정상인데, 특이하게 어떤 컴파일러들은 굉장히 관대하여 개발자의 의도를 파악하여 해주는 컴파일러들도 있다.

 

Why?

• Size of local variables must be determined at compile time.

※ array도 일종의 지역 변수이다.

 

※ 빌드 과정: 소스 코드 작성 -> 컴파일 -> 링킹 -> 실행 (소스 코드가 실행 가능한 프로그램으로 변환되는 일련의 과정)

▶ codes 2

 

"new" instruction can help!

• new: 프로그램이 동작(실행, runtime)하고 있는 도중에 할당을 해달라는 명령어이다.
• new instruction을 사용하면 동적인 크기를 갖는 array를 만드는 것이 가능하다.

It dynamically allocates memory during the runtime.

▶ Allocation / Deallocation (HEAP)

 

The memory segment used for dynamic allocation is HEAP.

HEAP is independent of STACK. (두 공간은 분리되어 있어, 영향 미치지 않음)

Even after the function termination, these variables are kept alive.

 

Dynamically allocated memory must be explicitly deallocated.

• 동적 메모리 할당과 동적 메모리 해제는 실행 시간에 이루어진다. (함수가 pop되어도 해제 안 됨)

"delete (or free)" instruction can be used.

If not?

• 메모리 누수가 발생할 수 있다.

※ STACK, HEAP은 화살표가 있지만 나머지는 없다. 그 이유는 STACK, HEAP은 모두 프로그램이 실행되는 과정에서 사이즈가 바뀔 수 있기 때문이다. STACK은 함수 호출과 반환(push와 pop)에 따라 자동으로 크기가 변하고, HEAP은 동적으로 메모리 할당 및 해제가 이루어지기 때문에 크기가 변경된다. 

▶ Dynamic Allocation

 

동적으로 할당된 공간을 가리키는 temp_array 포인터가 사라지면, 더이상 접근이 불가능하다. (사용하지 못하고 공간만 차지)

 

※ 포인터도 일종의 변수이다.

 

※ 자바나 파이썬과 같은 언어는 Garbage Collector를 통해 garbage를 알아서 수거한다. 반면, C나 C++과 같은 언어에서는 메모리 해제를 명시적으로 처리해야 하며, 만약 해제를 하지 않으면 메모리 누수가 발생하여 프로그램 종료 전까지 계속 메모리를 차지하게 된다. 이때 메모리 누수가 점점 늘어나면 어느 순간 프로세스가 죽게 되며, 심하면 컴퓨터 자체가 crush가 될 수 있기에 메모리 누수가 발생하지 않도록 잘 관리해야 한다.

How to prevent garbage?

 

▶ 1. "delete" allocated spaces if it is not used anymore. (더이상 안 쓸 때)

▶ 2-1. Keep the pointer (or address of allocated space) if necessary. (계속 쓸 거 같을 때)

• using return (void형 -> int형 함수)

동적 할당된 공간을 가리키고 있는 포인터가 사라지게 되면서 메모리 누수가 발생하는 것이기에,

이 포인터를 사라지지 않도록 만들어주면 메모리 누수가 발생하지 않는다.

• return 방식을 사용해 함수가 종료되더라도 동적 할당된 공간에 대한 포지션을 잃어버리지 않도록 한다.

▶ 2-2. Keep the pointer (or address of allocated space) if necessary.

• Call by reference

parameter 자체를 call by referece 방식으로 받으면 된다.

 

 

 

int* pt vs int*& pt

1. int* pt

• 포인터의 값을 복사해서 함수에 전달한다.
• 함수 내에서 포인터 pt가 가리키는 대상(e.g., 배열의 첫 번째 요소)은 변경할 수 있지만, 포인터 자체(pt가 가리키는 메모리 주소)는 변경할 수 없다.

void func(int* pt) {
    pt[0] = 10;  // 배열의 첫 번째 값을 변경
    pt = nullptr;  // 포인터 자체를 변경해도 함수 밖에는 영향을 미치지 않음
}

int arr[] = {1, 2, 3};
func(arr);

▶ pt[0] = 10은 배열의 첫 번째 값을 변경하지만, pt = nullptr은 함수 밖의 arr에는 영향을 미치지 않음

 

2. int*& pt

• 포인터에 대한 참조를 함수에 전달한다.
• 포인터 자체를 참조로 전달하므로, 함수 내에서 포인터가 가리키는 메모리 주소를 변경할 수 있다.

void func(int*& pt) {
    pt[0] = 10;  // 배열의 첫 번째 값을 변경
    pt = nullptr;  // 포인터 자체를 변경하면, 함수 밖에서도 `arr`가 nullptr로 바뀐다.
}

int arr[] = {1, 2, 3};
func(arr);

▶ pt = nullptr이 함수 밖의 arr에도 영향을 미쳐서, 함수가 끝난 후 arr는 nullptr로 변경됨

Static Allocation

▶ Static Allocation

 

static/global variables

• static variable: 함수 내에서만 접근 가능하지만, 값을 함수 호출 간에 유지하는 변수이다.
• global variable: 어떤 함수에도 속하지 않은 변수로, 어느 함수에서나 접근이 가능하다.

-> 프로그램이 진행되는 내내 유지가 되어야 한다.

 

The size of the DATA segment cannot change after compilation (fixed-size, CODE (TEXT) either).

 

If you declare too many global/static variables,

your program will become too large regardless of whether you use them or not.

 

※ 지역 변수는 return도 해주어야 하고, parameter로 넘겨주기도 해야 하는데 global 변수의 경우 parameter, return 없이 그냥 가져다가 쓰면 되기에 굉장히 편하다. 하지만 프로세스가 가지는 메모리 자체가 굉장히 커지게 되기 때문에 static, global 변수는 너무 많이 사용하면 안 된다.

Memory Allocation Comparison

▶ Automatic vs Dynamic vs Static Allocation

---

참고자료

https://computer-science-student.tistory.com/156

[c/c++] 연산자 우선순위(Operator Priority)