[Data Structure] Stack

스택

 

박스에 물건을 쌓듯이 먼저 들어간 물건이 가장 나중에 나오는 것처럼, 스택의 구조는 위와 같다. 후입선출, 나중에 들어간 데이터가 제일 먼저 밖으로 빠져 나오는 구조이다.

 

때문에 스택은 Push와 Pop이 핵심 연산이다.

 

class Stack
{
public:
    Stack()
    {
    	stackArr = new int[5];;
    	capacity = 5;
    	top = 0;
    };

private:
    int*    stackArr; // 스택 배열
    int     capacity; // 허용량
    int          top; // 현재 상위 위치

public:
    void Push(int data);
    void Pop();
    int Top() { return stackArr[top - 1]; }
    int Size() { return top; }

private:
    void reAlloc(); // 재할당을 위한 함수이기 때문에 private로 접근허용

};

이런 구조의 클래스가 있다고 가정하면 현재 내부에 선언된 멤버함수는 Push와 Pop이 있다. 간단하게 스택을 구현하면 함수는 다음과 같이 정의할 수 있다.

 

#include "Stack.h"

void Stack::Push(int data)
{
    if (top > capacity - 1)
        reAlloc(); //용량 초과시 재할당을 위한 함수

    stackArr[top] = data;
    top++;
}

void Stack::Pop()
{
    stackArr[top] = 0;
    --top;
}

void Stack::reAlloc()
{
    int* tempArr = new int[capacity * 2];

    for (int i = 0; i < top + 1; ++i)
    {
        tempArr[i] = stackArr[i];
    }

    delete[] stackArr;

    stackArr = tempArr;
    capacity *= 2;
}

 

이렇게 한 뒤 메인함수에서 스택을 사용해서 데이터를 입력하고 출력해보자.

 

#include "Stack.h"

int main()
{
	Stack stk;

	stk.Push(50);
	stk.Push(20);
	stk.Push(80);
	stk.Push(30);
	stk.Push(10);
	stk.Push(60);
	stk.Push(90);
	stk.Push(5);
	stk.Push(100);
	stk.Push(120);

	int num = stk.Size();

	for (int i = 0; i < num; ++i)
	{
		cout << stk.Top() << endl;
		stk.Pop();
	}

	return 0;
}

정상적으로 가장 나중에 들어간 데이터부터 차례대로 출력이 됨을 알 수 있다.

 

스택은 STL로 구현이 되어 있지만 어떤 구조인지 알기 위해 간단히 구현하면 위와 같이 구현할 수 있다. 스택은 배열로 구현할 수 있지만 리스트로도 구현이 가능한 구조이다.