Stack & Queue

Stack & Queue

Stack과 Queue 또한 List와 Array 같이 정말 많이 쓰이고 중요한 자료구조이다.

Stack을 시각적으로 생각해보면 구멍이 막힌 파이프에 Node를 하나씩 집어 넣는다고 생각해볼 수 있다. 앞 구멍이 막혔으므로 처음 들어간 Node가 당연히 마지막으로 나오게 되어 FILO(First In Last Out)이게 된다.

함수를 call하는 것은 함수를 곧 스택 영역에 올리는 것인데 예를 들어서, 재귀 함수 같은 경우에서 내부적으로 함수를 무한히 부르게 되면 stack이 넘쳐나서 stack frame을 벗어나는 상황이 발생하는데 이를 stack overflow라고 한다.

#pragma once

template <typename T>
class CStackNode
{
	template <typename T>
	friend class CStack;

private:
	CStackNode()
	{
	}

	~CStackNode()
	{
	}

private:
	T		mData;
	CStackNode<T>* mNext = nullptr;
};

template <typename T>
class CStack
{
public:
	CStack()
	{
	}

	~CStack()
	{
		while (mNode != nullptr)
		{
			Node* Next = mNode->mNext;

			delete mNode;

			mNode = Next;
		}
	}

private:
	typedef CStackNode<T>	Node;

private:
	Node* mNode = nullptr;
	int	mSize = 0;

public:
	void push(const T& Data)
	{
		Node* NewNode = new Node;

		NewNode->mData = Data;

		NewNode->mNext = mNode;

		mNode = NewNode;

		++mSize;
	}

	void pop()
	{
		if (mSize == 0)
			return;

		Node* Next = mNode->mNext;

		delete mNode;

		mNode = Next;

		--mSize;
	}

	bool top(T& Data)	const
	{
		if (mSize == 0)
			return false;

		Data = mNode->mData;

		return true;
	}

	int size()	const
	{
		return mSize;
	}

	bool empty()	const
	{
		return mSize == 0;
	}

	void clear()
	{
		while (mNode != nullptr)
		{
			Node* Next = mNode->mNext;

			delete mNode;

			mNode = Next;
		}

		mSize = 0;
	}
};

StackNode는 어떤 pointer 값을 가질까?

Stack 에서 노드의 방향성은 스택이 신장되는 방향과 반대로 포인터를 저장한다.

예를 들어서,

#0 => #1 => #2

#1노드에는 #0노드의 포인터 주소 저장
#2노드에는 #1노드의 포인터 주소 저장

Queue

#pragma once

template <typename T>
class CQueueNode
{
	template <typename T>
	friend class CQueue;

private:
	CQueueNode()
	{
	}

	~CQueueNode()
	{
	}

private:
	T		mData;
	CQueueNode<T>* mNext = nullptr;
};

template <typename T>
class CQueue
{
public:
	CQueue()
	{
	}

	~CQueue()
	{
	}

private:
	typedef CQueueNode<T>	Node;

private:
	Node* mFirst = nullptr;
	Node* mLast = nullptr;
	int	mSize = 0;

public:
	void push(const T& Data)
	{
		Node* NewNode = new Node;

		NewNode->mData = Data;

		if (mSize == 0)
			mFirst = NewNode;

		else
			mLast->mNext = NewNode;

		mLast = NewNode;

		++mSize;
	}

	void pop()
	{
		if (mSize == 0)
			return;

		Node* Next = mFirst->mNext;

		delete mFirst;

		mFirst = Next;

		--mSize;
	}

	bool front(T& Data)	const
	{
		if (mSize == 0)
			return false;

		Data = mFirst->mData;

		return true;
	}

	int size()	const
	{
		return mSize;
	}

	bool empty()	const
	{
		return mSize == 0;
	}

	void clear()
	{
		while (mFirst != nullptr)
		{
			Node* Next = mFirst->mNext;

			delete mFirst;

			mFirst = Next;
		}

		mLast = nullptr;
		mSize = 0;
	}
};

Queue는 빼는 곳과 넣는 곳의 위치가 다르게 때문에 stack과 달리 두개의 주소변수가 필요하다.

다양한 queue들

• Circle Queue
  배열로 자료구조를 만들었을때 처음 index부분에 push front하는게 값이 비싸다. 따라서 앞부분을 끝부분과 연결함으로서 배열로 자료구조로 만드는 queue.

• 우선순위 queue
  힙 정렬할때 사용.