[C++] 8 - 기초 문법 공부 일지(Stack)

• Stack
  • .LIFO - 후입선출 규칙을 따르는 자료 구조

Stack.h

#pragma once
#include <vector>
#include <iostream>
using namespace std;

template<typename T>
class Stack
{
public:
	void	push(const T& value) { _container.push_back(value); }
	void	pop() 
	{
		vector<T> newVector(_container.size() - 1);
		for (int i = 0; i < _container.size() - 1; i++)
			newVector[i] = _container[i];

		_container.clear();
		_container = newVector;
	}
	
	T&		top() { return _container[_container.size() - 1]; }
	bool	empty() { return size() > 0; }
	int		size() { return _container.size(); }

	void	Print()
	{
		for (auto data : _container)
			cout << data << " " << endl;
	}


private:
	vector<T> _container;
};

main.cpp

#include "pch.h"
#include "Stack.h"

int main()
{
	Stack<int> stack;
	stack.push(100);
	stack.push(200);
	stack.push(300);
	stack.push(400);

	cout << stack.top() << endl;
	stack.pop();

	stack.Print();
}

• Queue
  • .FIFO - 선입선출 규칙을 따르는 자료 구조

Queue.h

#pragma once
#include <vector>
#include <iostream>
using namespace std;

template<typename T>
class Queue
{
public:
	explicit	Queue() { _container.resize(100); }
	~Queue() { _container.clear(); _front = 0; _back = 0; _size = 0; }

	void		push(const T& value)
	{
		if (_size == _container.size())
		{
			vector<T> newVector(_container.size() - 1);
			newVector.resize(_size * 1.5);

			for (int i = 0; i < _size; i++)
				newVector[i] = _container[i];

			_container.clear();
			_container = newVector;
		}

		_container[_back] = value;
		_back = (_back + 1) % _container.size();
		_size++;
	}
	void		pop() { _front = (_front + 1) % _container.size(); _size--; }
	
	T&			front() { return _container[_front]; }
	bool		empty() { return _size == 0; }
	int			size() { return _size; }


	void		Print()
	{
		for (int i = _front; i < _back;i++)
			cout << _container[i] << " " << endl;
	}
private:
	vector<T>	_container;

	int			_front = 0;
	int			_back = 0;
	int			_size = 0;
};

main.cpp

#include "pch.h"
#include "Queue.h"

int main()
{
	Queue<int> queue;

	queue.push(100);
	queue.push(200);
	queue.push(300);

	queue.pop();

	queue.Print();
}

• PriorityQueue
  • 우선순위에 따라 정렬된 Queue
  • Tree   - heap 구조 사용

PriorityQueue.h

#pragma once
#include <vector>
#include <iostream>
using namespace std;

template<typename T, typename Predicate = less<T>>
class PriorityQueue
{
public:
	void push(const T& value)
	{
		_heap.push_back(value);

		int child = _heap.size() - 1;
		while (child > 0)
		{
			int parent = (child - 1) / 2; // now 의 부모 노드
			if (_predicate(_heap[child], _heap[parent])) break;

			std::swap(_heap[child], _heap[parent]);
			child = parent;
		}
	}
	void pop()
	{
		_heap[0] = _heap.back(); // 마지막 값 첫번째로
		_heap.pop_back(); // 마지막 값 제거

		int now = 0; // 처음부터 자리 찾기
		while (true)
		{
			int left = 2 * now + 1;
			int right = 2 * now + 2;
			int next = now;
			if (left >= _heap.size()) break; // 마지막 값 도달
			
			if (_predicate(_heap[next], _heap[left])) next = left;
			if (right < _heap.size() && _predicate(_heap[next], _heap[right])) next = right;
			if (next == now) break;

			std::swap(_heap[now], _heap[next]);
		}

	}

	void Print()
	{
		for (auto data : _heap)
			cout << data << " " << endl;
	}

	T& top() { return _heap[0]; }
	bool empty() { return _heap.empty();}

private:
	vector<T> _heap;
	Predicate _predicate;
};

main.cpp

#include "pch.h"
#include "Queue.h"

int main()
{
	PriorityQueue<int, greater<int>> queue;

	queue.push(100);
	queue.push(200);
	queue.push(300);

	queue.pop();
	queue.Print();
}