[자료 구조] 선형(Linear) 자료 구조 (2) 스택(Stack), 큐(Queue)

 

포스트를 읽으실 때 참고하실 점

• 해당 카테고리의 포스트들은 C/C++ 언어를 기준으로 작성되어 다른 언어에는 적용되지 않는 내용이 일부 포함될 수 있습니다. 또한, 글의 배치나 띄어쓰기는 PC 버전 전체 화면 크기를 기준으로 작성됩니다.
• 틀린 부분이 있는 경우, 댓글이나 이메일로 연락주시면 내용을 정정하도록 하겠습니다.

 

---

 

지난 포스트에서 배열, 연결 리스트에 대한 키워드를 정리(정리한 거 맞나?...)해봤는데 이번 포스트에서는 나머지 선형 자료 구조인 스택(stack)과 큐(queue), 그리고 자료 구조를 공부할 때 지속적으로 접하게 되는 개념인 추상 자료형(abstract data type, ADT)의 개념에 대해 정리해보려고 한다.

 

 

---

 

스택(Stack)

스택은 기본적으로 나중에 들어온 자료를 먼저 내보내는, 이른바 후입선출(last-in first-out, LIFO) 형태를 따르는 자료 구조이다(메모리 구조에서 이야기하는 스택도 같은 원리에 기반). 스택 구조에서 가장 중요한 것은 데이터가 들어오는 순서와 나가는 순서가 반대라는 것이다.

* 선입후출(first-in last-out, FILO)이라고 하는 경우도 있음.

 

 

후입선출의 형태를 가지는 구조를 어떻게 구현해야할까?

 

 

누군가가 방법을 알려주지 않고 만들어보라 한다면 어려울 것 같기도 하지만, 사실 간단한 방법을 통해 구현된다.

 

★ 앞으로 등장하는 모든 자료 구조는 배열과 연결 리스트 두 가지 방법으로 모두 구현 가능하며, 기반이 되는 구조의 특징(이전 포스트 참고)에 따른 장/단점이 존재한다. 따라서 활용 목적 상, 자주 사용되는 형태가 정해져있을 수 있다.

// 간단한 스택 클래스 코드


// 배열 기반
#include <vector>

template<typename T>
class Stack_Based_on_Array
{
private:
	std::vector<T> Data;

	int Top = -1;		// 내 역할이 제일 중요하지롱~

public:
	// some methods for stack
};


// 연결 리스트 기반
template<typename T>
class Stack_Based_on_LinkedList
{
public:
	struct Node
	{
		T Data;
		Node* Next;
	};

private:
	Node* Base;		// 연결 리스트에선 나도 필요해
	Node* Top;		// 내 역할이 제일 중요하지롱~
	
public:
	// some methods for stack
};

 

데이터가 들어올 수 있는 위치를 나타낼 Top이라는 멤버를 선언하여 이 멤버를 이용해 후입선출 형태의 구조를 구현한다. 이를 제외하면 그냥 배열이나 연결 리스트와 본질적으로 다를 것이 없다.

* 참고) 스택은 일반적으로 배열 형태로 구현하는 경우가 더 많다(이유는 아래 '스택과 큐의 활용' 부분 참고).

 

 

---

 

추상 자료형(abstract data type, ADT)

자료 구조를 공부하다 보면 추상 자료형이라는 개념이 자주 등장한다. 이 개념을 정확하게 모르더라도 자료 구조나 알고리즘을 공부할 수는 있지만 체계적으로 공부를 하려면 개념을 알아두어야 한다.

* 글쓴이는 실제로 추상 자료형이라는 거를 정확히 모르는 상태로 먼저 자료 구조와 알고리즘을 공부했었음...

 

추상 자료형이란, 어떠한 데이터들과 그 데이터들을 사용하여 수행할 연산(즉, 메서드)들을 추상적으로 정의한 것이다. 데이터를 다루는 메서드의 구체적인 구현까지는 정의하지 않기 때문에 '추상' 자료형이다. 마치 이는 우리가 클래스를 설계할 때(당연히 우리는 초보 프로그래머라 이런 방법에 숙달되어있지는 않지만...), 객체가 가질 데이터와 객체가 수행할 기능들을 기반 클래스나 인터페이스 클래스 등을 이용해 순수 가상 함수로만 정의(추상화, abstraction)해두는 것과 같다.

 

대중 교통의 하나인, 버스(bus)를 추상 자료형에 비유하여 표현해볼 수 있다. 버스의 승객들은 일종의 데이터라고 볼 수 있다. 그 승객들은 버스를 탈 수 있고, 내릴 수도 있다. 그리고 다른 대중 교통으로 환승을 할 수도 있다. 승객들이 버스를 타고 내리거나 환승하는 것은 승객들이 할 수 있는 행동, 즉 데이터들을 이용해 수행될 수 있는 연산이다. 그러므로 아래와 같이 버스라는 구조의 추상 자료형을 표현해볼 수 있다.

 

• 데이터(data): 승객
• 연산(operation): 탑승, 하차, 환승

 

비유한 것과 같이, 추상 자료형은 어떠한 자료 구조를 이론적인 측면에서 추상화를 해놓은 것이다.

 

 

---

 

다시 스택의 얘기로 돌아와서, 이 스택이라는 구조도 당연히 추상 자료형으로 표현될 수 있다. 스택이 가지는 연산은,

 

• 새로운 자료를 추가한다(push)
• 스택 내에 자료가 존재한다면, 가장 마지막에 들어온 자료를 내보낸다(pop)
• 스택 내에 자료가 존재한다면, 가장 마지막에 들어온 자료를 알려준다(top)
• 스택이 비어있는지 여부를 알려준다(empty)

 

과 같은 연산들을 포함한다. 이걸 굳이 달달 외우기보다는, 이러한 추상 자료형에 부합하는 자료 구조를 어떤 방법으로 구현하는지가 더 중요하다고 생각한다.

 

스택의 추상 자료형에 따라 스택 자료 구조를 실제로 구현하려면 어떻게 해야할까? 바로 Top을 이용하여 구조를 관리할 수 있도록 구현을 하면 된다. 국제법이나 헌법으로 정해져 있지는 않지만, 스택을 배열로 구현할 때 일반적으로 Top은 -1로 초기화하여 구현한다. 데이터를 스택에 넣을 때는 스택이 이미 꽉 찼는지 (즉, 오버플로가 발생하는지) 확인해야하므로 Top 멤버를 먼저 이동(증가)시킨 뒤 데이터를 추가하고, 데이터를 스택에서 뺄 때는 스택이 이미 비었는지 (즉, 언더플로가 발생하는지) 확인한 뒤에 데이터를 뺀 다음 Top을 이동(감소)시킨다.

 

[핵심] 스택을 구현하기 위해서는...

데이터가 들어올 수 있는 위치를 가리키기 위한 Top 멤버(정수형 또는 포인터)를 사용한다 !
(단, 연결 리스트의 경우는 스택 내의 가장 첫 데이터를 가리키기 위한 Base 포인터도 함께 사용)

 

 

---

 

큐(queue)

큐는 스택과는 다르게 먼저 들어온 데이터가 먼저 내보내지는, 이른바 선입선출(first-in first-out, FIFO삐뽀?) 형태를 따르는 자료 구조이다. 스택에 Top이 있다면 큐에도 무언가가 있지 않을까? 하는 생각을 했다면 당신은 이미 자료 구조의 고수가 될 싹이 보이는 인재이다.

* 참고) 섬댕이의 1초 쓸없지식 타임: 당구 큐대는 영어로 cue 라고 한다.

 

큐는 Front(또는 Head)와 Rear(또는 Tail)라는 두 개의 멤버를 활용하여 구현된다. 구현하는 사람마다 조금씩 다르기는 하지만, 일반적으로는 Front는 내보내기 위한 데이터의 위치를 나타내며, Rear는 큐 안에 데이터가 들어올 위치를 나타낸다. 

대부분의 경우에는 Front = Rear = 0인 상태로 시작하도록 구현하는 것 같다(배열 기준).

// 간단한 형태의 큐 클래스


#include <vector>

// 배열 기반
template<typename T>
class Queue_Based_on_Array
{
private:
	std::vector<T> Data;

	int Front;		// 우리 역할이
	int Rear;		// 제일 중요하지롱~

public:
	// some methods for queue
};


// 연결 리스트 기반
template<typename T>
class Queue_Based_on_LinkedList
{
public:
	struct Node
	{
		T Data;
		Node* Next;
	};

private:
	Node* Front;		// 우리 역할이
	Node* Rear;		// 제일 중요하지롱~
	
public:
	// some methods for queue
};

 

스택과 마찬가지로 Front, Rear가 없으면 그냥 일반 배열이나 연결 리스트이다. 큐의 추상 자료형은 아래와 같다.

 

• 새로운 자료를 추가한다(enqueue)
• 큐 내에 자료가 존재한다면, 가장 먼저 들어온 자료를 내보낸다(dequeue, 참고: double-ended queue랑 다르다)
• 큐 내에 자료가 존재한다면, 가장 먼저 들어온 자료를 보여준다(peek, 내보내지는 않음)
• 큐가 비어있는지 여부를 알려준다(empty)

 

위와 같은 기능을 구현하기 위해서 큐에서는 Front와 Rear 멤버를 적절하게 이용해야 한다. 큐에 새로운 데이터가 입력될 때는 Rear를 제어하며, 데이터를 내보낼 때는 Front를 제어한다. 일반적으로 Front == Rear인 경우를 비어있는 상태라고 정의한다.

* 참고) 큐 역시 일반적으로 배열 형태로 구현하는 경우가 더 많다(이유는 아래 '스택과 큐의 활용' 부분 참고).

 

[핵심] 큐를 구현하기 위해서는...

큐 안에 현재 존재하는 데이터 중에서,
가장 앞의 데이터(Front)와 데이터가 들어올 위치(Rear)를 가리키는 멤버를 사용한다 !

큐의 추상 자료형을 구체화하기 위해 메서드를 구현할 때에는
Front와 Rear의 움직임에 항상 주의해서 구현해야 한다 !

 

큐는 배열에 기반하여 구현할 때 한정하여 가지는 특징들이 있다. 선형 큐는 동적 배열을 활용해 가변 길이를 가질 수는 있지만, 데이터 입출력 과정에서 자연스럽게 빈 공간이 만들어져 메모리 낭비가 발생한다(데이터를 내보낼 때마다 Front가 뒤쪽으로 이동하기 때문). 이러한 빈 공간을 재사용하려면 큐에 존재하는 데이터 전체를 꺼낸 다음 다시 큐를 만들어 집어넣거나, 데이터 전체를 일일이 앞쪽으로 옮겨주는 비효율적인 과정이 수반된다.

 

한편, 배열 기반의 환형 큐(circular queue)는 처음 정한 길이(capacity)를 바꿀 수 없고 선형 큐에 비해 구현이 까다롭지만 지정된 길이 내에서 데이터가 여러 번 입출력 되어도 메모리를 효율적으로 사용할 수 있는 장점이 있다.

* 참고) 환형 큐를 배열로 구현할 때 Front의 위치와 Rear의 위치가 같으면 empty 상태인지 full 상태인지 구분할 수 없기 때문에, 일반적으로 capacity를 실제 큐의 크기보다 1 만큼 작게 설정하고 데이터를 입력 받는다.

* 참고) 환형 큐의 enqueue와 dequeue 연산의 구현에 있어 나머지 연산을 활용해 Front, Rear를 제어하면 간편하다.

 

연결 리스트 기반의 큐는 포인터를 통한 연결로 인해 배열 기반의 큐보다 더 자유로운 형태로 구현할 수 있지만, 자주 구현되는 형태는 아니다.

 

추가적으로, deque(여기서는 double-ended queue의 의미. 신기하게도 '데큐(나의 히어로 아카데미아의 데쿠 아님)'가 아닌 '덱' 이 좀 더 정확한 발음이라고 한다)라는 이름의 자료 구조가 있는데 이 구조는 앞과 뒤, 양방향으로 데이터가 들어왔다 나갔다 하는 큐이다. 게임 프로그래밍 실무에서는 deque는 거의 쓰이는 일이 없다고 한다. 그래도 이름이랑 개념정도는 알아두자.

 

 

---

 

스택과 큐의 활용

스택과 큐는 일반적으로 배열 형태로 구현하여 사용하는 경우가 더 많다. 그 이유는 1) 중간에 데이터를 삽입하거나 제거하는 일이 전혀 없고, 2) 스택이나 큐를 사용할 때, 대체로 고정된 크기의 형태로 사용하는 경우가 일반적이므로 연결 리스트를 사용하는 것이 오히려 메모리 단편화가 발생할 소지가 더 크기 때문이다(연결 리스트를 사용하면 노드를 계속해서 할당/제거하기 때문).

 

스택이나 큐를 활용하는 곳은 정말 상상 이상으로 다양하다. 우리는 프로그래머 꿈나무니까 어디에 활용하는지도 매우 중요하다. 스택은 데이터의 입력과 출력의 방향을 뒤집어야 하는 경우(어떤 프로그램에서 Ctrl + Z(undo), Ctrl + Y(redo)와 같은 명령을 구현한다거나...)나 재귀 호출과 같은 구조를 구현할 때 이용된다. 큐는 프로그램에 전달되는 메세지를 관리하기 위한 메세지 큐(환형 큐를 주로 사용)를 만드는 곳에 사용되기도 한다. 또한 향후에 비선형 자료 구조 및 알고리즘을 공부할 때에도 스택과 큐가 계속해서 사용된다.

 

• 함수의 재귀 호출이나 깊이 우선 탐색(depth-first search, DFS) 알고리즘 → 스택 원리에 기반.
• 너비 우선 탐색(breadth-first search, BFS) 알고리즘 → 큐 자료 구조에 기반.

 

---

 

포스트에 소개되지 않은 구체적인 내용은 1) 글 아래의 태그 또는 블로그 내 검색을 통해 활용 예시 찾아보기(코딩 문제 풀이 등), 2) 관련 링크나 구글링을 통해 따로 공부해야하는 점은 양해를 부탁드립니다.