[자료구조] Stack and Queue

Stack

homogeneous items를 보관하며, 한쪽으로만 넣고 뺄 수 있음
LIFO: Last In First Out

ADT Operations

• Push(ItemType newItem)
• Pop()
• Top()

대표적으로 쓰이는 건 이 세 개고, 외에도 MakeEmpty, IsEmpty. IsFull 등 존재

---

C++로 구현

스택 구현은 배열로 함.

StackType.h

#pragma once
#define MAX_ITEMS 10000

class FullStack {};
class EmptyStack {};

template<class ItemType>
class StackType
{
public:
	StackType(); // 생성자
	bool IsFull() const;
	bool IsEmpty() const;
	void Push(ItemType item);
	void Pop(ItemType& item);
	ItemType Top();
private:
	int top;
	ItemType items[MAX_ITEMS];
};

StackType.cpp

#include "StackType.h"

template<class ItemType>
StackType<ItemType>::StackType()
{
	top = -1;
}

template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
	if (top < 0) return true;
	else return false;
}

template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
	if (top == MAX_ITEMS) return true;
	else return false;
}

template<class ItemType>
void StackType<ItemType>::Push(ItemType item)
{
	if (IsFull())
		throw FullStack();
	top++;
	items[top] = item;
}

template<class ItemType>
void StackType<ItemType>::Pop(ItemType& item)
{
	if (IsEmpty())
		throw EmptyStack();
	item = items[top];
	top--;
}

template<class ItemType>
ItemType StackType<ItemType>::Top()
{
	return items[top];
}

평소 스택 라이브러리를 이용했던 거랑 비슷하게 작동한다~

---

Queue

마치 차례대로 줄을 선 것처럼, 먼저 들어간 것이 먼저 나오는 자료구조
즉 front가 먼저 나가고, rear는 나중에 나옴
FIFO (First In First Out)

---

C++로 구현

• IsFull()

rear + 1 == front
또는 일반적으로, (rear + 1) % maxQue == front 라면
=> Queue가 꽉 찬 상태

• IsEmpty()

rear == front
=> Queue가 빈 상태

QueType.h

#pragma once

template<class ItemType>
class QueType
{
public:
	QueType(int max);
	~QueType();

	bool IsEmpty() const;
	bool IsFull() const;
	void Enqueue(ItemType item);
	void Dequeue(ItemType& item);
private:
	int front;
	int rear;
	int maxQue;
	ItemType* items;
};

QueType.cpp

#include "QueType.h"

template<class ItemType>
QueType<ItemType>::QueType(int max)
{
	maxQue = max + 1;
	front = maxQue - 1;
	rear = maxQue - 1;
	items = new ItemType[maxQue]; // 동적 할당
}

template<class ItemType>
QueType<ItemType>::~QueType()
{
	delete[] items;
}

template<class ItemType>
bool QueType<ItemType>::IsEmpty() const
{
	return (rear == front);
}

template<class ItemType>
bool QueType<ItemType>::IsFull() const
{
	return ((rear + 1) % maxQue == front);
}

template<class ItemType>
void QueType<ItemType>::Enqueue(ItemType item)
{
	rear = (rear + 1) % maxQue;
	items[rear] = item;
}

template<class ItemType>
void QueType<ItemType>::Dequeue(ItemType& item)
{
	front = (front + 1) % maxQue;
	item = items[front];
}