DS-L04

• 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 : 스택이 빈 상태를 만든다.

• 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 : 큐가 비어있는 상태로 만든다.

#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 배열의 선언

1. char str1[10] = {‘a’, ‘b’, …};
2. char str2[10] = “abcdefg”;
3. char* str3 = “abcdefg”;

• 1, 2는 서로 같고, 3번의 경우에는 1, 2번과 다른다.
• 선언한 이후 str2[0] = “f”; 를 하면 오류가 나지 않지만 str3[0] = “f”; 하면 오류가 난다.
• 3번의 포인터의 경우 abcdefg를 하나의 데이터로 인식하고, 데이터에 대해 read only 권한을 갖는다.
• 때문에 출력 자체는 문제가 없지만 문자를 변경하려는 경우 오류가 발생한다.

참고문헌

연결문서