스택(Stack)

  스택 

데이터를 하나의 접근점을 통해 순차적으로 저장하는 자료구조로 마지막에 입력된 데이터가 가장 먼저 사용되는 후입 선출(Last In First Out) 구조를 가진다.

 

- 삽입(Push) 연산

스택에 데이터를 삽입하고 삽입된 데이터를 최상단으로 표시한다.

 

* 원본 데이터

인덱스	0	1	2	3 : TOP	4
데이터	10	20	30	40

인덱스	0	1	2	3	4 : TOP
데이터	10	20	30	40	50

 

- 인출(Pop) 연산

최상단에 존재하는 데이터를 인출하고 최상단의 다음에 존재하는 데이터를 최상단으로 표시한다.

인덱스	0	1	2	3 : TOP	4
데이터	10	20	30	40	50

┗→ 50

 

  스택 구현 준비 

스택은 선형 리스트와 연결 리스트에서 모두 구현할 수 있는 기본적인 자료구조 중 하나이다.

 

구현에 필요한 메서드 및 속성은 다음과 같다.

• 생성자
  • Stack() 비어있고 기본 초기 용량을 가지는 인스턴스 생성
  • Stack(Stack&) 다른 Stack 데이터로 인스턴스 생성
  • Stack(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성
• 속성 
  
  • Count Stack에 포함된 데이터의 개수
• 메서드 
  • Push(data) Stack의 맨 위에 데이터를 저장
  • Peek() Stack의 맨 위의 데이터를 제거하지 않고 반환
  • Pop() Stack의 맨 위의 데이터를 제거하고 반환
  • Clear() 저장되어 있는 모든 데이터 삭제
  • Contains(data) 데이터가 저장되어 있는지 여부 확인

 

  스택 구현 

ArrayList와 SinglyLinkedList를 이용하여 Stack을 구현한다.

 

Stack.h

#pragma once
// ArrayList를 사용하는 경우
#include "../ArrayList/ArrayList.h"

// SinglyLinkedList를 사용하는 경우
#include "../LinkedList/SinglyLinkedList.h"

class Stack
{
public:
#pragma region 생성자
	Stack();
	Stack(const Stack& other);
#pragma endregion

#pragma region 속성
	const size_t Count() { return m_items.Count(); }
#pragma endregion

#pragma region 메서드
	void Push(int value);

	int Peek();
	int Pop();
	void Clear();

	bool Contains(int value);

	void PrintInfo();
#pragma endregion

private:
#pragma region 변수
	// ArrayList를 사용하는 경우
	ArrayList m_items;
    
	// SinglyLinkedList를 사용하는 경우
	SinglyLinkedList m_items;
#pragma endregion
};

 

생성자 구현

기본 생성자와 Stack을 인자로 받는 복사 생성자를 구현한다.

 

Stack.cpp

/// <summary>
/// 비어있고 초기 용량을 가지는 Stack을 생성한다.
/// </summary>
Stack::Stack()
{
}

/// <summary>
/// 다른 Stack과 동일한 값을 가지는 Stack을 생성한다.
/// </summary>
/// <param name="other">기준이 될 Stack</param>
Stack::Stack(const Stack& other)
	: m_items(other.m_items)
{
}

 

데이터 삽입 메서드 구현

데이터 삽입 연산에 필요한 메서드들을 구현한다.

 

Stack.cpp

/// <summary>
/// Stack의 맨 위에 값을 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void Stack::Push(int value)
{
	m_items.Add(value);
}

 

데이터 인출 메서드 구현

데이터 인출 연산에 필요한 메서드들을 구현한다.

 

Stack.cpp

/// <summary>
/// Stack의 최상위 값을 제거하지 않고 반환한다.
/// </summary>
/// <returns>최상위에 있는 값</returns>
int Stack::Peek()
{
	if (m_items.Count() <= 0)
	{
		throw std::out_of_range("empty");
	}
    
	// ArrayList를 사용하는 경우
	return m_items.Item(m_items.Count() - 1);
    
	// SinglyLinkedList를 사용하는 경우
	return m_items.Front().m_data;
}

/// <summary>
/// Stack의 최상위 값을 제거한 뒤 반환한다.
/// </summary>
/// <returns>최상위에 있던 값</returns>
int Stack::Pop()
{
	if (m_items.Count() <= 0)
	{
		throw std::out_of_range("empty");
	}

	// ArrayList를 사용하는 경우
	int data{ m_items.Item(m_items.Count() - 1) };
	m_items.RemoveAt(m_items.Count() - 1);

	// SinglyLinkedList를 사용하는 경우
	int data{ m_items.Front().m_data };
	m_items.Remove(&m_items.Front());

	return data;
}

/// <summary>
/// Stack의 모든 값을 제거한다.
/// </summary>
void Stack::Clear()
{
	m_items.Clear();
}

 

기능 메서드 구현

자료구조를 효율적으로 사용하기 위한 기능 메서드를 구현한다.

 

Stack.cpp

/// <summary>
/// Stack에 지정한 값이 존재하는지 확인한다.
/// </summary>
/// <param name="value">Stack에서 찾을 값</param>
/// <returns>값의 존재 여부</returns>
bool Stack::Contains(int value)
{
	return m_items.Contains(value);
}

 

참고문헌

Microsoft MSDN.Stack 클래스 (System.Collections)