스택

스택이란?

가장 마지막에 들어간 데이터가 처음으로 꺼내지는 구조를 가진 자료구조 입니다. (LIFO)
가장 처음에 들어간 데이터가 가장 마지막에 꺼내지는 구조를 가진 자료구조입니다. (FILO)

 

 

스택의 ADT

스택이란 자료구조를 구현하기 전에 해당 자료구조의 ADT를 정의할 필요가 있습니다.

1. Last in First Out(LIFO) : 마지막에 들어간 값이 첫 번째로 나오는 구조

2. 탐색, 삽입, 삭제를 구현할 것.

3. stack 최상단 데이터 값을 반환하는 함수를 구현할 것.

 

 

스택 ADT 선언

스택의 ADT를 참고하여 클래스로 선언 해보겠습니다. 

 

template <typename T>
class CustomStack
{
public:
	CustomStack()
		: list(new T[10])
		, pointer(-1)
		, arraySize(10)
	{

	}

private:
	bool isFull();
	void initializeArray();

public:
	// 1. 탐색
	bool search(T data);

	// 2. 삽입
	void push(T data);

	// 3. 삭제
	void pop();

	// 4. 최상단 값 추출
	T top();

	// util 함수들
	bool empty();
	int size();

private:
	int arraySize;
	int pointer;
	T* list;

};

 

코드 분석

일단 제가 ADT에서 생각했던 부분을 위주로 선언을 해두었습니다.

위와 같이 선언된 스택은 기본적인 요소와 기능을 갖추고 있으며 구현하는 사람에 따라 요소와 기능의 선언이 달라질 수 있습니다. 위의 선언에서 요소와 기능을 중점으로 간단하게 설명해보겠습니다.

 

요소

1. arraySize : 스택을 배열을 이용하여 구현할 것인데 현재 배열의 최대 크기를 의미합니다.

2. ponter      : 현재 스택의 최상단 위치를 나타냅니다.

3. list            : 데이터를 담을 동적할당된 배열입니다.

 

기능

1. search : 탐색 기능입니다.

2. push : 삽입 기능입니다.

3. pop : 삭제 기능입니다.

4. top : 최상단 값을 추출합니다.