[C++, 자료구조] 스택(Stack)

■ 스택(Stack)

[스택 자료구조 예시]

스택(Stack) 자료구조는 실 생활에서도 자주 볼 수 있는 상황으로 예를 들 수 있다. 쌓인 상자나 프링글스 통 안의 감자칩처럼, 가장 아래에 있는 물건을 꺼내기 위해선 그 위에 있는 물건을 먼저 꺼내야 한다.

 

따라서 스택은 “가장 나중에 들어간 것이 가장 먼저 나온다.(LIFO : Last-In, First Out)” 라는 후입선출 방식의 자료구조이다.

 

▶ 스택의 추상 자료형

앞서 살펴본 리스트 자료구조의 추상자료형은 필요에 따라 정의 내용이 차이가 있었다. 하지만 스택의 추상 자료형은 상대적으로 정형화된 편이다.

 

한쪽이 막혀 있는 프링글스 통을 가지고 할 수 있는 일을 정리해 보면 아래와 같다.

1. 프링글스 통에 감자칩을 넣는다 : push
2. 프링글스 통에서 감자칩을 꺼낸다 : pop
3. 제일 위에 있는 감자칩을 확인한다 : peek

정의	기능
void Init(Stack* stack)	스택의 초기화를 진행한다. (스택 생성 후 제일 먼저 호출)
bool IsEmpty(Stack* stack)	스택이 빈 경우 true 반환. 아닐 경우 false 반환.
void Push(Stack* stack, Data data)	스택에 데이터를 저장한다.
Data Pop(Stack* stack)	마지막에 저장된 요소를 삭제하고 반환한다.
Data Peek(Stack* stack)	마지막에 저장된 요소를 반환하되 삭제하지 않는다.

스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜 각각 push, pop, peek이라 한다. 이제 이 추상자료형을 기반으로 직접 스택을 구현해 보자.

 

■ 배열 기반 스택 구현

[배열 기반 stack push 연산]

연결 리스트는 다양한 상황이 존재하지만 스택은 그 특성상 리스트만큼 상황이 다양하지 않다. 위 그림처럼 데이터를 추가하는 연산에 대해 정리해 보자.

• 인덱스 0의 배열 요소가 ‘스택의 바닥(프링글스 통의 바닥)’으로 정의된다.
• 마지막으로 저장된 데이터의 위치를 저장한다.
  • 저장된 위치를 기억해야 push(데이터를 삽입함), pop(데이터를 반환함) 연산을 쉽게 구현할 수 있다.

배열의 첫 번째 요소(인덱스 0)를 스택의 바닥으로 정의하면, 길이에 상관없이 인덱스 0의 요소가 항상 스택의 바닥이 된다.

 

1. ArrayStack.h

#pragma once
constexpr int STACK_LEN = 100;
typedef int Data;

struct ArrayStack
{
	Data arr[STACK_LEN];
	int topIndex;
};

typedef ArrayStack Stack;

void Init(Stack* p_stack);				// 스택 초기화

void Push(Stack* p_stack, Data data);	// 스택에 데이터 넣기
Data Pop(Stack* p_stack);				// 스택에서 데이터 꺼내기
Data Peek(Stack* p_stack);				// 최상위 데이터 확인

bool IsEmpty(Stack* p_stack);			// 스택이 비었는지 확인

앞서 정리한 스택의 추상 자료형을 기반으로 헤더 파일의 함수들을 정의하였다. 구현도 그렇게 어렵지는 않으니, 아래 내용을 보기 전에 직접 먼저 구현해 보는 것을 추천한다.

 

2. ArrayStack.cpp

🛠️stack 초기화 및 확인 함수

void Init(Stack* p_stack)
{
	if(p_stack == nullptr)
	{
		cout << "스택이 존재하지 않습니다!" << endl;
		return;
	}

	p_stack->topIndex = -1;
}

bool IsEmpty(Stack* p_stack)
{
	return p_stack->topIndex == -1;
}

Init 함수에서는 스택의 최상단을 표시하는 멤버인 topIndex만 -1로 초기화해주면 된다.

스택이 비어있는 경우는 topIndex 가 -1인 경우이므로, p_stack->topIndex == -1의 결과를 반환해 주면 된다.

 

🛠️ 데이터 삽입, 반환

void Push(Stack* p_stack, Data data)
{
	if(p_stack == nullptr || p_stack->topIndex + 1 >= STACK_LEN)
	{
		cout << "스택이 존재하지 않거나 더 이상 저장할 수 없습니다!" << endl;
		return;
	}

	p_stack->topIndex++;
	p_stack->arr[p_stack->topIndex] = data;
}

Data Pop(Stack* p_stack)
{
	if(p_stack == nullptr || IsEmpty(p_stack))
	{
		cout << "스택이 존재하지 않거나 꺼낼 데이터가 없습니다!" << endl;
		return -1;
	}

	Data result = p_stack->arr[p_stack->topIndex--];

	return result;
}

[배열 기반 stack push 연산]처럼 스택의 최상단을 가리키는 topIndex를 먼저 증가시킨 후, 그 위치에 데이터 삽입을 진행한다.

반대로 데이터를 추출(Pop)할 때는 반환할 데이터를 미리 저장한 뒤, topIndex를 감소시킨다.

• Push : topIndex 증가 → 데이터 삽입
• Pop : 데이터 추출 → topIndex 감소

 

🛠️ 최상단 데이터 확인

Data Peek(Stack* p_stack)
{
	if(p_stack == nullptr || IsEmpty(p_stack))
	{
		cout << "스택이 존재하지 않거나 꺼낼 데이터가 없습니다!" << endl;
		return -1;
	}

	return p_stack->arr[p_stack->topIndex];
}

스택이 반환할 다음 데이터를 확인할 필요가 있으므로, 반환은 하되 삭제하지 않는 함수(Peek)를 구현하였다.

 

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

int main()
{
	Stack stack;
	Data data = 0;

	Init(&stack);

	for(int i = 1; i <= 99; i += 2)
	{
		Push(&stack, i);
	}

	data = Peek(&stack);
	cout << "최상위 데이터: " << data << endl;

	while(IsEmpty(&stack) == false)
	{
		data = Pop(&stack);
		cout << data << " ";
	}

	cout << endl;
	return 0;
}

 

[실행 결과]

Main에서 만든 스택 자료구조를 테스트해 보면, 가장 마지막에 저장된 데이터가 먼저 나오는 LIFO구조로 데이터가 저장된 것을 확인할 수 있다.

 

■ 연결 리스트 기반 스택 구현

[연결 리스트 기반 스택 구현]

스택도 결국 연결 리스트이다. 다만 저장된 순서의 역순으로 조회(삭제)가 가능한 연결 리스트일 뿐이다.

• Head노드는 항상 최상단 데이터를 가리킨다.
• 데이터의 반환(삭제)은 Head노드가 가리키는 데이터부터 반환하고 삭제한다.

메모리 구조만 놓고 보면 연결 리스트인지, 스택인지 알 수 없다. 다만 위와 같은 메모리 구조를 바탕으로 push, pop 연산이 포함된 추상 자료형을 가지게 된다.

 

1. ListStack.h

#pragma once
typedef int Data;

struct Node
{
	Data data = 0;
	Node* next = nullptr;
};

struct LinkedStack
{
	Node* head = nullptr;
};

typedef LinkedStack Stack;

void LInit(Stack* p_stack);				// 스택 초기화

void LPush(Stack* p_stack, Data data);	// 스택에 데이터 넣기
Data LPop(Stack* p_stack);				// 스택에서 데이터 꺼내기
Data LPeek(Stack* p_stack);				// 최상위 데이터 확인

bool LIsEmpty(Stack* p_stack);			// 스택이 비었는지 확인

헤더파일에 선언된 함수의 종류와 그 기능은 앞서 보인 배열 기반 스택의 경우와 다르지 않다. 내부 구현이 배열에서 연결 리스트로반 바뀐 것뿐이다.

 

2. ListStack.cpp

🛠️stack 초기화 및 확인 함수

void LInit(Stack* p_stack)
{
	if (p_stack == nullptr)
	{
		return;
	}

	// 헤드 노드가 존재하지 않는 경우
	if(p_stack->head == nullptr)
	{
		p_stack->head = new Node();
	}

	// 데이터가 존재하는 경우
	auto cur = p_stack->head->next;

	while (cur != nullptr)
	{
		auto next = cur->next;
		delete cur;
		cur = next;
	}

	p_stack->head->next = nullptr;
}

bool LIsEmpty(Stack* p_stack)
{
	return p_stack->head->next == nullptr;
}

데이터가 존재하는 상태에서 Init 함수가 호출될 수 있으므로, 데이터가 존재한다면 저장된 데이터를 순차적으로 삭제한다.

head의 next는 항상 스택의 맨 위 데이터를 가리키므로, 이 변수가 nullptr이라면 스택은 비어있는 상태이다.

 

🛠️ 데이터 삽입, 반환

void LPush(Stack* p_stack, Data data)
{
	if(p_stack == nullptr || p_stack->head == nullptr)
	{
		return;
	}

	auto newNode = new Node();
	newNode->data = data;

	// 기존 노드 연결
	newNode->next = p_stack->head->next;

	// 헤드 노드와 새 노드 연결
	p_stack->head->next = newNode;
}

Data LPop(Stack* p_stack)
{
	if(p_stack == nullptr || LIsEmpty(p_stack))
	{
		cout << "스택이 존재하지 않거나 꺼낼 데이터가 없습니다!" << endl;
		return -1;
	}

	auto result = p_stack->head->next->data;
	auto delNode = p_stack->head->next;

	p_stack->head->next = delNode->next;
	delete delNode;

	return result;
}

데이터를 추가하는 Push 함수는 리스트의 머리에 새 노드를 추가해야 하니 위와 같이 구현하였다.

1. 새 노드를 생성한다(newNode).
2. newNode의 Next 노드를 Head→next 노드로 교체한다.
3. head노드와 newNode를 연결한다.

반대로 Pop함수는 포인터 변수 head가 가리키는 노드를 소멸시키고, 소멸된 노드의 데이터를 반환해야 한다.

1. 삭제할 노드의 주소와 데이터를 저장한다.
2. head노드와 삭제할 노드의 다음 노드를 연결한다.

 

🛠️ 최상단 데이터 확인

Data LPeek(Stack* p_stack)
{
	if (p_stack == nullptr || LIsEmpty(p_stack))
	{
		cout << "스택이 존재하지 않거나 꺼낼 데이터가 없습니다!" << endl;
		return -1;
	}

	return p_stack->head->next->data;
}

 

여기까지 연결 리스트를 사용하여 stack을 구현해 봤다. 다음에는 이 스택을 사용하여 계산기 프로그램을 만들어보자.