스택 (배열을 이용한 구현)

스택은 한쪽 끝에서만 들어가고 한쪽 끝에서만 삽입과 삭제가 이루어지는 자료구조이다. LIFO(Last In First Out)로 가장 먼저 들어간 것이 가장 나중에 나오는 구조이다. 쉽게 생각하기 위해서 프링글스 통을 떠올려보자. 가장 밑에 있는 감자칩은 가장 먼저 들어갈 것이다. 이 감자칩을 빼내려면 위에 있는 감자칩을 모두 빼낸 후 가장 나중에 나올 수 있다. 이 구조가 스택의 핵심이다.

배열을 이용한 구현
들어가기에 앞서
 1. 5개의 배열을 이용한 스택을 구현한다.
 2. top이라는 용어가 나오는데 top은 가장 최근에 저장된 위치를 가리키는 변수이다.
    비어있는 상태일 경우에는 -1을 가리킨다.

5개 배열의 스택 초기 형태

① 데이터 삽입을 보자. 스택은 Push()라는 함수 호출로 값을 삽입한다.
가장 먼저 10이라는 값을 삽입해보자. top은 -1의 초기값에서 ++연산을 통해 값을 하나 증가시킴으로써
top의 값은 0이 된다. top이 0을 가리키는데 이 배열 위치에 10이라는 값을 저장한다.
이로써 데이터의 삽입이 완료가 된다. 아래의 그림은 10이 추가된 상태에서 20을 추가하는 모습을 보여준다.

데이터 삽입에 따라 변화되는 top을 나타낸 그림

② 데이터의 삭제와 반환을 보자. 스택은 Pop()이라는 함수 호출로 데이터를 삭제와 반환을 한다. top이 가리키고 있는 위치를 저장해둔 후 top --연산을 통해 top을 감소하며 저장해둔 위치를 반환한다.

20을 가리키던 top이 삭제, 반환되어 10을 가리키는 그림 

이제 코드로 구현해보자.

#include <iostream>
 
using namespace std;
 
#define MAX_LENGTH 5
 
// 스택 구조체
typedef struct arrayStack
{
    // 생성자
    arrayStack() : top(-1) { memset(dataArr, 0, sizeof(dataArr)); }
 
    int dataArr[MAX_LENGTH];
    int top;
}ARRAYSTACK;
 
void Push(ARRAYSTACK* stack, int data)
{
    // 가득차 있을 경우 리턴
    if (stack->top == MAX_LENGTH)
        return;
 
    // 데이터 추가를 위한 인덱스 증가
    stack->top++;
 
    // 데이터 저장
    stack->dataArr[stack->top] = data;
}
 
bool IsEmpty(ARRAYSTACK* stack)
{
    // 비어있을 경우 true를 반환
    if (stack->top == -1)
        return true;
 
    return false;
}
 
int Pop(ARRAYSTACK* stack)
{
    if (IsEmpty(stack))
    {
        cout << "스택이 비어있습니다." << endl;
        return 0;
    }
 
    // 삭제할 데이터가 저장된 인덱스 저장 및 감소
    int index = stack->top;
    stack->top--;
 
    // 삭제되는 데이터 반환
    return stack->dataArr[index];
}
 
int Peek(ARRAYSTACK* stack)
{
    if (IsEmpty(stack))
    {
        cout << "스택이 비어있습니다." << endl;
        return 0;
    }
 
    // 맨 위에 저장된 데이터 반환
    return stack->dataArr[stack->top];
}
 
int main()
{
    // 스택 생성
    ARRAYSTACK stack;
 
    // 데이터 삽입
    for (int i = 0; i < 5; ++i)
    {
        Push(&stack, i);
    }
 
    // 데이터 검색
    cout << Peek(&stack) << endl;
 
    // 데이터가 존재하지 않을 때까지 루프문 순회
    while (IsEmpty(&stack) == false)
    {
        // 데이터 출력
        cout << Pop(&stack) << endl;
    }
}