/ C

자료구조 정복하기 with C++ (3)Stack 스택

자료구조 정복하기 with C++ (3)Stack 스택

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.

스택(Stack)

스택은 마지막에 들어온 것이 먼저 나가는 LIFO(Last In First Out) 구조를 가진 자료 구조입니다. 일상 생활에서 책을 쌓고, 책을 꺼내는 것과 브라우저에서 서핑 후 뒤로가기 버튼을 누르는 것과 같습니다. 스택에서 데이터를 넣는 것을 push , 데이터를 꺼내는 것을 pop 이라고 합니다. 그리고 push와 pop을 하는 위치를 top이라고 하고, 스택의 가장 아랫부분을 bottom이라고 합니다.

스택 기능

구현할 stack의 기능은 다음과 같습니다.

  1. 스택의 공간 유무 반환
  2. 스택의 톱 원소 반환
  3. 톱에 아이템 삽입
  4. 톱 아이템 삭제

Stack

Stack.h

스택의 헤더파일

#pragma once

template <class T>							//자료형을 사용할 때 정의하기
class Stack
{
private:
	T* stack;
	int top;
	int capacity;

public:
	Stack(int stackCapacity = 10);			//처음에 크기가 stackCapacity인 공백 스택을 생성

	bool IsEmpty() const;					//스택의 원소 수가 0이면 true, 아니면 false를 반환

	T& Top() const;							//스택의 톱 원소를 반환

	void Push(const T& item);				// 스택의 톱에 item을 삽입
			
	void Pop();								// 스택의 톱 원소를 삭제
};

Stack.cpp

스택 소스코드

#include "Stack.h"
#include <iostream>

using namespace std;

template <class T>
Stack<T>::Stack(int stackCapacity) : capacity(stackCapacity)
{
	if (capacity < 1) throw "Stack capacity must be > 0";
	stack = new T[capacity];
	top = -1;
}

template <class T>
inline bool Stack<T>::IsEmpty() const { return top == -1; }

template <class T>
inline T& Stack<T>::Top() const
{
	if (IsEmpty()) throw "Stack is empty";
	return stack[top];
}

template<class T>
//배열이 차면 크기를 2배로
void ChangeSize1D(T* a, const int oldSize, const int newSize)
{
	if (newSize < 0) throw "New length must be >- 0";

	T* temp = new T[newSize];
	int number;
	(oldSize > newSize) ? (number = newSize) : (number = oldSize);
	copy(a, a + number, temp);
	delete[] a;
	a = temp;
}


template <class T>
void Stack<T>::Push(const T& x)
{
	if (top == capacity - 1)
	{
		ChangeSize1D(this, capacity, 2 * capacity);
		capacity *= 2;
	}
	stack[++top] = x;
}

template<class T>
void Stack<T>::Pop()
{
	if (IsEmpty()) throw "Stack is empty Cannot delete.";
	stack[top--].~T();
}

결과

main.cpp

#include "Stack.h"
#include <iostream>
#include "stack.cpp"

using namespace std;

int main()
{
	//stack 생성
	Stack <int>stack;

	//stack의 원소 수 검사
	cout << "stack 공백 검사" << endl;
	cout << stack.IsEmpty() << endl;
	
	//stack에 원소 대입
	cout << "\n0, 1, 2 순서로 스택에 대입" << endl;
	stack.Push(0);
	stack.Push(1);
	stack.Push(2);

	cout << "\nstack 공백 검사" << endl;
	cout << stack.IsEmpty() << endl;

	//stack의 톱 원소
	cout << "\n톱 원소: " << stack.Top() << endl;
	
	//stack의 톱 원소 삭제
	cout << "\nstack 톱 원소 삭제" << endl;
	stack.Pop();

	cout << "\n톱 원소: " << stack.Top() << endl;


	return 0;
}

Stack 자료구조를 작성했습니다. 결과가 잘 나옵니다!

ng.github.io/blob/master/Pictures/ds_2.jpg?raw=true’>