스택(Stack) - c++ : 스택 리스트, 스택 동적 배열, 스택 정적 배열 구현

▶️ 스택

 

• 선입후출, 후입선출 방식의 자료구조입니다.
  • 처음 들어온 요소가 맨 마지막에 나가고, 맨 마지막에 들어온 요소가 맨 처음 나가는 방식입니다.

 

• 선형적인 자료구조 입니다.

 

• 배열 또는 리스트로 구현해도 무리가 없습니다.
  • 사이즈를 알때는 정적으로 사용
  • 사이즈를 모를때(런타임에 결정될 경우) 동적으로 사이즈를 결정하는것이 효율적입니다. 

 

• 길찾기 등에서 자주 사용합니다. 

 

 

 

 

▶️ 스택을 리스트로 구현한 예제입니다.

• CStackNode의 멤버변수는
  • mData : T형 데이터
  • mNext  : 다음 노드(이전에 들어온)를 가르키는 포인터
• CStackList의 멤버변수는
  • mSize  : 노드의 총 갯수
  • mEnd  : 마지막 노드(제일 마지막에 들어온)를 가르키는 포인터

StackList.h

#pragma once
#include <assert.h>

template <typename T>
class CStackNode
{
	template <typename T>
	friend class CStackList;

public : 
	CStackNode () {}
	~CStackNode () {}

private:
	// 해당 노드의 이전에 들어온 노드를 가르키는 포인터
	CStackNode<T>*	mNext = nullptr;
    // 노드의 데이터 
	T	mData;
};

template <typename T>
class CStackList
{
public :
	CStackList () {}
    // 동적할당 되기 때문에 소멸자 호출시 모든 노드를 제거합니다.
	~CStackList () { clear (); }

private :
	// 제일 마지막에 들어온 노드를 가르키는 포인터
	CStackNode<T>*	mEnd	= nullptr;
    // 노드의 총 갯수
	int	mSize	= 0;
	
public :
	void push ( const T& data )
	{
		CStackNode<T>* node = new CStackNode<T>;
		node->mData = data;

		node->mNext = mEnd;
		mEnd = node;

		++mSize;
	}

	T pop ()
	{
		assert ( !empty () );

		CStackNode<T>* nextEnd = mEnd->mNext;
		T data = mEnd->mData;

		delete mEnd;

		mEnd = nextEnd;

		--mSize;

		return data;
	}

	bool empty () const { return mSize == 0 ; }

	int size () const { return mSize;  }

	void clear ()
	{
		while ( mEnd )
		{
			CStackNode<T>* nextEnd = mEnd->mNext;
			delete mEnd;
			mEnd = nextEnd;
		}

		mSize = 0;
	}
};

 

main.cpp

#include "CStacList";

int main ()
{
	CStackList<int> intStack;

	for (int i = 0 ; i < 10 ; ++i)
	{
		intStack.push ( i );
	}

	while (!intStack.empty ())
	{
		std::cout << intStack.pop () << std::endl;
	}
    
    return 0;
}

 

 

 

 

 

 

▶️ 동적 배열을 사용하는 스택 예제입니다.

• mCapacity  : 여유공간 갯수
• mSize  : mArray에 요소의 총 갯수
• mArray  : 요소를 가르키는 포인터 배열 

CStackDynamicArray.h

#pragma once
#include <assert.h>

template <typename T>
class CStackDynamicArray
{
public:
	CStackDynamicArray() {}
	~CStackDynamicArray()
	{
		if (mArray)
			delete[] mArray;
	}

private:
	T*	mArray		= nullptr;
	int mSize		= 0;
	int mCapacity	= 0;

public:
	void push( const T& data )
	{
		// 첫 사용
		if ( mCapacity == 0 )
			ReAlloc( 1 );

		// 용량초과 
		else if ( mCapacity == mSize )
			ReAlloc( mCapacity * 2 );

		mArray[mSize] = data;
		++mSize;
	}

	T pop()
	{
		assert( !empty() );

		return mArray[--mSize];
	}

	bool empty() const { return mSize == 0; }

	bool capacity(){ return mCapacity; }

	bool size() const { return mSize; }

	bool clear() const { mSize = 0; }

	void ReAlloc(int newCapacity)
	{
		mCapacity = newCapacity;

		T* array = new T[newCapacity];
		
		if ( nullptr != mArray )
		{
			memcpy( array, mArray, sizeof( T ) * mSize );

			delete[] mArray;
		}

		mArray = array;
	}
};

 

main.cpp

#include "CStackDynamicArray";

int main ()
{
	CStackDynamicArray<int> intStack;

	for (int i = 0 ; i < 10 ; ++i)
	{
		intStack.push ( i );
	}

	while (!intStack.empty ())
	{
		std::cout << intStack.pop () << std::endl;
	}
    
    return 0;
}

 

 

 

▶️ 정적 배열을 사용하는 스택 예제 입니다.

• mSize  : mArray에 저장된 요소의 총 갯수
• mArray  : 요소를 저장한 배열 
• Count : 배열의 크기 (기본값은 100이며, CStackStaticArray 선언시 결정됩니다)

stack.h

// stack.h
#pragma once
#include <assert.h>

template <typename T, int Count = 100>
class CStackStaticArray
{
public :
	CStackStaticArray() {}
	~CStackStaticArray() {}

private: 
	T	mArray[Count]	= {};
	int mSize			= 0;

public : 
	void push( const T& data )
	{
		assert( mSize != Count );

		mArray[mSize] = data;
		++mSize;
	}

	T pop()
	{
		assert( mSize >= 0 );

		--mSize;
		return mArray[mSize];
	}

	bool empty() const { return mSize == 0; }

	bool size() const { return mSize; }

	bool clear() const { mSize = 0; }
};

main.cpp

#include <iostream>
#include "Stack.h"

int main()
{
	// 미리 배열의 공간 크기를 설정 
	CStackStaticArray<int, 200> sStack;
	sStack.push( 1 );
	sStack.push( 3 );
	sStack.push( 5 );

	while ( !sStack.empty() )
	{
		std::cout << "pop : " << sStack.pop() << std::endl;
	}

	return 0;
}