[C++] 큐와 스택 만들기(자료구조 헬 입성)

 

*head-tail / front-rear / start-end

Queue의 연산형태

stack의 연산 형태

방법1. 단방향 큐/스택 만들기

1.1 단방향 큐

#include <iostream>
#include <string>
#include <queue>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
};

// 큐 만들기
class Queue
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void Enqueue(int value);	// 넣는거
	int Dequeue();				// 빼는거
	int GetSize();				// size게터
	bool IsEmpty();				// 비어있는지 확인
	void Show();				// 전체 출력
};

void main()
{
	Queue intQueue;

	cout << "---큐 시작---" << endl;
	intQueue.Enqueue(10);
	intQueue.Enqueue(20);
	intQueue.Enqueue(30);
	intQueue.Enqueue(40);

	while (intQueue.IsEmpty() != true)
	{
		cout << intQueue.Dequeue() << endl;
	}
	cout << "---큐 끝---" << endl;
}

void Queue::Enqueue(int value)
{
	Node* newNode = new Node();
	newNode->value = value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		tail = newNode;
	}
}
int Queue::Dequeue()
{
	// head가 한칸 이동하면 됨
	Node* temp = nullptr;
	temp = head;
	int result = head->value;

	if (head == tail)
	{
		head = nullptr;
		tail = nullptr;
	}
	else
	{
		head = head->next;
	}
	size--;
	delete temp;
	return result;
}
int Queue::GetSize()
{
	return size;
}
bool Queue::IsEmpty()
{
	if (head == nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void Queue::Show()
{
	Node* current = nullptr;
	current = head;
	while (current != nullptr)
	{
		cout << current->value << endl;
		current = current->next;
	}
}

1.2 단방향 스택

#include <iostream>
#include <string>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
};

// 스택 만들기
class Stack
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void Push(int value);	// 넣는거
	int Pop();				// 빼는거
	int GetSize();			// size게터
	bool IsEmpty();			// 비어있는지 확인
	void Show();			// 전체 출력
};

void main()
{
	Stack intStack;

	cout << "---스택 시작---" << endl;
	intStack.Push(10);
	intStack.Push(20);
	intStack.Push(30);
	intStack.Show();
	cout << "---스택 끝---" << endl;
}

void Stack::Push(int value)
{
	Node* newNode = new Node();
	newNode->value = value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		tail = newNode;
	}
}
int Stack::Pop()
{
	Node* prevTail = head;
	int result = tail->value;

	if (head == tail)
	{
		head = nullptr;
		tail = nullptr;
		delete prevTail;
	}
	else
	{
		while (prevTail->next != tail)
		{
			prevTail = prevTail->next;
		}
		delete tail;
		tail = prevTail;
	}
	size--;
	return result;
}
int Stack::GetSize()
{
	return size;
}
bool Stack::IsEmpty()
{
	if (head == nullptr)
		return true;
	else
		return false;
}
void Stack::Show()
{
	Node* prevTail;
	Node* tempTail = tail;

	while (tempTail != head)
	{
		prevTail = head;
		cout << tempTail->value << endl;
		while (prevTail->next != tempTail)
		{
			prevTail = prevTail->next;
		}
		tempTail = prevTail;
	}
	cout << tempTail->value << endl;
}

방법2. 양방향 큐/스택 만들기

2.1 양방향 큐

#include <iostream>
#include <string>
#include <queue>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
	Node* prev = nullptr;
};

// 큐 만들기
class Queue
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void Enqueue(int value);	// 넣는거
	int Dequeue();				// 빼는거
	int GetSize();				// size 게터
	bool IsEmpty();				// 비어있는지 확인
	void Show();				// 전체 출력
};

void main()
{
	Queue intQueue;

	cout << "---큐 시작---" << endl;
	intQueue.Enqueue(10);
	intQueue.Enqueue(20);
	intQueue.Enqueue(30);

	while (intQueue.IsEmpty() != true)
	{
		cout << intQueue.Dequeue() << endl;
	}
	cout << "---큐 끝---" << endl;
}

void Queue::Enqueue(int value)
{
	Node* newNode = new Node();
	newNode->value = value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
}
int Queue::Dequeue()
{
	Node* temp = head;
	int result = head->value;

	if (head == tail)
	{
		head = nullptr;
		tail = nullptr;
	}
	else
	{
		head = head->next;
	}
	size--;
	delete temp;
	return result;
}
int Queue::GetSize()
{
	return size;
}
bool Queue::IsEmpty()
{
	if (head == nullptr)
		return true;
	else
		return false;
}
void Queue::Show()
{
	Node* current = head;
	while (current != nullptr)
	{
		cout << current->value << endl;
		current = current->next;
	}
}

2.2 양방향 스택

#include <iostream>
#include <string>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
	Node* prev = nullptr;
};

// 스택 만들기
class Stack
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void Push(int value);	// 넣는거
	int Pop();				// 빼는거
	int GetSize();			// size게터
	bool IsEmpty();			// 비어있는지 확인
	void Show();			// 전체 출력
};

void main()
{
	Stack intStack;

	cout << "---스택 시작---" << endl;
	intStack.Push(10);
	intStack.Push(20);
	intStack.Push(30);
	intStack.Show();
	cout << "---스택 끝---" << endl;
}


void Stack::Push(int value)
{
	Node* newNode = new Node();
	newNode->value = value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
}
int Stack::Pop()
{
	int result = tail->value;

	if (head == tail)
	{
		delete head;
		head = nullptr;
		tail = nullptr;
	}
	else
	{
		tail = tail->prev;
		delete tail->next;
	}
	size--;
	return result;
}
int Stack::GetSize()
{
	return size;
}
bool Stack::IsEmpty()
{
	if (head == nullptr)
		return true;
	else
		return false;
}
void Stack::Show()
{
	Node* prevTail;
	Node* tempTail = tail;

	while (tempTail != head)
	{
		prevTail = head;
		cout << tempTail->value << endl;
		while (prevTail->next != tempTail)
		{
			prevTail = prevTail->next;
		}
		tempTail = prevTail;
	}
	cout << tempTail->value << endl;
}