[자료구조 및 알고리즘] Stack (C++)

신동욱·2025년 1월 29일

목록 보기

4/18

1. What is a Stack? 📚

책상 위에 쌓인 책 🏛️

책상 위에 책이 쌓여 있습니다. 가장 밑에 있는 책이 가장 먼저 쌓였을 겁니다. 그리고 가장 위에 있는 책이 가장 최근에 쌓은 책이겠죠? 가장 밑에 있는 책을 꺼내려면 어떻게 해야 할까요? 물론 한꺼번에 책을 들어서 꺼낼 수 있겠지만;;

책이 매우 무거워서 한 권씩만 꺼낼 수 있다고 가정해 봅시다. 그럼 가장 위에 있는 책부터 한 권씩 꺼내야만 가장 밑에 있는 책에 도달할 수 있습니다.

LIFO(Last-in First-out) 🔄

이것이 바로 스택(Stack)입니다. 스택은 가장 최근에 추가된 자료가 가장 먼저 제거됩니다. 이런 순서 규칙을 우리는 LIFO(Last-in first-out)이라고 부릅니다.

top-base 🏔️⬇️

스택은 한 쪽 끝에서만 자료의 추가와 삭제가 일어나는 순서있는(ordered) 집합입니다. 이러한 끝을 top 그리고 그 반대편을 base라고 합니다.

🔼 top : 자료를 넣고(push) 빼는(pop) 위치
🔽 base : top의 반대편 끝

스택의 특징 : 순서 뒤집기 🔁

스택은 넣은 순서와 반대로 꺼내게 되는 특징이 있습니다.

💡 실생활 예시: 웹브라우저의 뒤로가기 버튼. 방문한 페이지 URL을 스택에 쌓아두고, 뒤로가기를 누르면 top에서 하나를 팝(pop)합니다.

2. Stack ADT(Abstract Data Type) ✨

앞서 살펴본 스택의 특징으로부터, 스택이 어떤 데이터(data)와 어떤 기능(Operations)을 가져야 할지 예상할 수 있습니다.

스택은 top에서 데이터의 입출력이 일어나므로, 이 위치(top)를 기억하고 있어야 합니다. 또한 스택의 크기(size)를 저장하고 있어야 자료의 개수를 파악하는데 도움이 될 것입니다.

스택에 핵심 기능은 자료를 넣고 빼는 것입니다. 그 외에 부가적인 기능이 추가되면 Stack의 ADT가 완성됩니다.

Data 📂

top : 스택의 첫 번째 요소를 가리키는 포인터
size : 요소의 개수

Operations ⚙️

push(item) : 새로운 항목을 스택의 맨 위에 추가
pop() : 스택의 맨 위 항목을 반환하고 제거
topValue() : 맨 위 요소의 복사본을 반환
length() : 스택의 요소 개수를 반환
isEmpty() : 스택이 비어 있는지 여부를 반환
clear() : 스택을 다시 초기화

stack 추상 클래스 💻

다음과 같이 꼭 필요한 기능들만 추상 클래스로 만들어서 구현에 독립된 기능을 보장하도록 해보겠습니다.

#pragma once
template <typename T>
class Stack {
public:
	virtual ~Stack() {}
	// Reinitialize the stack.
	virtual void clear() = 0;

	// Push "it" onto the top of the stack.
	virtual bool push(T it) = 0;

	// Remove and return the element at the top of the stack.
	virtual T pop() = 0;

	// Return a copy of the top element.
	virtual T topValue() = 0;

	// Return the number of elements in the stack.
	virtual int length() = 0;

	// Tell if the stack is empty or not.
	virtual bool isEmpty() = 0;

};

3. Stack 구현 🛠️

3-1. Array-based stack 🗄️

#include <iostream>
#include "Stack.h"
using namespace std;

template <typename T>
class AStack : public Stack<T> {
public:
	T* stackArray;						// Array holding stack elements
	static const int DEFAULT_SIZE = 10; // Default size
	int maxSize;						// 할당 크기를 위해
	int top;							// top의 위치
	
	// 생성자
	AStack(int size = DEFAULT_SIZE) {
		stackArray = new T[size]; // 동적 할당
		top = 0;
		maxSize = size;
	}
	// 소멸자
	~AStack() { delete[] stackArray; }

	void clear() { top = 0; }
	bool push(T it) {
		if (top >= maxSize)
			return false;
		stackArray[top++] = it;
		return true;
	}

	T pop() {
		if (top == 0)
		{
			cout << "빈 스택입니다\n";
			return T();
		}
		return stackArray[--top];
	}

	T topValue() { return stackArray[top - 1]; }

	int length() { return top; }

	bool isEmpty() { return top == 0; }
};

3-2. Linked Stack 🔗

Linked Stack은 Single Linked List로 구현가능합니다. 데이터의 입출력이 한 쪽 끝에서만 이루어지고, 랜덤 엑세스를 하지 않기 때문입니다.

Linked Stack에서 pop()하는 과정을 살펴보겠습니다. 🏃‍♂️💨

값의 반환을 위해 top의 값을 it 변수에 복사해놓습니다.

그리고 top이 top의 next를 가리키도록 합니다. 그리고 원래 top이 가리키던 메모리 공간은 반납해버리면 되겠죠.

it을 반환하면 끝입니다.

Single Linked List의 노드를 표현할 때 썼던 Link 클래스를 그대로 사용하여 Linked Stack을 구현해 보겠습니다.

#include <iostream>
#include "Link.cpp"
#include "Stack.h"
using namespace std;

template <typename T>
class LStack : public Stack<T> {
public:
	Link<T>* top;
	int stackSize;

	//생성자
	LStack() { top = nullptr; stackSize = 0; }
	//소멸자
	~LStack() {
		// 명시적으로 delete
		while (top != nullptr) { // top이 nullptr이 될 때까지 반복
			Link<T>* tmp = top;
			top = top->next(); // 다음 노드로 이동
			delete tmp; // 현재 노드 메모리 해제
		}
	}

	void clear() {
		// 명시적으로 delete
		while (top != nullptr) {
			Link<T>* tmp = top;
			top = top->next();
			delete tmp;
		}
		stackSize = 0;
	}

	bool push(T it) {
		top = new Link<T>(it, top);
		stackSize++;
		return true;
	}

	T pop() {
		if (stackSize == 0) {
			cout << "스택이 비었음\n";
			return T();
		}
		Link<T>* tmp = top;
		T it = top->element();
		top = top->next();

		stackSize--;
		delete tmp;
		return it;
	}

	T topValue() { 
		if (top == nullptr) {
			cout << "빈 스택입니다.\n";
			return T();
		}
		return top->element(); }

	int length() { return stackSize; }

	bool isEmpty() { return stackSize == 0; }
};