[자료구조] 스택(Stack), 큐(Queue)

 이번 글에서는 선형적 자료구조 중 스택(Stack)과 큐(Queue)에 대해서 살펴보도록 하겠다. 스택과 큐의 특징에 대해 알아보고, 직접 구현까지 해보도록 하겠다.

 

🔻스택(Stack)

스택(Stack)은 LIFO(Last-In-First-Out, 후입선출)의 특징을 가진 자료구조이다.

LIFO란, 가장 먼저들어온 것이 가장 늦게나가는 방식이다. 

위와 같이, 1,2,3순서대로 들어갔지만, 나올때는 3,2,1순서로 나오는 것을 LIFO방식이라고하고,

스택은 이러한 LIFO방식을 사용하는 자료구조이다.

즉, 스택에 가장 나중에 들어온 자료가 가장 먼저 삭제된다.

 

그러면 이러한 자료구조는 어디에 활용될 수 있을까?

우리가 에디터를 사용하여 글을 쓰다보면 잘못 썻을 때, Ctrl + Z를 사용해서 다시 이전으로 되돌린다. 이런 식으로 가장 나중에 들어온 것을 가장 먼저 써야할 때 사용할 수 있다.

 

🔸스택(Stack)의 구현

스택의 구현은 연결리스트를 사용하여 구현할 수도 있고, 배열을 사용하여 구현할 수도 있다. 나는 배열을 이용하여 크기가 10인 스택을 간단하게 구현해보았다.

template <typename T>
class Stack
{
public:
	void push(const T& val)
	{
		if (_topPos == _size - 1)
			return;

		_topPos++;
		_data[_topPos] = val;
		_size++;
	}

	T& top()
	{
		return _data[_topPos];
	}
	
	void pop()
	{
		_topPos--;
		_size--;
	}

private:
	T _data[10];
	int _topPos = 0;
	int _size = 0;
};

스택의 구현을 딱봐도 정말 간단하다.

 가장 뒤에 있는 자료의 인덱스를 가지고있는 변수를 하나두어, 추가할때는 그 인덱스를 1올려주고, 제거할때는 그 인덱스를 1 줄여주는 식으로 구현하면 된다.

 위의 코드는 정말 간단하게 짠 것인데, 이렇게 크기를 제한하는 것이 싫다면, 자료를 저장하는 배열을 동적배열이나 연결리스트 등으로 변경하면 해결할 수 있다.

template <typename T>
class Stack
{
public:
	void push(const T& val)
	{
		_data.push_back();
		_size++;
	}

	T& top()
	{
		return _data.back();
	}
	
	void pop()
	{
		_data.pop_back();
		_size--;
	}

private:
	vector<T> _data;
	int _size = 0;
};

 실제로 vector를 이용하여 스택을 구현하면 이런식으로 더욱 간단해진다.

 

 

 

 

🔻큐(Queue)

큐(Queue)는 스택과는 반대로 FIFO(First-In-First-Out, 선입선출)의 특징을 가진 자료구조이다.

즉, 가장 먼저 들어온 것이 가장 먼저 나가는 것이다.

이런식으로 들어간 순서 그대로 나오는 것이 특징이다.

큐에 가장 먼저 들어온 자료가 가장 먼저 삭제된다.

 

이러한 큐는 스택보다 활용할 수 있는 범위가 넓다. 보통 먼저들어간 것이 먼저나오는 것이 일반적이기 때문이다. 대기열같은 부분에서도 가장 먼저 대기열에 오른 작업을 먼저 수행하는 등 다방면으로 활용이 가능하다.

 

💡원형 큐(Circular Queue)?

 큐는 일반적으로 연결리스트로 구현하는 것이 가장 편하다. pop을 하면 그냥 맨 앞에 노드의 연결을 끊어버리면 되기 때문이다. 그에반해 배열로 구현하게 되면, 자료를 추가하면 뒤에 붙히고 제거하면 앞에를 빼는 방식이므로 공간적 낭비가 발생하거나, 불필요한 소요가 큰 작업을 해야할 수도 있다. 앞에 자료가 빠질 때마다 배열을 한칸씩 앞으로 당기거나, 아니면 공간을 비워두면서 낭비를 해야하기 때문이다. 하지만 배열을 사용하고도 앞서말한 문제점을 해결할 수 있다. 그 해결책이 바로 원형 큐(Circular Queue)이다.

 위는 배열로 큐를 구현하였을 때, 1,2,3,4,5,6을 순서대로 push하고 3번 pop을 한 상태이다. 일반적으로, 배열을 사용한 큐라면 위 상황에서 자료를 더 push하고 싶다면, 456을 앞으로 당기거나, 배열의 크기를 늘리는 수 밖에 없다. 하지만 앞으로 당기는 것도 비용이 발생하고, 배열의 크기를 늘리는 일또한 공간적 낭비가 심하다. 그래서 생각해낸 방법이, 앞에 비워진 공간을 활용하는 방법이다. 여기서 만약에 7을 push하고 싶다면 0번 인덱스에 7을 넣고, 이쪽이 큐 상에서 맨뒤이고 4가 맨 앞이다라는 정보만 가지고 있으면 되는 것이다.

 이런 식으로 말이다. push를 하면 rear부분에 넣고, pop을 하면 front부분에서 빼면된다.

 

 실제로는 선형적인 배열 위에 있지만 위와 같이 순환하는 형태로 생각을 하는 것이다. 이러한 순환적 특성을 이용하였기 때문에 원형 큐(Circular Queue)라고 불린다.

여기서 공간적한계까지 없애고 싶다면, 동적배열을 사용해서 꽉찼을 경우 공간을 증설하는 방법을 채택하면 될것같다.

🔸원형 큐(Circular Queue)의 구현

 일반적인 큐의 구현은 위에 서술한 스택의 구현을 참고하면 stl의 list자료구조를 써서 정말 간단하게 만들수 있어서 생략하고, 원형 큐를 구현해보는 것이 학습적 가치가 높다고 생각하여 배열을 이용하여 크기가 10짜리인 원형 큐를 구현해보았다.

const int CAPACITY = 10;
template <typename T>
class Queue
{
public:

	void push(const T& val)
	{
		if (_size == CAPACITY - 1)
			return;

		_data[_rear] = val;
		_rear = (_rear + 1) % CAPACITY;
		_size++;
	}

	T& front()
	{
		return _data[_front];
	}
	
	void pop()
	{
		_front = (_front + 1) % CAPACITY;
		_size--;
	}

	bool empty() { return _size == 0; }

private:
	T _data[CAPACITY];
	int _front = 0;
	int _rear = 0;
	int _size = 0;
};

 자료가 추가되면 rear의 위치를 옮기고, 자료가 빠지면 front의 위치를 옮기는 방식으로 위에서 설명한 그대로 구현하였다. 여기서 순환적 구조를 구현하기 위해 나머지 연산인 %를 사용한 것을 볼 수 있는데 크기가 10인 큐에서 현재 rear의 위치가 9번 인덱스라면 여기서 rear에 1을 더해주게 되면 10이므로 배열의 크기를 초과한다. 여기서 배열의 크기만큼을 나눈 나머지를 계산해주게 되면 0번 인덱스로 가게되면서 순환적 구조를 구현할 수 있다. 

 이런 식으로 나머지 연산을 이용하여 순환적 구조를 구현하는 아이디어가 학습할 가치가 높다고 생각하여, 원형큐를 직접 구현해보았다.

 

 

🔻마치며

 여기까지해서 스택과 큐, 그리고 원형큐 까지 알아보았다. 스택과 큐는 굉장히 기초적인 자료구조이면서 굉장히 중요한 자료구조 이므로 주의기울여 학습해야한다고 생각한다. 그래서 사실은 간단은 구조를 가지고있지만 자세히 정리해보았다.