[Data Structure] 스택

개요

• top이 가리키는 한 쪽 끝에서 Push, Pop이 일어나는 순서 리스트
• 후입선출(Last In First Out, LIFO)

스택에서 구현할 기능

• 생성자: 스택 capacity 초기화 및 스택 배열 할당
• 소멸자: 스택 배열 해제
• IsEmpty: 스택이 비어있는 지 확인
• Top: top이 가리키는 값 리턴
• Push: 꽉 찬 경우 두 배로 늘려서 데이터 옮기기
• Pop: top이 가리키는 값 추출
• Print: 스택 출력

코드

#pragma once

#include <iostream>

template <typename T>
class Stack
{
public:
	Stack(int stackCapacity);
	~Stack();
	bool IsEmpty() const;
	T& Top() const;
	void Push(const T& item);
	void Pop();
	void PrintStack();
private:
	T* stack; // 스택 배열
	int top = -1;
	int capacity; // 스택 크기
};

template <typename T>
Stack<T>::Stack(int stackCapacity)
{
	capacity = stackCapacity;
	stack = new T[capacity];
}

template <typename T>
Stack<T>::~Stack()
{
	delete stack; // 스택 삭제
}

template <typename T>
bool Stack<T>::IsEmpty() const
{
	if (top <= -1) 
		return true;
	else 
		return false;
}

template <typename T>
T& Stack<T>::Top() const
{
	if (IsEmpty())
	{
		std::cout << "Stack is empty." << std::endl;
		return NULL; // 비어있는 경우 리턴
	}

	return stack[top];
}

template <typename T>
void Stack<T>::Push(const T& item)
{
	// 배열이 가득 찬 경우 크기를 두 배 늘린 새로운 배열을 만든 후
	// 기존 배열의 값들을 복사 후 기존 배열 삭제
	if (top >= capacity-1)
	{
		T* temp = new T[capacity * 2]; // 2배 크기 배열 할당
		memcpy(temp, stack, sizeof(T) * capacity); // 메모리 복사
        capacity *= 2;
		delete stack;
		stack = temp;
	}

	top++;
	stack[top] = item;
}

template <typename T>
void Stack<T>::Pop()
{
	if (IsEmpty())
	{
		std::cout << "Stack is empty." << std::endl;
		return; // 비어있는 경우 리턴
	}

	top--;
}

template <typename T>
void Stack<T>::PrintStack()
{
	for (int i = 0; i <= top; i++)
	{
		std::cout << stack[i] << " ";
	}
	std::cout << std::endl;
}