자료구조 - 스택

[스택(Stack)]

스택(Stack)은 후입선출(Last-In, First-Out, LIFO) 방식의 자료구조로, 데이터를 저장하고 접근하는데 사용됩니다.

이 자료구조는 데이터를 넣는(push) 작업과 데이터를 빼내는(pop) 작업을 지원합니다.

C++에서는 표준 라이브러리의 std::stack 클래스를 사용하여 스택을 구현할 수 있습니다.

 

 

 

[스택의 개념]

 

개념 설명

• 스택은 한쪽 끝에서만 데이터를 삽입하고 삭제할 수 있는 자료구조입니다.
• 가장 최근에 삽입된 항목이 가장 먼저 삭제됩니다.
• 주요 연산은 push (데이터 삽입), pop (데이터 삭제), top (가장 최근에 삽입된 데이터 접근) 입니다.
• top은 초기값이 -1 입니다.

 

스택의 구조

• 배열이나 연결 리스트 등으로 구현될 수 있습니다.
• 배열로 구현할 경우 크기가 고정되어 있거나 동적으로 크기를 조절할 수 있습니다.

 

 

[스택의 추상 자료형(ADT)]

스택은 다음과 같은 연산들로 추상화할 수 있습니다.

 

<is_empty> : 스택이 비어있는지 확인합니다.

top이 가장 최근에 삽입된 데이터를 가리키기 때문에 top을 사용해서 확인합니다.

is_empty(S):
    if top == -1
        then return TRUE
        else return FALSE

 

<is_full> : 스택이 가득 차 있는지 확인합니다.

top >= (MAX_STACK_SIZE - 1) 이면 스택이 꽉 차 있습니다.

is_full(S):
    if top >= (MAX_STACK_SIZE - 1)
        then return TRUE
        else return FALSE

 

<push> : 스택의 맨 위에 요소를 삽입합니다.

top을 증가시키고나서 요소를 삽입해야 합니다. 그렇지 않으면 마지막 요소가 지워지게 됩니다.

push(S, x):
    if is_full(S)
        then error "overflow"
        else top<-top+1
            stack[top]<-x

 

<pop> : 스택의 맨 위에 요소를 삭제합니다.

스택이 비어있지 않으면 top이 가리키는 값을 반환하고 top을 하나 감소시킵니다.

pop(S, x):
    if is_empty(S)
        then error "underflow"
        else e<-stack[top]
            top<-top-1
            return e

 

<peek> : 스택의 맨 위 요소를 제거하지 않고 반환합니다.

peek(S)
    if(is_empty(S))
        return ERROR_STACK_EMPTY;
    else
    	return 마지막 요소 삭제하지 않고 반환

 

배열을 사용하는 스택을 구현해보면 다음과 같습니다.

#include <iostream>

#define MAX_SIZE 100

class Stack 
{
    private:
        int arr[MAX_SIZE];
        int top;

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

        bool isEmpty() 
        {
            return (top == -1);
        }

        bool isFull() 
        {
            return (top == MAX_SIZE - 1);
        }

        void push(int value)
        {
            if (isFull()) 
            {
                std::cout << "Stack overflow!" << std::endl;
                return;
            }
            arr[++top] = value;
        }

        void pop() 
        {
            if (isEmpty())
            {
                std::cout << "Stack underflow!" << std::endl;
                return;
            }
            top--;
        }

        int peek() 
        {
            if (isEmpty()) 
            {
                std::cout << "Stack is empty!" << std::endl;
                return -1;
            }
            return arr[top];
        }
};        

int main() 
{
    Stack myStack;

    // 스택에 데이터 삽입
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // 스택의 가장 위(top) 요소 확인
    std::cout << "Top element of the stack: " << myStack.peek() << std::endl;

    // 스택에서 데이터 삭제
    myStack.pop();

    // 스택이 비어있는지 확인
    if (myStack.isEmpty()) 
    {
        std::cout << "Stack is empty." << std::endl;
    } 
    else 
    {
        std::cout << "Stack is not empty." << std::endl;
    }

    return 0;
}