- toc {:toc}
Stack
-
Stack at the logical level
-
Stack : 순서가 있는 동일한 타입의 요소를 갖는다. 요소의 추가와 제거를 하나의 입구만으로 수행한다.
-
스택은 LIFO(Last In First Out)구조이다. ex) 뒤로가기, 되돌리기기
-
Stack ADT Operations
- Transformers
- Push : 스택이 full이면 오류를 발생시킨다. 그렇지 않으면 새로운 요소를 top에 추가한다.
- Pop : 스택이 empty면 오류를 발생시킨다. 그렇지 않으면 top의 요소를 제거한다.
- Observers
- IsEmpty : 스택이 현재 비었는지를 확인한다.
- IsFull : 스택이 현재 꽉 차있는지를 확인한다.
- Top : 스택이 empty면 오류를 발생시킨다. 그렇지 않으면 top의 요소를 복사해 반환한다.
- Iterator
- MakeEmpty : 스택이 빈 상태를 만든다.
- Transformers
-
Class templete
-
템플릿은 타입 파라미터를 사용하여 여러 버전의 클래스 타입을 만들 수 있도록 만들어준다.
-
템플릿에 대한 실제 파라미터는 데이터 타입이다. Built-in 또는 user-defined 이든 사용 가능하다.
#include "ItemType.h"
templete<class ItemType>
class StackType{
public:
StackType();
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType item);
void Pop(ItemType& item);
ItemType Top();
private:
int top;
ItemType items[MAX_ITEMS];
}Queue
-
Queue at the logical level
-
Queue : 큐는 순서가 있는 동일한 요소를 저장하는 구조이다. 한 쪽 끝(뒤)에서 새로운 요소가 추가되고, 한 쪽 끝(앞)에서 새로운 요소가 제거된다.
-
큐는 FIFO(first in first out) 구조를 갖는다. ex) 버퍼
-
Queue ADT Operations
- Transformers
- Enqueue : 새로운 요소를 큐의 뒤에 추가한다.
- Dequeue : 큐의 앞에 있는 요소를 제거하고 해당 요소를 반환한다.
- Observers
- IsEmpty : 큐가 현재 비었는지를 결정한다.
- IsFull : 큐가 현재 가득 차 있는지를 결정한다.
- Iterator
- MakeEmpty : 큐가 비어있는 상태로 만든다.
- Transformers
#include "ItemType.h"
templete<class ItemType>
class QueType{
public:
QueType();
QueType(int max);
~QueType();
bool IsEmpty() const;
bool IsFull() const;
void Enqueue(ItemType item);
void Dequeue(ItemType& item);
private:
int front;
int rear;
int maxQue;
ItemType* items; // 동적 배열 할당, 위 스택도 동적 배열 할당 해도 무관하다.
}Pointer Variable
-
Pointer Variable : 메모리에서 값이 변수의 주소인 변수이다.
-
포인터 변수를 선언하기 위해 포인터가 가리키는 값의 자료형, 타입을 명시해야 한다.
- ex) int* ptr;
-
Address operator(&) : 주소 연산자는 해당 값이 메모리 상에서 위치한 주소를 반환한다.
int x = 10; int* ptr = &x; cout << &ptr; // print : 10 -
NULL Pointer : null 값을 저장한 포인터. C++에서 null로 지정하려면 0으로 초기화하거나 할당하면 된다.
-
포인터는 인스턴스화 될 때 값이 할당되지 않으면 포인터는 기본적으로 어떤 가비지 주소를 가리킨다.
-
Allocation of memory
- Static Allocation - 정적 할당은 컴파일 시간에 메모리 공간을 점유한다.
- Dynamic Allocation - 동적 할당은 new 연산자를 사용함으로써 런타임에 메모리 공간을 점유한다.
-
프로그램 데이터의 일생의 3가지 종류
-
Static data : 메모리 할당은 프로그램의 실행 동안 존재한다. 프로그램 종료 전까지는 없어지지 않는다. → 질문 : static data는 어디에 저장되나?, 해제는 언제되는가?, 전역변수 취급을 받는가?
-
Automatic data : 함수 시작 단계에서 자동적으로 만들어지고 반환 시에 종료된다.
-
Dynamic data : new, delete 연산자를 사용하여 명시적으로 할당, 해제한다.
동적 할당
- new operator : 만약 힙에 빈 공간을 이용 가능하다면 메모리가 요청된 객체나 배열을 할당하고 포인터를 반환한다.
- 그렇지 않으면 null pointer 0을 반환한다.
- 동적으로 할당된 객체는 delete 연산자로 해제할 때까지 존재한다.
char* ptr;
ptr = new char;
*ptr = 'B';
delete ptr;- delete하면 ptr이 가리키는 할당된 주소가 사라지고, null값이 들어간다.
char 배열의 선언
- char str1[10] = {‘a’, ‘b’, …};
- char str2[10] = “abcdefg”;
- char* str3 = “abcdefg”;
- 1, 2는 서로 같고, 3번의 경우에는 1, 2번과 다른다.
- 선언한 이후 str2[0] = “f”; 를 하면 오류가 나지 않지만 str3[0] = “f”; 하면 오류가 난다.
- 3번의 포인터의 경우 abcdefg를 하나의 데이터로 인식하고, 데이터에 대해 read only 권한을 갖는다.
- 때문에 출력 자체는 문제가 없지만 문자를 변경하려는 경우 오류가 발생한다.