[자료구조] 스택(Stack) 개념, 동적배열로 스택 직접 구현하기 C++

1. 스택이란?

스택(stack)은 영어로 "쌓다"라는 뜻으로 그 의미가 개념과 연관이 깊다.

데이터가 아래에서 위로 쌓이는 구조로 데이터가 계속 쌓이면 밑에 있는 데이터는 깔리게 된다.

데이터를 꺼내려면 가장 위의 데이터부터 꺼내야 함

 

이런 구조를 LIFO : Last-In-First-Out (마지막에 들어간 사람이 가장 먼저 나온다)라고 한다.

대표적인 예시로 프링글스 통, 엘리베이터가 있다.

1. 프링글스를 만들 때는 아래에서부터 하나씩 차곡차고 쌓고 꺼낼 때는 가장 위에 있는 과자부터 먹어야 한다.

2. 엘리베이터에 제일 마지막에 탄사람이 가장 먼저 내린다.

대표적인 스택의 예 : 프링글스 통

2. 스택에서의 용어

자료구조에서 데이터를 넣거나 뺄 때 사용하는 용어들이 있다.

아래에서 해당 용어의 기능을 하는 함수를 구현할 것이다.

이미지 출처 : https://medium.com/@1991dharapatel

• 스택에 데이터를 넣는 것 : push
• 스택에서 데이터를 빼는 것 : pop
• 현재 스택의 맨 위에 쌓여있는 데이터를 의미 : top   <- peek라고도 부름

 

3. C++ 스택 클래스 구현

연결리스트, 배열 등으로 다양하게 구현할 수 있지만 필자는 c++ 동적배열을 사용하여 스택을 구현하겠다.

스택에 데이터가 추가될 때마다 동적배열의 크기가 1씩 늘어난다.

 

스택 클래스 메서드 설명

함수의 첫 글자를 대문자로 하는 이유는 C++ STL에서 스택라이브러리를 지원한다. 해당 STL과 함수명이 겹치지 않게 하기 위함

Stack Class 구조

stack.h로 사용할 수 있게 만들었다.

아래 형식만 보고 클래스를 직접 구현해 본다면 좋은 경험이 될 것이다.

#pragma once

#include <cassert>
#include <iostream>

template<typename T> // 모든 자료형을 쓸 수 있는 스택을 만들기 위해 템플릿 사용
class Stack
{
public:
	Stack(int capacity = 1){} //스택 클래스 생성자

	~Stack(){} //스택 클래스 소멸자

	void Resize(int new_capacity) {} //스택의 동적 배열 크기를 2배 늘려준다.

	bool IsEmpty() const {} //스택이 비었는지 알려줌

	int Size() const {} //스택의 크기

	void Print() {} //스택의 전체요소들 출력

	T& Top() const {} //현재 스택의 최상단 데이터 출력

	void Push(const T& item) {} //스택에 데이터 추가

	void Pop() {} //스택에서 데이터 빼기

protected:
	T* stack_ = nullptr; //템플릿을 자료형으로 하는 동적 배열을 만들어준다.
	int top_ = -1; //동적 배열에서 스택의 top의 인덱스 정보를 담고 있다.
    			//-1로 초기화해야 첫번째 값이 push되면서 인덱스가 0이 된다.
	int capacity_ = 0; //현재 스택의 크기를 담는다.
};

 

사용 변수 설명

top_ : 가장 마지막에 스택에 추가된 요소의 인덱스를 의미
-1로 초기화해야 첫 번째 값이 push 되면서 인덱스가 0이 된다.

 

생성자, 소멸자

스택을 생성하면 기본 크기가 1인 동적배열을 만든다.

스택 소멸 시에는 동적 배열이 삭제된다.

	Stack(int capacity = 1)
	{
		assert(capacity > 0);
		Resize(capacity);
	}

	~Stack()
	{
		if (stack_) delete[] stack_;
	}

 

Push(), Pop()

스택에 데이터를 넣거나 빼주는 함수이다.

Push(const T& item)

• top을 가리키는 인덱스를 +1 하고 증가시킨 인덱스에 추가할 값 저장
• 추가된 값에 맞게 ReSize() 함수로 스택(동적 배열)의 크기를 1 증가시킨다.

Pop

• top_을 1 줄이면 끝

	void Push(const T& item)
	{
		Resize(top_ + 1);
		stack_[++top_] = item; //top_을 하나 증가시켜 그 곳에 item을 넣음
	}
    
	void Pop()
	{
		assert(!IsEmpty()); //스택이 비었는데 접근하면 assert 발생시킴
		top_--;
	}

 

Top()

top_ 인덱스의 값을 가져오기만 하면 된다.

	T& Top() const
	{
		assert(!IsEmpty()); 
        
		return stack_[top_];
	}

 

IsEmpty(), Size()

IsEmpty() : top_ == -1이 true 라면 true 반환, false면 false 반환

Size() : 스택의 마지막 인덱스를 가리키고 있으니 크기는 마지막 인덱스 +1

	bool IsEmpty() const
	{
		return top_ == -1 
	}

	int Size() const
	{
		return top_+1;
	}

 

Resize()

매개변수로 받은 크기에 맞게 동적 배열을 새로 만들고 값을 복사해 주는 기능을 가지고 있음

1. new_capacity를 매개변수로 받고 그에 맞게 동적할당을 한다.

2. 새로 만든 동적 배열에 기존의 배열의 값을 복사

3. 기존의 동적 배열을 삭제, 새로 만든 배열을 stack_으로 new_capacity을 capacity_로 둔다.

	void Resize(int new_capacity)
	{
		T* new_stack = new T[new_capacity];
		memcpy(new_stack, stack_, sizeof(T) * Size());
		if (stack_) delete[] stack_;
		stack_ = new_stack;
		capacity_ = new_capacity;
	}

 

Print()

스택(동적배열)을 순회하며 값을 출력한다.

	void Print()
	{
		using namespace std;

		for (int i = 0; i < Size(); i++) // Size() 사용
			cout << stack_[i] << " ";
		cout << endl;
	}

 

4. 전체코드

#pragma once

#include <cassert>
#include <iostream>

template<typename T>
class Stack
{
public:
	Stack(int capacity = 1)
	{
		assert(capacity > 0);
		Resize(capacity);
	}

	~Stack()
	{
		if (stack_) delete[] stack_;
	}

	void Resize(int new_capacity)
	{
		T* new_stack = new T[new_capacity];
		memcpy(new_stack, stack_, sizeof(T) * Size());
		if (stack_) delete[] stack_;
		stack_ = new_stack;
		capacity_ = new_capacity;
	}

	bool IsEmpty() const
	{
		return top_ == -1;
	}

	int Size() const
	{
		return top_+1; 
	}

	void Print()
	{
		using namespace std;

		for (int i = 0; i < Size(); i++) 
			cout << stack_[i] << " ";
		cout << endl;
	}

	T& Top() const
	{
		assert(!IsEmpty());
		return stack_[top_];
	}

	void Push(const T& item)
	{
		Resize(top_ + 1);
		stack_[++top_] = item;
	}

	void Pop()
	{
		assert(!IsEmpty());
		top_--; 
	}

protected: // 뒤에서 상속해서 사용
	T* stack_ = nullptr;
	int top_ = -1; // 0 아님
	int capacity_ = 0;
};