[자료구조] 스택 (stack)

스택

스택은 컴퓨터에서 믿을 수 없을 정도로 많이 사용되는 자료구조이다.

후입선출(LIFO : Last In First Out) 형태로 나중에 들어온 것이 가장 먼저 나가는 형태를 띈다.

 

직역 그대로 데이터를 순서대로 쌓는 자료구조라고 생각하면 된다.

스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.

 

 

📌

스택 상단 : 스택에서 입출력이 이루어지는 부분

스택 하단 : 반대쪽인 바닥 부분

요소 : 스택에 저장되는 것

공백 스택 : 스택에 요소가 하나도 없을 때

 

---

스택의 연산

• push() : 스택 맨 위에 item을 추가
• pop() : 스택의 맨 위에 원소를 제거해서 반환
• peek() : 스택의 맨 위의 요소를 제거하지 않고 반환
• isFull() : 스택이 꽉 찼는지 확인
• isEmpty() : 스택이 현재 비어있는지 확인

 

---

클래스 생성

const int MAX = 10;

class Stack
{
    int top;
    int data[MAX];

public:
    Stack();
    void push(int element);
    int pop();
    int peek();
    bool isFull(), isEmpty();
    int size();
    void print();
};

클래스로 스택을 정의해준다.

 

---

생성자 초기화

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

 

 

push 함수

void Stack::push(int element) // 스택 맨 위에 item을 추가
{
    if (isFull())
    {
        error("Stack Full");
    }
    else
    {
        data[++top] = element;
    }
}

 

pop 함수

int Stack::pop() // 스택의 맨 위에 원소를 제거해서 반환
{
    if (isEmpty())
        error("Stack Empty");
    return data[top--];
}

 

peek 함수

int Stack::peek() // 스택의 맨 위의 요소를 제거하지 않고 반환
{
    if (isEmpty())
        error("Stack Empty");
    return data[top];
}

 

isFull 함수

bool Stack::isFull()
{
    return top == MAX - 1;
}

 

isEmpty 함수

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

 

print 함수

void Stack::print()
{
    for (int i = 0; i < top + 1; ++i)
        cout << data[i] << "\n";
}

 

---

📌 전체 코드

#include <iostream>

using namespace std;
const int MAX = 10;

void error(const char *message)
{
    cout << "Error: " << message << "\n";
    exit(1);
}

class Stack
{
    int top;
    int data[MAX];

public:
    Stack();
    void push(int element);
    int pop();
    int peek();
    bool isFull(), isEmpty();
    void print();
};

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

void Stack::push(int element) // 스택에 요소 삽입
{
    if (isFull())
    {
        error("Stack Full");
    }
    else
    {
        data[++top] = element;
    }
}

int Stack::pop() // 스택의 맨 위에 원소를 제거해서 반환
{
    if (isEmpty())
        error("Stack Empty");
    return data[top--];
}

int Stack::peek() // 스택의 맨 위의 요소를 제거하지 않고 반환
{
    if (isEmpty())
        error("Stack Empty");
    return data[top];
}

bool Stack::isFull()
{
    return top == MAX - 1;
}

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

void Stack::print()
{
    for (int i = 0; i < top + 1; ++i)
        cout << data[i] << " ";
    cout << "\n";
}

int main()
{
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    cout << "stack: ";

    stack.print();
    stack.pop();

    cout << "stack: ";
    stack.print();

    cout << "peek: " << stack.peek();
}

 

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!