Algorithm&DataStructure - Stack

1 Stack

https://velog.io/@tiiranocode/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9Dstack-%ED%81%90queue

 

- 한쪽 끝에서만 자료를 컨테이너에 넣고 뺄 수 있다. (LIFO - Last In First Out)

- 최근에 들어간 값이 가장 먼저 나온다.

- 이런 특징으로 다양한 문제 해결에 적용 가능하다.

- 배열 혹은 list를 활용하여 여러 구현이 가능하다.

• S.top(): 스택의 가장 윗 데이터를 반환 
• S.pop(): 스택의 가장 윗 데이터를 삭제
• S.push(): 스택의 가장 위에 데이터 삽입
• S.empty(): 스택이 비었다면 1 반대의 경우 0 반환

2 구현 (vector기반)

- Stack.h

#ifndef __Stack_h_
#define __Stack_h_
#include <vector>
using namespace std;

template <typename T>
class Stack{
private:
    int top;
    vector<T> arr;
public:
    Stack():top(-1){};
    bool isEmpty() const;
    void push(T data);
    T pop();
    T top() const;
    ~Stack(){};
};
#endif

- Stack.cpp

#include "Stack.h"
#include <iostream>

template <typename T>
bool Stack<T>::isEmpty() const {
    if (top == -1) {
        cout<<"스택이 비어있습니다"<<endl;
        return true;
    } else {
        cout<<"스택이 비어있지 않습니다"<<endl;
        return false;
    }
}
template <typename T>
void Stack<T>::push(T data) {
    cout<<data<<" 저장"<<endl;
    arr.push_back(data);
    top++;
}
template <typename T>
T Stack<T>::pop() {
    if(isEmpty()){
        cout<<"삭제할 원소가 없습니다."<<endl;
        return 0;
    }
    cout<<"최상단 원소 제거"<<endl;
    top--;
    T tmp = arr.back();
    arr.pop_back();
    return tmp;
}
template <typename T>
T Stack<T>::top() const{
    if(isEmpty()){
        cout<<"원소가 없습니다."<<endl;
        return 0;
    }
    cout<<"최상단 원소 엿보기"<<endl;
    return arr.back();
}

- main.cpp

#include "Stack.h"
#include "Stack.cpp"

int main(){
    Stack<int> stack;
    stack.isEmpty();

    stack.push(1);
    stack.push(2);
    stack.push(3);

    stack.isEmpty();

    stack.top();
    stack.pop();
    stack.top();

    return 0;
}

3 구현 (list기반)

- Stack.h

#ifndef __Stack_h_
#define __Stack_h_
#include <list>
using namespace std;

template <typename T>
class Stack{
private:
    int top;
    list<T> linkedList;
public:
    Stack():top(-1){};
    bool isEmpty() const;
    void push(T data);
    T pop();
    T top() const;
    ~Stack(){};
};
#endif

- Stack.cpp

#include "Stack.h"
#include <iostream>

template <typename T>
bool Stack<T>::isEmpty() const {
    if (top == -1) {
        cout<<"스택이 비어있습니다"<<endl;
        return true;
    } else {
        cout<<"스택이 비어있지 않습니다"<<endl;
        return false;
    }
}
template <typename T>
void Stack<T>::push(T data) {
    cout<<data<<" 저장"<<endl;
    linkedList.push_back(data);
    top++;
}
template <typename T>
T Stack<T>::pop() {
    if(isEmpty()){
        cout<<"삭제할 원소가 없습니다."<<endl;
        return 0;
    }
    cout<<"최상단 원소 제거"<<endl;
    top--;
    T tmp = linkedList.back();
    linkedList.pop_back();
    return tmp;
}
template <typename T>
T Stack<T>::top() const{
    if(isEmpty()){
        cout<<"원소가 없습니다."<<endl;
        return 0;
    }
    cout<<"최상단 원소 엿보기"<<endl;
    return linkedList.back();
}

- main.cpp

#include "Stack.h"
#include "Stack.cpp"

int main(){
    Stack<int> stack;
    stack.isEmpty();

    stack.push(1);
    stack.push(2);
    stack.push(3);

    stack.isEmpty();

    stack.top();
    stack.pop();
    stack.top();

    return 0;
}