[Stack] 스택 Stack

스택 Stack

✏️개념

• 프로그램에서 중요성과 활용도가 매우 높은 자료구조

• 물건을 쌓아 올리듯 자료를 쌓아올린 형태의 자료구조
• 스택에 저장된 자료는 선형구조를 가짐
• 선형구조 : 자료간의 관계가 1대1관계

• 비선형구조 : 자료간 관계가 일대다인 관계

• 스택에 자료를 삽입하거나 꺼낼 수 있음
• LIFO 후입선출 : 마지막 삽입한 자료가 먼저 꺼내어짐

✏️구현

• 자료를 선형으로 저장할 저장소 필요
• C에선 배열 사용 가능
• 마지막 삽입된 원소 위치를 top이라고 함

연산

• 삽입 : push. 저장소에 자료를 저장
• 삭제 : pop. 저장소에서 자료를 꺼냄
• isEmpty() : 스택이 공백인지 아닌지 확인
• peek() : 스택의 top에 있는 원소 반환
• size() : 스택에 현재 저장되어 있는 데이터 개수 반환

push, pop 알고리즘

• push

    push(stack, x){
        top = top + 1;
        if(top > StackSize){
            overflow;
        }
        else{
            stack[top] = x;
        }
    }

• pop

    pop(stack){
        if(top == 0){
            // 빈 stack 이므로
            underflow;
        }
        else{
            return stack[top];
            top = top -1;
        }
    }

• 1차원 배열을 사용하여 구현한다면 구현은 용이하지만 크기 변경이 어렵다. 이때 저장소를 동적으로 할당하여 스택을 구현한다면, 메모리를 효율적으로 사용할 수 있다. 그러나 1차원 배열로 구현하는 것보다 복잡해진다.

구현

#include <iostream>
#include <cstdlib>
using namespace std;
 
// Stack 사이즈
#define SIZE 10
 
// Stack 클래스
class Stack
{
    int *arr;
    int top;
    int capacity;
 
public:
    Stack(int size = SIZE);         // 생성자
    ~Stack();                       // 소멸자
 
    void push(int);
    int pop();
    int peek();
 
    int size();
    bool isEmpty();
    bool isFull();
};
 
// 생성자
Stack::Stack(int size)
{
    arr = new int[size];
    capacity = size;
    top = -1;
}
 
// 소멸자
Stack::~Stack() {
    delete[] arr;
}
 
void Stack::push(int x)
{
    if (isFull())
    {
        cout << "Overflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
 
    cout << "Inserting " << x << endl;
    arr[++top] = x;
}
 
int Stack::pop()
{
    // underflow
    if (isEmpty())
    {
        cout << "Underflow\nProgram Terminated\n";
        exit(EXIT_FAILURE);
    }
 
    cout << "Removing " << peek() << endl;
 
    return arr[top--];
}
 
int Stack::peek()
{
    if (!isEmpty()) {
        return arr[top];
    }
    else {
        exit(EXIT_FAILURE);
    }
}
 
int Stack::size() {
    return top + 1;
}
 
bool Stack::isEmpty() {
    return top == -1;               // or return size() == 0;
}
 
bool Stack::isFull() {
    return top == capacity - 1;     // or return size() == capacity;
}