Stack

정의

• 선형 자료구조
• LIFO(Last In, First Out)의 특성을 가져 가장 최근에 Push된 아이템이 제일 먼저 Pop되는 특징을 가짐
• Array나 Linked List 방식, 2가지 방식으로 구현가능

구성

• top : 현재 가리키는 아이템의 위치, 값이 없을 때는 -1 값을 가짐
• MAX_STACK_SIZE : array를 사용해 구현할 경우 array 생성시 사이즈 지정, IsFull() 체크시 기준이 됨
• Push(item) : 아이템을 입력받아 배열의 가장 위에 추가
• Pop() : 가장 위에 있는 아이템을 제거하면서 출력
• Peek() : 가장 위에 있는 아이템을 제거하지 않고 보여줌
• IsEmpty() : Stack이 비어있는지 여부를 출력, top
  (비어있는데 Pop() 또는 Peek()을 호출해 underflow 오류 발생하는 것을 방지)
• IsFull() : Stack이 가득 차있는지 여부를 출력
  (가득 차있는데 Push(item)를 호출해 overflow 오류 발생하는 것을 방지)
• Size() : 현재 포함하고 있는 아이템의 개수를 출력

사용

1) 함수 호출시 Stack으로 작동(재귀 함수가 대표적)
2) 중위 연산식을 후위 연산식으로 바꾸기
3) Backtracking 연산에 사용
4) Undo(실행 취소) 기능

구현

template <typename T>
class Stack
{
private:
    int top;
    const static int maxSize = 100;
    T arr[maxSize];

public:
    Stack() { top = -1; }

    bool IsFull() { return top == maxSize - 1; }
    bool IsEmpty() { return top == -1; }

    T Pop()
    {
        if(IsEmpty())
        {
            throw "Stack is empty";
        }

        return arr[top--];
    }

    void Push(T value)
    {
        if(IsFull())
        {
            throw "Stack is full";
        }

        arr[++top] = value;
    }
    
    T Peek()
    {
        if(IsEmpty())
        {
            throw "Stack is empty";
        }

        return arr[top];
    }
};

• template <typename T> 기능을 활용해 사용시 타입을 입력받아 여러 타입에 사용할 수 있는 Stack을 구현

Private 필드

private:
    int top;
    const static int maxSize = 100;
    T arr[maxSize];

• top : 현재 가리키고 있는 인덱스의 위치
• maxSize : 미리 정해둔 배열의 최대 크기
• arr : T 타입의 maxSize 크기의 배열

Public 필드

생성자

Stack() { top = -1; }

• 생성시 가리키고 있는 인덱스 위치를 -1로 초기화
• -1을 가리키고 있을 때 해당 Stack이 비어있는 것으로 인식

boolean 함수

bool IsFull() { return top == maxSize - 1; }
bool IsEmpty() { return top == -1; }

• IsFull() : Stack이 가득 차있는 여부를 확인
• IsEmpty() : Stack이 비어있는지 여부를 확인

Push, Pop, Peek 함수

void Push(T value)

    void Push(T value)
    {
        if(IsFull())
        {
            throw "Stack is full";
        }

        arr[++top] = value;
    }

• T 타입의 매개변수를 입력받아 Stack이 가득 차 있는지 확인 후 가득 차있다면 에러를 표시하고 아닐 경우 top에 1을 더한 자리에 값을 추가

T Pop()

    T Pop()
    {
        if(IsEmpty())
        {
            throw "Stack is empty";
        }

        return arr[top--];
    }

• Stack이 비어있지 않을 경우 기존 top위치에 있는 값을 반환하고 top 값을 1 감소시킴
• Stack이 비어있을 경우 역시 에러를 표시

T Peek()

    T Peek()
    {
        if(IsEmpty())
        {
            throw "Stack is empty";
        }

        return arr[top];
    }

• Stack이 비어있을 경우 역시 에러를 표시하며, 비어있지 않을 경우 기존 top위치에 있는 값을 제거하지 않고 해당 데이터를 표시