[코딩인터뷰] 문제 3.2

문제 3.2

	#region Question 3.2
	/*
	* push와 pop의 두가지 연산뿐 아니라, 최솟값을 갖는 원소를 반환하는 min 연산을 갖춘 스택은 어떻게 구현할 수 있겠는가?
	*/
	public class StackWithMin
	{
	/// <summary>
	/// 데이터를 저장하는 스택
	/// </summary>
	private Stack<int> dataStack;
	/// <summary>
	/// 최솟값을 저장하는 스택
	/// </summary>
	private Stack<int> minStack;
	/// <summary>
	/// 스택 최솟값
	/// </summary>
	public int Min
	{
	get
	{
	try
	{
	return minStack.Peek();
	}
	catch (InvalidOperationException)
	{
	return int.MaxValue;
	}
	}
	}
	/// <summary>
	/// 클래스 초기화
	/// </summary>
	public StackWithMin()
	{
	this.minStack = new Stack<int>();
	this.dataStack = new Stack<int>();
	}
	/// <summary>
	/// 입력된 <paramref name="value"/> 데이터를 저장한다.
	/// </summary>
	/// <param name="value">저장할 데이터</param>
	public void Push(int value)
	{
	// 새로 입력된 데이터가 현재 최솟값보다 작은지 확인한다.
	if (value <= Min)
	{
	this.minStack.Push(value);
	}
	this.dataStack.Push(value);
	}
	/// <summary>
	/// 스택에서 마지막으로 저장된 데이터를 반환한다.
	/// </summary>
	/// <returns>스택 최상단 데이터</returns>
	public int Pop()
	{
	try
	{
	var value = this.dataStack.Pop();
	// 만약 최솟값과 반환할 데이터가 같을 경우, 이전 최솟값으로 변경한다.
	if (value == Min)
	{
	this.minStack.Pop();
	}
	return value;
	}
	catch (InvalidOperationException)
	{
	throw new Exception("Stack is empty.");
	}
	}
	}
	#endregion

view raw Code_Q3_2.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q3_2()
	{
	var stackWithMin = new StackQueue.StackWithMin();
	stackWithMin.Push(6);
	stackWithMin.Push(3);
	stackWithMin.Push(8);
	Assert.AreEqual(3, stackWithMin.Min);
	Assert.AreEqual(8, stackWithMin.Pop());
	Assert.AreEqual(3, stackWithMin.Pop());
	Assert.AreEqual(6, stackWithMin.Min);
	Assert.AreEqual(6, stackWithMin.Pop());
	}

view raw Test_Q3_2.cs hosted with ❤ by GitHub