Stack(스택) 구현 & Stack STL 총정리

c++ 에서 array를 이용하여 stack을 구현하기.

c++의 STL 중 하나인 Stack Container를 구현해봤다.

 

 

 Stack의 동작 원리

-LIFO (Last in First Out) : 가장 마지막에 들어온 값이 가장 먼저 나갈 수 있는 형태이다.

반대로 가장 먼저 들어온 값은 가장 마지막에 나갈 수 있다.

 Stack의 함수

1) empty - stack이 비어있다면 true를 return, 아니라면 false를 return.
2) push - 값을 stack에 집어넣는다.
3) pop - 가장 최근에 들어온 값을 stack에서 빼낸다.
4) top - 가장 최근에 들어온 값을 return.
5) size - stack의 크기를 return.
가 있다.

 구현한 코드 설명

1) empty

스택이 비어 있다면 true를, 아니라면 false를 return.

2) push

스택의 크기를 먼저 증가시킨다.
집어 넣을 값을 스택에 집어 넣는다.

3) pop

만약 스택이 비어 있다면 -1을 출력.
아니라면 가장 최근에 들어온 값을 꺼낸다.

4) top

만약 스택이 비어 있다면 -1을 출력.
아니라면 가장 최근에 들어온 값을 return.

5) size

스택의 현재 크기를 return.

 

Coding

// array를 통한 stack 구현.
// 기능
// 1) empty 2) push 3) pop 4) top 5) size
// stack이 비어있을 때 N의 값은 -1

#include <iostream>

using namespace std;

struct Stack{
    // 스택의 크기를 나타내는 N
    // 스택의 값 저장소 arr
    int N = -1;
    int * arr;
};
using stack = Stack *;

// 1) empty
// stack s 가 비어있다면 true를 , 아니라면 false 를 출력.
bool empty(stack s){
    return (s->N == -1) ? true : false;
}
// 2) push
// stack s 에 num 값을 집어넣음.
void push (stack s , int num){
    s->arr[++s->N] = num;
}
// 3) pop
// stack s에서 가장 최근에 들어온 값을 뺌.
void pop (stack s){
    if(empty(s)){
        cout << "It doesn't work. stack is empty" << "\n";
    }
    else{
        s->N--;
    }
}
// 4) top
// stack s 에서 가장 최근에 들어온 값을 출력.
int top(stack s){
    if(empty(s)){
        return -1;
    }
    return s->arr[s->N];   
}
// 5) size
// stack s 의 크기를 출력.
int size(stack s){
    return s->N+1;
}

실행 결과

설명

push 를 통해 [1,2,3,4,5] 스택을 만들고 top() -> 5

pop을 통해 [1,2,3,4] 만든 뒤 top() -> 4

size() -> 4

empty() -> 0 (false)

 

-----------------------------------------------------------------------------------------------

STL 사용.

헤더 파일

#include <stack>

선언

stack<type> 스택이름 ;

스택 함수들


1) empty
스택이름.empty()

스택이 비어있다면 true , 아니라면 false를 반환.

2) push
스택이름.push(데이터);

스택에 괄호 속 데이터를 추가한다.

3) pop
스택이름.pop();

가장 최근에 들어온 데이터를 삭제한다.

4) top
스택이름.top();

가장 최근에 들어온 데이터를 return.

5) size
스택이름.size();

스택의 현재 사이즈를 return.

6) swap
swap(스택 1, 스택2);

스택 1 과 스택 2을 바꿔준다.

 

Coding

#include <iostream>
#include <stack>

using namespace std;

int main(int args , char** argv){
    stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);
    cout << "empty(0 is not empty, 1 is empty) : " << s.empty() << endl;
    cout << "size : " << s.size() << endl;
    cout << "stack values : ";
    while(!s.empty()){
        cout << s.top() << ' ';
        s.pop();
    }
    cout << "\n" << "empty(0 is not empty, 1 is empty): " << s.empty() << endl ;    
}

출력 결과