What is Stack?
스택은 동종의 아이템들(자료형이 같은 것들)만의 그룹이고 Stack의 맨 위에 아이템을 추가하고 삭제한다.
이러한 특성을 LIFO(Last in First Out)이라 부른다. ex). Undo, Back Browser
Stack
-
Logical level
-
Constructor
- Class Name
-
Transformer
-
Push(value)
-
Pop( )
-
-
Observer
-
size( )
-
isFull( )
-
isEmpty( )
-
-
Stack의 동작설명
-
Stack이 비어있는 상태는 어떻게 되는 것일까?
- Stack의 맨 위의 값(top)이 -1로 설정된다.
-
size( )
-
size는 맨위의 값(top)에 1을 더하여 return해준다.
-
아무것도 없을 때, top = -1 --> -1 + 1 = 0 --> size의 반환 값 : 0
-
-
isFull( )
-
Stack에서 설정한 Max_Size값에서 -1을 뺀 값이 현재 top과 동일하며 True이다.
-
아닐 경우는 False를 반환한다.
-
왜 Max_Size에서 1을 빼는가? --> 첫 번째의 값의 인덱스가 0이기 때문이다.
-
-
isEmpty( )
- Stack의 top의 값이 -1이면 True를 아니면 False를 반환한다.
-
push( )
-
Unsorted list의 appendItem가 유사한 동작방식이다.
-
isFull일 경우 아무것도 반환하지 않는다.
-
만약 isFull이 아니라면, top의 값에 1을 더한 후, data[top]에 추가하고자 하는 value를 붙인다.
-
시간복잡도 : O(1)
-
-
pop( )
-
isEmpty일 경우 아무것도 -1을 반환한다.
-
isEmpty가 아닐 경우 반환하고자 하는 맨 꼭대기의 값을 변수에 저장한다.
-
이후 top의 값에서 1을 뺀 후, 변수를 반환한다.
-
시간복잡도 : O(1)
-
Big - O 시간복잡도 (Stack)
| Operation | Time Complexitiy |
|---|---|
| size( ) | O( 1 ) |
| isFull( ) / isEmpty( ) | O( 1 ) |
| push(ItemType value ) | O( 1 ) |
| pop( ) | O( 1 ) |
Class Template
Stack은 한 종류의 자료형만을 저장할 수 있는 구조(homogeneous)이다.
하지만 여러 형태의 자료형(int, char, bool)을 저장하고 싶다면 어떻게 해야할까?
이때 도와주는 것이 Class Template이다.
-
Class Template
-
Type Parameters를 활용하여, 다양한 버전의 class type를 생성하도록 해준다.
-
형식적인 parameter는 class template의 정의에서, 실제 parameter는 client code에서 나타난다.
-
둘다 < >로 둘러 쌓여있다는 것을 기억해야한다.
-
-
Class Template 사용법
-
Template의 실제 parameter가 data type이다.
-
어떤 타입을 사용한든, 내재된거나, 유저가 정의한 것들 중 하나여야한다.
-
Class Template를 제작할때, 반드시 헤더 파일을 포함해야한다.
-
Pointer
-
메모리의 할당 방법
-
변수가 선언 될때, 값이 할당될 수 있도록 충분한 메모리 공간이 마련된다.
-
int : 4byte / float : 4byte / char : 1byte
-
-
메모리의 주소(Memory Addresses)
- array가 아닌 변수의 주소는 '&'를 통해 확인할 수 있다.
-
Pointer Variable
-
메모리에서 주소의 위치 값을 나타내는 변수이다.
-
포인터 변수를 선언하기 위해선 반드시, 값의 타입을 명시해야한다.
- int * ptr : 정수형 포인터
- char * ptr : 문자형 포인터
-
int x = 12; int * ptr = &X;
-
이 경우 x의 주소를 ptr이 그리고 ptr은 x를 가리키고 있다고 말한다.
-
ptr로 가리켜진 값은 *ptr로 표시된다.
-
-
포인터의 변수는 어떤 형태인든 크기가 8byte로 동일하다.
-
null Pointer (nullptr)
-
포인터를 표현하는 값 중에 "널을 표현한 값"이다
-
하지만 Null은 메모리 주소 0을 가리키는 것은 아니다.
-
"포인터가 아무것도 가리키지 않은 상태"를 의미한다.
-
NULL과 nullptr차이
-
C++11부터 도입된 nullptr은 포인터 타입의 널 값을 의미하며 정수 0과 구분되는 명확한 타입이다.
-
반면 NULL은 정수 0으로 정의된 매크로로, 함수 오버로딩 시 int로 취급되어 예기치 않은 오류를 유발할 수 있다.
-
이러한 NULL의 단점을 보완하고자, nullptr이 등장한다.
-
-
-
Memory Allocation
-
Process Memory Map
-
프로그램을 메모리에 적재할 때 프로세스의 요소들을 배치하는 방식.
-
스택 영역 (Stack Area)
-
스택영역으로 할당된 부분은 스택 방식으로 작동. : LIFO방식
-
메모리의 정확성을 유지하기 위해 stack 방식을 사용.
-
-
힙 영역 (Heap Area)
-
프로그램 실행 중(런타임)에 동적으로 할당되는 데이터(객체, 배열 등)를 위한 메모리 영역.
-
address를 Stack 영역에 참조 데이터 타입(Reference Data Type)으로 만들어서 그것을 reference해서 사용.
-
-
데이터 영역 (Data Area)
-
프로그램의 전역 변수(Global)와 정적(Static) 변수가 저장되는 메모리 공간.
-
BSS (Block Stated Symbol) // Data Segment (Initialized Data)이 존재.
-
-
Text(Code) 영역
- 프로그램의 실행 가능한 코드들을 포함하고 있는 영역.
-
추가 개념
-
Dynamic Allocation (동적 할당)
-
프로그램 실행 중(런타임)에 필요한 만큼의 메모리(힙 영역)를 운영체제로부터 할당받아 사용하는 기술.
-
필요한 만큼만 메모리를 사용하므로 자원을 효율적으로 관리가 가능하다.
-
하지만, 할당한 메모리는 반드시 프로그래머가 삭제해야하며, 그렇지 않을 경우 메모리 누수가 발생할 수 있다.
-
