Stack 막 구현해보기

https://cplusplus.com/reference/stack/stack/

https://cplusplus.com/reference/stack/stack/

 

기능>

1. 생성자 : 기본 생성자만 추가 

2. empty() : 현재 스택이 비어있는지 체크하여 Bool 타입 반환

3. size() : 현재 스택에 저장된 데이터의 갯수 Integer 타입 반환

4. top() : 가장 최근에 넣은 데이터 반환 (수정 가능)

5. push() : 스택에 데이터 추가

6. pop() : 스택에서 가장 최근 추가한 데이터 삭제

7. swap() : 서로 다른 스택끼리 저장된 데이터 관리 자료구조 교환 (길이가 달라도 상관 없음)

 

 

스택 컨테이너의 멤버 함수를 직접 구현해보자.

01) 데이터를 배열로 관리

 

[StackByArray.h 소스코드]

#pragma once

template <class T>
class StackByArray
{
public:
	StackByArray()
	{
		length = 0;
		capacity = 2;
		pArr = new T[capacity];
	}
	~StackByArray()
	{
		delete[] pArr;
		pArr = nullptr;
	}

public:
	bool empty()
	{
		return length == 0;
	}
	T& top()
	{
		if (length == 0)
		{
			printErrMsg("Stack empty!");	
			pArr[length] = -1;
		}
		return pArr[length];
	}
	int size()
	{
		return length;
	}
	void push(const T value)
	{
		if (length == capacity-1)
		{
			T* pNewArr = new T[capacity * 2];
			for (int i = 1; i < capacity; ++i)
			{
				pNewArr[i] = pArr[i];
			}

			delete pArr;
			pArr = pNewArr;
			capacity *= 2;
		}

		pArr[++length] = value;
		return;
	}
	void pop()
	{
		if (length == 0)
		{
			printErrMsg("Stack empty!");
		}
		else
		{
			--length;
		}
		return;
	}
	void emplace(const T value)
	{
		if (length == capacity - 1)
		{
			T* pNewArr = new T[capacity * 2];
			for (int i = 1; i < capacity; ++i)
			{
				pNewArr[i] = pArr[i];
			}

			delete[] pArr;
			pArr = pNewArr;
			capacity *= 2;
		}

		pArr[++length] = value;
		return;
	}
	void swap(StackByArray<T>& target)
	{
		T* tmp = pArr;
		int tmpLength = length;
		int tmpCapacity = capacity;

		pArr = target.pArr;
		length = target.length;
		capacity = target.capacity;

		target.pArr = tmp;
		target.length = tmpLength;
		target.capacity = tmpCapacity;
		return;
	}
	void printErrMsg(const char* msg)
	{
		std::cout << "ERROR: " << msg << '\n';
		return;
	}

private:
	T* pArr;
	int length;
	int capacity;
};

 

02) 데이터를 더블 링크드 리스트로 관리

 

[StackByDoubleLinkedList.h 소스코드]

#pragma once

#include <iostream>

template <typename T>
struct Node
{
	T	        value;
	Node<T>*	pPrev;
	Node<T>*	pNext;
};

template <class T>
class StackByDoubleLinkedList
{
public:
	StackByDoubleLinkedList()
	{
		pHeader = new Node<T>();
		pTail = new Node<T>();

		pHeader->pNext = pTail;
		pHeader->pPrev = nullptr;

		pTail->pNext = nullptr;
		pTail->pPrev = pHeader;

		length = 0;
	}
	~StackByDoubleLinkedList()
	{
		Node<T>* pNode = pHeader;
		while (pNode != nullptr)
		{
			Node<T>* delNode = pNode;
			pNode = pNode->pNext;
			delete delNode;
		}
	}

public:
	bool empty()
	{
		return length == 0;
	}
	T& top()
	{
		Node<T>* top = pTail->pPrev;
		if (top == nullptr)
		{
			printErrMsg("Stack empty!");
			return pTail->value;
		}
		else
		{
			return top->value;
		}
	}
	int size()
	{
		return length;
	}
	void push(const T value)
	{
		Node<T>* top = pTail->pPrev;
		Node<T>* newTop = new Node<T>();
		newTop->value = value;

		top->pNext = newTop;
		newTop->pPrev = top;

		newTop->pNext = pTail;
		pTail->pPrev = newTop;

		++length;
		return;
	}
	void pop()
	{
		if (length == 0)
		{
			printErrMsg("Stack empty!");
		}
		else
		{
			Node<T>* oldTop = pTail->pPrev;
			Node<T>* newTop = oldTop->pPrev;
			newTop->pNext = pTail;
			pTail->pPrev = newTop;
			delete oldTop;

			--length;
		}

		return;
	}
	void emplace(const T value)
	{
		Node<T>* top = pTail->pPrev;
		Node<T>* newTop = new Node<T>();
		newTop->value = value;

		top->pNext = newTop;
		newTop->pPrev = top;

		newTop->pNext = pTail;
		pTail->pPrev = newTop;

		++length;
		return;
	}
	void swap(const StackByDoubleLinkedList<T>& target)
	{
		Node<T>* tmp;
		
		Node<T>* h1 = this->pHeader;
		Node<T>* h2 = target.pHeader;

		tmp = h1->pNext;
		h1->pNext = h2->pNext;
		h2->pNext = tmp;
		h1->pNext->pPrev = h2;
		h2->pNext->pPrev = h1;

		Node<T>* t1 = this->pTail;
		Node<T>* t2 = target.pTail;

		tmp = t1->pPrev;
		t1->pPrev = t2->pPrev;
		t2->pPrev = tmp;
		t1->pPrev->pNext = t2;
		t2->pPrev->pNext = t1;

		return;
	}

	void printErrMsg(const char* msg)
	{
		std::cout << "Error: " << msg << '\n';
		return;
	}



private:
	Node<T>* pHeader;
	Node<T>* pTail;
	int length;
};

 

[Main.cpp 소스코드]

#include "StackByDoubleLinkedList.h"
#include "StackByArray.h"


int main(int argc, char* argv[])
{
	StackByArray<int> mystack1, mystack2;
	mystack1.push(10);
	mystack1.push(20);
	mystack1.push(30);
	mystack1.push(40);
	mystack1.push(50);

	std::cout << "stack size: " << mystack1.size() << '\n';
	std::cout << "stack top: " << mystack1.top() << '\n';

	mystack1.top() = 99999;
	std::cout << "mystack1 top: " << mystack1.top() << '\n';

	mystack2.emplace(100);
	mystack2.emplace(200);
	mystack2.emplace(300);
	mystack2.emplace(400);
	mystack2.emplace(500);
	
	std::cout << "stack size: " << mystack2.size() << '\n';
	std::cout << "mystack2 top: " << mystack2.top() << '\n';

	// swap
	mystack1.swap(mystack2);
	std::cout << "swap>mystack1 top: " << mystack1.top() << '\n';
	std::cout << "swap>mystack2 top: " << mystack2.top() << '\n';

	return 0;
}

 

 

[실행화면]

 

[개선점]

1) emplace()와 push() 함수의 기능이 동일하나 문서를 참조해보면 다르다. 

2) stack 컨테이너의 문서와 소스코드를 보면 기본 컨테이너라는 개념이 있고,

컨테이너의 기본적인 기능을 제공하며, 확장에 용이하게 설계되어 있다.

위 사항에 따라 기본 컨테이너를 추가하고 

템플릿 프로그래밍을 더 잘 활용하면, 좀더 유연한 스택 자료구조를 구현해 볼 수 있다.