[C++/자료구조] Stack과 Queue

Stack ?

• 후 입 선 출 (LIFO : Last In First Out)
• 뒤에 들어온 오브젝트가 먼저 나간다는 의미
• 예) 웹페이지의 뒤로가기 버튼의 경우, 먼저 나타난 오브젝트가 뒤에 들어온 오브젝트가 가장 나중에 등장하게 된다.

즉, [1 page][2 page] [3 page][4 page] ⇒ [4 → 3 → 2 → 1] 변화

• C++ template Stack

#include <iostream>
#include <stack> //stack을 사용하기 위해 라이브러리를 포함해준다.
using namespace std;

int main()
{
	stack<int> s; //선언

	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4); //데이터 삽입

	int data = s.top(); //최상위 원소 출력 -> 데이터 제거는 안된 상태
	s.pop(); //마지막 데이터 원소 제거

	cout << s.empty() << '\n'; //비어있는지 유무를 확인
	cout << s.size() << '\n'; //데이터 원소 개수
}

Stack에는 스택의 정의 때문에 iterator이 없다.
실제로 구현하고 싶다면, 아래의 url을 참고하면 된다.
https://stackoverflow.com/questions/525365/does-stdstack-expose-iterators
→ stack의 경우 container vector,list,deque를 사용해서 구현 가능하다.
→ 그래서, template <typename T,typename Container = vector> 로 구현가능하다.

#include <iostream>
#include <list>
#include <vector>
using namespace std;

template <typename T,class Container = vector<T>>
class Stack
{
public:
	void push(T val)
	{
		_data.push_back(val);
	}
//성능 향상을 위해서 pop-top을 별도로 구분했다.
//pop 자체에서 reference를 넘길 수 없음. why? 삭제 대상이기 때문에 참조를 넘기면 안됨
//그렇다면, value로 전달되어야하는데 이럴 경우 속도에 영향 주게 되고
// 이를 막기 위해서 두 기능을 나눔
	void pop()
	{
		_data.pop_back();
	}

	T& top()
	{
		return _data.back();
	}

	int size()
	{
		return _data.size();
	}

	bool empty()
	{
		return _data.empty();
	}
private:
	//vector<T> _data; //vector나 list를 응용한다면 쉽게 구현 가능
	//list<T> _data; // 도 구현 가능하다.
	Container _data; // 도 구현 가능하다.
};

Queue

- 선 입 선 출 ( FIFO : First In First Out )
- 먼저 들어온 오브젝트가 먼저 나간다는 의미
- 예를 들어, 편의점 음료수의 경우 먼저 들어간 경우에 더 빨리 팔릴 가능성이 높다.
- ←(front) [ 1 ][ 2 ] [ 3 ][ 4 ] ←(rear)

C++ template Queue

#include <iostream>
#include <queue>
using namespace std;

int main()
{

	queue<int> q;

	for (int i = 0; i < 100; i++)
	{
		q.push(i); //데이터 삽입
	}

	while (q.empty() == false) //데이터가 비워있는지 유무 확인
	{
		int value = q.front(); //가장 앞에 있는 데이터 추출
		q.pop(); //앞에 있는 데이터 제거
		cout << value << '\n';
	}

	int size = q.size(); //데이터 크기 추출
	cout << q.size() << '\n';
}

→ Queue 실제로 구현, deque 사용

#include <iostream>
#include <deque>
#include <queue>
using namespace std;
//list, deque를 대표 Container로 사용 가능
//pop_front를 지원하는 list,deque 사용하고 default == deque<T>
//vector의 erase는 빠르게 동작하지 못한다는 단점이 있음.  O(N)
template <typename T,class Container=deque<T>>
class Queue
{
public:
	void push(const T& val)
	{
		_data.push_back(val); //O(1)
	}
	void pop()
	{
		_data.pop_front(); //O(1)
	}

	int top()
	{
		return _data.front();
	}

	int size()
	{
		return _data.size();
	}

	bool  empty()
	{
		return _data.empty();
	}
private:
	//list<T> _data;
	Container _data;
};

-> 원형 큐 구현 (배열을 이용한 큐)

#include <iostream>
//#include <deque>
#include <vector>
using namespace std;
//list, deque를 대표 Container로 사용 가능
//vector의 erase는 빠르게 동작하지 못한다는 단점이 있음.  O(N)
template <typename T>
class Queue
{
public:

	Queue():_size(0),_front(0), _rear(0)
	{
	}
	//원형큐
	//[front/rear] [] [] [] [] ... [] : 0단계, 초기
	//[front] [rear] [] [] [] ...  [] : 1단계, 0번 idx에 값 삽입
	//[front] [] [rear] [] [] [] ... [] : 2단계, 1번 idx에 값 삽입
	//[] [front] [] [rear] [] [] [] ... [] : 3단계, pop 수행, 0번 idx 값을 날려줌
	void push(const T& val)
	{
		if (_data.size() == _size)
		{
			//자리가 없음, 데이터 전부 찼음
			//증설 작업 수행
			int newSize =std::max(1, static_cast<int>(_data.size() * 2));
			vector<T> newData;
			newData.resize(newSize); //데이터 증설 작업에 필수적 
			for (int i = 0; i < _size; i++)
			{
				int idx = (i + _front)%_data.size();
				newData[i] = _data[idx];
			}
			_data.swap(newData); //swap을 이용해서 증설된 벡터의 주소와 교환한다.
			_front = 0; //0으로 초기화
			_rear = _size; //현재 size만큼 _back존재
		}
		_size++;
		_data[_rear] = val;
		_rear = (_rear + 1) % _data.size();
	}
	void pop()
	{
		_size--;
		_front = (_front + 1) % _data.size();;
	}

	int top()
	{
		return _data[_front];
	}

	int size()
	{
		return _size;
	}

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

	vector<T> _data;
	int _front;
	int _rear;
	int _size;
};