Stack

후입선출 구조이다.

 

구현 사항

push : O(1)

pop : O(1)

top : O(1)

 

 

코드

#pragma once

#include "GlobalDefine.h"
#include "MyVector.h"

template <typename _Ty>
class MyStack {
public:
	explicit MyStack() : vec_() {}

	~MyStack() {}

public:
	inline void push(const _Ty& _val)
	{
		vec_.push_back(_val);
	}

	inline void push(_Ty&& _val)
	{
		vec_.push_back(std::move(_val));
	}

	inline void pop()
	{
		vec_.pop_back();
	}

	inline _Ty& top()
	{
		return vec_.back();
	}

	inline bool empty() const { return size() == 0; }

	inline const int& size() const { return vec_.size(); }

private:
	MyVector<_Ty> vec_;
};

 

 

Stock Span

BOJ 2493 탑 https://www.acmicpc.net/problem/2493

위의 문제와 같은 개념이다.

요점은 입력된 값마다 인덱스를 붙이고, 현재 입력된 값보다 큰 값을 찾을때까지 pop을 수행한다.

pop되는 값이 추후 입력되는 값보다 작더라도 어차피 현재 입력된 값보다 작기 때문에 pop을 해도 상관없다.

일종의 그리디 알고리즘이다.

 

코드

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

void stockSpan(int price[], const int& n, int span[]) {
	stack<pair<int,int>> st;

	for (int i = 0; i < n; ++i) {
		while (!st.empty() && st.top().second < price[i])
			st.pop();

		if (st.empty())
			span[i] = 1;
		else
			span[i] = i - st.top().first;

		st.push({ i, price[i] });
	}
}

int main() {
	int price[] = { 100, 80, 60, 70, 60, 75, 85 };
	int n = sizeof(price) / sizeof(int);
	int span[1000] = {};

	stockSpan(price, n, span);

	for (int i = 0; i < n; ++i)
		cout << span[i] << ' ';

	return 0;
}