[STL] 스택 stack

스택은 컨테이너 클래스의 일종으로 다수의 데이터 객체들을 저장하는 자료구조를 나타내는 클래스이다. 스택은 push, pop 등의 멤버함수를 사용하여 LIFO의 특성에 따라 객체들을 삽입하거나 삭제할 수 있다.

LIFO$($Last In First Out) : 한쪽 끝$($top)에서 모든 삽입과 삭제가 일어나는 리스트

스택의 삽입과 삭제

• 삽입 push$($B) : top포인터를 +1 한후 top의 위치에 값을 삽입
• 삭제 pop$($) : top이 가리키고 있는 값을 스택에서 삭제

[ADT] 스택의 구현

#include<iostream>
using namespace std;

class Stack
{
private:
    int *stack;
    int top;
    int capacity;
public:
    Stack(int stackCapacity=1) //생성자
    {
        top=-1; 
        capacity = stackCapacity;
        stack = new int[capacity];
    }
    void Push(int &x);
    int Pop();
    int isEmpty();
    int showTop();
    int showSize();
};

void Stack::Push(int &x)
{
    if(top==capacity-1) //스택이 가득 차있을 경우
    {
        capacity*=2;
        int *temp = new int[capacity]; //두배 더 큰 배열 temp
        for(int i=0; i<=top; i++) temp[i]=stack[i]; 
        stack=temp; //stack이 이제 더 큰 배열 temp를 가리킴
        delete [] temp; //temp가 더이상 temp를 가리키지 않음
    }
    stack[++top]=x; //top을 한칸 올린후에 그 위치에 x를 삽입
}

int Stack::Pop()
{
    int x;
    if(top==-1) return -1; //스택이 비어서 삭제할 값이 없는경우 널값을 반환

    x=stack[top--]; //x에 스택의 top이 가리키는 값을 삽입한후 top을 한칸 내림
    return x;
}

int Stack::isEmpty()
{
    if(top==-1) return 1; //스택이 비었으면 1반환
    else return 0; //아니면 0반환 
}

int Stack::showTop()
{
    if(top==-1) return -1;
    return stack[top];
}

int Stack::showSize()
{
    return top+1;
}

[STL] 스택의 멤버함수 및 사용

#include<stack> 헤더를 추가하여 스택을 사용할 수 있다.

• push$($element) : 스택의 맨뒤에 원소 추가
• pop$($) : 스택의 맨뒤에 원소를 삭제
• top$($) : 스택의 맨뒤에 원소를 반환
• empty$($) : 스택이 빈상태면 true, 아니면 false 반환
• size$($) : 스택안에 들어있는 총원소 수를 반환

사용 예제

#include<iostream>
#include<stack> //스택 헤더
using namespace std;

int main(void)
{
    stack<int> st;
    st.push(1);
    st.push(2);
    cout<<st.top()<<'\n';

    st.pop();
    cout<<st.top()<<'\n';
    st.pop();

    if(st.empty()) cout<<"스택이 비었습니다\n";

    cout<<st.size()<<'\n';
    return 0;
}

결과

2
1
스택이 비었습니다
0

풀어보면 좋은 문제

• 괄호 $($BOJ_9012)

• 에디터 $($BOJ_1406)