스택(Stack)

스택이란?

스택(Stack)은 한글로 번역하면 '쌓다, '더미'이다. 말그대로 데이터를 차례차례 쌓아 놓은 형태의 구조를 뜻한다. 

 

예를 들어, 밑이 막힌 상자에 물건을 채워 넣는다고 생각해보자. 밑이 막혀있으니 위로만 물건을 집어 넣고 뺄 수 있을 것이다. 그렇기 때문에 가장 처음에 넣은 물건은 가장 나중에 뺄 수 있을 것이다. 마찬가지로 스택 구조도 이와 같은 특징을 가진다. 이러한 구조를 '후입선출(Last-In First-Out : LIFO)'이라고 한다.

 

스택은 Push()를 이용해 데이터를 차곡차곡 쌓고 Pop()을 이용하여 가장 위에 있는(Top) 데이터를 꺼낸다. 또한 편의에 따라 Peek()을 이용하여 Top에 있는 데이터를 미리 볼 수도 있다.

 

스택의 구조

---

스택의 활용

스택은 정말 많은 곳에서 사용된다. 특히 입력 순서의 역순으로 이루어져야 하는 경우가 많은 작업에 긴요하게 사용된다. 스택의 활용 분야는 다음과 같다.

 

• 문서나 그림, 수식 등의 편집(Editor)에서 되돌리기(Undo) 기능을 구현할 때 스택이 사용된다. 보통 되돌리기 기능은 수행된 명령어들 중에서 가장 최근에 수행된 것부터 순차적으로 취소해야 하기 때문이다.

• 함수 호출에서 복귀주소를 기억하는데 스택을 사용한다. 예를 들어 main()에서 a()함수가 호출되고 a()에서 다시 b()를 그리고 b()에서 c()를 호출시켰다고 하자. 이와 같은, 복잡한 함수의 호출과 반환을 위해 운영체제는 시스템 스택을 사용하는데, 함수가 호출될 때마다 활성화 레코드를 만들어 스택에 저장한다. 이 레코드에는 현재 수행되는 문장의 주소(Program Counter : PC)가 저장되는데, 함수가 끝나면 스택에서 가장 최근의 복귀 주소를 구해서 그곳으로 되돌아간다. 활성화 레코드에는 함수 호출시 매개변수와 함수 안에서 선언된 지역 변수들도 함께 저장된다.

• 문서나 소스코드에서 괄호 닫기가 정상적으로 되었는지를 검사하는 프로그램에서도 스택을 사용한다. 또한 계산기 프로그램에서 입력된 수식을 계산하는 과정에도 스택이 사용되고, 미로에서 출구를 찾기 위해서도 스택을 사용할 수 있다.

---

스택의 구현

스택의 구현 방법을 배열을 이용하는 방법과 연결 리스트를 이용하는 방법 두 가지가 존재한다.여기서는 쉽게 구현할 수 있는 배열을 사용할 것이다. 배열로 구현하였을때 단점은 최대 크기가 미리 정해져 있다는 것이다. 이러한 단점을 완화 하고자 원래 정했던 배열 크기가 Push()나 Pop()으로 넘어가거나 불필요하게 남는 공간이 있는경우 일정 크기만큼 늘리거나 줄여서 배열을 재할당(Reallocate)하도록 구현하였다.

 

구조

구조는 다음과 같다. UserInterface 클래스를 통해 Stack기능을 캡슐화하며 메뉴출력 등의 기능을 제공한다.

 

데이터

기본적으로 스택에 들어가는 Data의 내용은 다음과 같다.

// DataType.h

#pragma once

class DATA
{
public:
	DATA() {}
	DATA(int number, int size, const char* data)
		:Number(number),
		Size(size)
	{
		if (0 < size)
			Contents = new char[size];
		memset(Contents, 0, size);

		memcpy(Contents, data, strlen(data));
	}
	~DATA()
	{
		SAFE_DELETE_ARR<char*>(Contents);
	}

public:
	bool operator == (DATA& other)
	{
		return Number == other.Number;
	}
	void operator =(DATA& other)
	{
		Number = other.Number;
		Size = other.Size;

		SAFE_DELETE_ARR<char*>(Contents);

		Contents = new char[Size];
		memcpy(Contents, other.Contents, Size);
	}

public:
	int Number = 0;
	char* Contents = nullptr;
	int Size = 0;
};

Number는 식별 숫자이고, Contents는 데이터를 저장할 char의 배열을 할당할 포인터, 그리고 Size는 Contents 데이터의 크기이다. 기본적으로 Data를 만들때 이 세가지 정보를 입력받는다. 비교(==)나 대입(=)의 편의성을 위해 오퍼레이터 함수를 만들어 놓았다. 

 

매크로

할당이 많기 때문에 할당 해제 작업이 필수적이다. 그래서 할당 해제를 편하게 사용할 수 있도록 매크로 함수로 만들었다.

// Macro.h
#pragma once

template <typename T>
inline void SAFE_DELETE(T& val)
{
	if (nullptr != val)
	{
		delete val;
		val = nullptr;
	}
}

template <typename T>
inline void SAFE_DELETE_ARR(T& val)
{
	if (nullptr != val)
	{
		delete[] val;
		val = nullptr;
	}
}

 

미리 컴파일 된 헤더는 다음과 같다.

// pch.h

#ifndef PCH_H
#define PCH_H

// 여기에 미리 컴파일하려는 헤더 추가
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <stdlib.h>


#include "Macro.h"
#include "DataTypes.h"

using namespace std;

#endif //PCH_H

데이터와 매크로 헤더는 미리 컴파일하는 헤더에 #include 시켜 모든 위치에서 쓸 수 있도록 하였다.

 

UserInterface 클래스

// UserInterface.h

#pragma once
#include "ClassStack.h"

class UserInterface
{
public:
	UserInterface();
	~UserInterface();

public:
	int  PrintMenu();
	void Logic();

public:
	void Push();
	void Pop();
	void Clear();

private:
	ClassStack* Stack_ = nullptr;
};

UserInterface 클래스는 콘솔 창에 메뉴를 띄우고 스택을 동적할당하여 사용자가 원하는 기능들을 메서드 호출하는 작업을 한다. (스택의 기능과 사용을 캡슐화)

// UserInterface.cpp

#include "pch.h"
#include "UserInterface.h"
#include "ClassStack.h"

UserInterface::UserInterface()
{
	Stack_ = new ClassStack;
}

UserInterface::~UserInterface()
{
	Stack_->Clear();
	SAFE_DELETE<ClassStack*>(Stack_);
}

int UserInterface::PrintMenu()
{
	// 메뉴를 출력한다.
	cout << "=======================================" << endl;
	cout << "1.Push 2.Pop 3.Clear 4.Exit" << endl;

	// 입력에 맞는 기능을 수행한다.
	int input;
	cin >> input;
	switch (input)
	{
	case 1: Push(); break;
	case 2: Pop(); break;
	case 3: Clear(); break;
	case 4: return -1;
	default:
		cout << "잘못된 입력!" << endl;
		break;
	}

	return 0;
}

void UserInterface::Logic()
{
	// 종료할때까지 반복한다.
	while (true)
	{
		if (-1 == PrintMenu())
			break;
	}
}

void UserInterface::Push()
{
	// 필요한 데이터를 입력받고 Push한다.
	int number, size;
	cout << "식별 숫자를 입력해주세요? "; cin >> number;
	cout << "데이터의 크기를 입력해주세요? ";cin >> size;

	cout << "데이터 내용을 입력해주세요." << endl
		 << "------------------------------------------" << endl;
	
	string tmpData;
	cin >> tmpData;

	Stack_->Push(number, size, tmpData.c_str());

	cout << "------------------------------------------" << endl;
	cout << "추가 완료!" << endl;
}

void UserInterface::Pop()
{
	// 비어 있는지 확인
	if (true == Stack_->IsEmpty())
	{
		cout << "비어 있습니다!" << endl;
		return;
	}

	// 비어 있지 않다면 Pop을 하면서 Pop한 데이터를 가져온다.
	DATA val;
	Stack_->Pop(&val);

	// 데이터의 내용을 출력한다.
	cout << "식별 숫자 : " << val.Number <<
		" 데이터 크기 : " << val.Size << endl;
	printf("데이터 내용\n%s\n", val.Contents);
}

void UserInterface::Clear()
{
	// 모든 데이터를 Clear한다.
	Stack_->Clear();
	cout << "모든 데이터가 삭제되었습니다." << endl;
}

 

Stack 클래스

// ClassStack.h

#pragma once
#include "DataTypes.h"

class ClassStack
{
public:
	ClassStack() {}
	~ClassStack();

public:
	bool IsEmpty() { return (-1 == Top); }

public:
	void Push(int number, int size, const char* data);
	void Pop(DATA* OutData);
	void Clear();

private:
	void Swap(int ChangeSize);

private:
	int Top = -1;
	int Size = 0;
	DATA** Container = nullptr;
	DATA** ForSwap = nullptr;
};

Top을 이용하여 가장 최근의 추가한 데이터를 인덱스로 가리키도록 한다. Size는 스택 배열인 Container의 크기이며 ForSwap은 Container의 크기를 재할당할때 임시로 데이터를 옮겨 놓을 수 있도록 해주는 멤버변수이다. 그리고 Top이 -1인 경우는 스택이 비어 있는 것으로 IsEmpty 메서드를 이용하여 여부를 파악할 수 있다.

// ClassStack.cpp

#include "pch.h"
#include "ClassStack.h"

// 크기를 늘리거나 줄일 단위
const int UNIT = 2;

ClassStack::~ClassStack()
{
	SAFE_DELETE_ARR<DATA**>(Container);
	SAFE_DELETE_ARR<DATA**>(ForSwap);
}

void ClassStack::Push(int number, int size, const char* data)
{
	// 데이터를 추가한다.

	++Top;

	// 만약 Container가 배열로 할당되어 있지 않은 경우
	// 할당을 해준다.
	if (nullptr == Container)
	{
		Size = UNIT;
		Container = new DATA*[Size];
	}

	// 추가하기 전 배열이 꽉찬경우
	// 재할당하여 배열의 크기를 늘린다.
	if (Top == Size)
	{
		Size += UNIT;
		Swap(-UNIT);
	}
	
	// 새로운 데이터를 동적 할당하여 스택의 Top위치에 넣는다.
	DATA* NewData = new DATA(number, size, data);
	Container[Top] = NewData;
}

void ClassStack::Pop(DATA* OutData)
{
	// Top에 있는 데이터를 동적할당 해제하고
	// OutData 포인터로 역참조하여 Pop할 데이터를 받는다.

	// 만약 불필요하게 배열의 크기가 잡혀있는 경우
	// 재할당하여 배열의 크기를 줄인다.
	if ((Size - Top) > UNIT)
	{
		Size -= UNIT;
		Swap(0);
	}

	// OutData 포인터가 있는 경우
	// 데이터를 받는다.
	if(nullptr != OutData)
		*OutData = *Container[Top];

	// Pop할 데이터를 동적할당 해제한다.
	SAFE_DELETE<DATA*>(Container[Top]);
	--Top;
}

void ClassStack::Clear()
{
	// 스택이 빌때까지 Pop을 반복한다.
	while (-1 != Top)
	{
		Pop(nullptr);
	}
	// 컨테이너 배열을 동적할당 해제한다.
	SAFE_DELETE_ARR<DATA**>(Container);
}

void ClassStack::Swap(int ChangeSize)
{
	// ForSwap에 Container에 있는 모든 정보를 복사한다.
	ForSwap = new DATA*[Size];
	memcpy(ForSwap, Container, sizeof(DATA*) * (Size + ChangeSize));

	// Container를 알맞는 크기로 재할당하고 
	// ForSwap에 있는 정보를 다시 Continer에 복사한다.
	SAFE_DELETE_ARR<DATA**>(Container);
	Container = new DATA* [Size];
	memcpy(Container, ForSwap, sizeof(DATA*) * (Size + ChangeSize));

	// 다 사용한 ForSwap은 동적할당 해제시켜준다.
	SAFE_DELETE_ARR<DATA**>(ForSwap);
}

 

Main()

#include "pch.h"
#include "UserInterface.h"

int main()
{
	UserInterface ui;
	ui.Logic();
}

UserInterface 클래스에 캡슐화 해둔 덕분에 인스턴스를 만들고 Logic() 메서드만 호출해주면 된다. 

 

출력 값