[Data Structure] Stack

스택 (Stack)

•  먼저 들어온 데이터가 나중에 나가는 LIFO(Last-In First-Out)구조
• 스택의 구현도 여러 형태로 가능하다. (리스트, 배열, 템플릿 등등)

 

Stack 구조

 

큐와 마찬가지로 세 가지 형태로 구현을 해봤다.

 

1. 연결 리스트를 이용한 스택

 

데이터 구조

struct Stack
{
	int iData;
	Stack* next;
};

함수

• Push

bool CStack::Push(int iData)
{
	Stack* newData;

	newData = (Stack*)malloc(sizeof(Stack));
	if (NULL == newData)
		return false;
	
	newData->iData = iData;

	if (NULL == m_Top)
	{
		m_Top = m_Bottom = newData;
	}
	else
	{
		newData->next = m_Top;
		m_Top = newData;
	}
	
	m_iStackSize++;

	return true;
}

• Pop

int CStack::Pop()
{
	Stack* popData;
	int iData;
	
	if (m_Top == m_Bottom)
		return -1;

	popData = (Stack*)malloc(sizeof(Stack));
	if (NULL == popData)
		return -1;

	iData = m_Top->iData;

	popData = m_Top;
	m_Top = m_Top->next;
	free(popData);
	popData = NULL;

	m_iStackSize--;

	return iData;
}

• IsEmpty

bool CStack::IsEmpty()
{
	if (m_Bottom == m_Top)
		return true;
	else
		return false;
}

 

2. 템플릿 형식의 스택

• 역시, 리스트로 구현한 것과 크게 다르지 않다.

#pragma once

#include <stdio.h>
#include <string.h>

template<typename T>
struct Stack
{
	T data;
	Stack<T> *next;
};

template<typename T>
class CStackT
{
public:
	CStackT(): m_Top(NULL), m_Bottom(NULL), m_iStackSize(0) {};
	~CStackT() {};

public:
	bool PushT(T _data)
	{
		Stack<T> *newData;

		newData = (Stack<T>*)malloc(sizeof(Stack<T>));
		if (NULL == newData)
			return false;

		newData->data = _data;

		if (NULL == m_Top)
		{
			m_Top = m_Bottom = newData;
		}
		else
		{
			newData->next = m_Top;
			m_Top = newData;
		}

		m_iStackSize++;

		return true;
	}
	T Pop()
	{
		Stack<T> *popData;
		T _data;
		if (IsEmpty())
			return NULL;

		popData = (Stack<T>*)malloc(sizeof(Stack<T>));
		if (NULL == popData)
			return false;

		_data = m_Top->data;

		popData = m_Top;
		m_Top = m_Top->next;
		free(popData);
		popData = NULL;

		m_iStackSize--;

		return _data;
	}

	bool IsEmpty()
	{
		if (m_Bottom == m_Top)
			return true;
		else
			return false;
	}

private:
	Stack<T> *m_Top;
	Stack<T> *m_Bottom;
	int m_iStackSize;
};

3. 배열을 이용한 스택

• 배열을 이용하여 구현 할 경우, 코드 길이도 줄어들고, 속도도 빨라진다. 
• 크기 제약이 있다는 것이 단점이다.

함수

• Push

bool CStackA::Push(int iData)
{
	if (MAX_STACK_SIZE == m_Top + 1)
		return false;

	if (0 == m_Top)
	{
		m_Stack[m_Top] = iData;
	}
	else
	{
		m_Top++;
		m_Stack[m_Top] = iData;
	}
	
	return true;
}

• Pop

int CStackA::Pop()
{
	int iData;

	if (IsEmpty())
		return -1;
	
	iData = m_Stack[m_Top];
	m_Top--;

	return iData;
}

• IsEmpty

bool CStackA::IsEmpty()
{
	if (0 == m_Top)
		return true;
	else
		return false;
}