Stack [c++]

stack개념

stack에서의 삽입/삭제은 오로지 stack의 꼭대기에서만 이루어집니다. stack 가운데에 있는 데이터를 삭제하거나 새로운 데이터를 삽입하는 것은 불가능합니다. 스택의 가장 아래에 있는 데이터를 꺼내려면 그 위에 있는 데이터를 모두 꺼내야 합니다.

---

stack특징

-LIFO(Last In - First Out)
-FILO(First In - Last Out)

---

c++로 구현한 array Stack

#include <iostream>
using namespace std;
template <typename T>
struct Node {
        T data;
};
template <typename T>
class ArrayStack{
        private:
                Node<T>* nodes_;
                int capacity_;
                int top_;

        public:
                ArrayStack();
                ~ArrayStack();
                ArrayStack(int capacity);

                void push(T newData);
                void pop();
                T top();
                int getSize();
                bool isEmpty();
                void printAll();
};
template <typename T>
ArrayStack<T>::ArrayStack():nodes_(nullptr), top_(-1), capacity_(0){}
template <typename T>
ArrayStack<T>::~ArrayStack(){
        delete nodes_;
}
template <typename T>
ArrayStack<T>::ArrayStack(int capacity){
        capacity_ = capacity;
        top_ = -1;
        nodes_ = (Node<T>*)malloc(sizeof(Node<T>)*capacity_);
}
template <typename T>
void ArrayStack<T>::push(T newData){
        if (capacity_ == top_){
                capacity_ *= 2;
                nodes_ = (Node<T>*)realloc(nodes_, sizeof(Node<T>)*capacity_);
        }
        nodes_[++top_].data = newData;
}
template <typename T>
void ArrayStack<T>::pop(){
        cout << "pop : " << nodes_[top_--].data << endl;
}
template <typename T>
T ArrayStack<T>::top(){
        return nodes_[top_].data;
}
template <typename T>
int ArrayStack<T>::getSize(){
        return top_ + 1;
}
template <typename T>
bool ArrayStack<T>::isEmpty(){
        return top_ == -1;
}
template <typename T>
void ArrayStack<T>::printAll(){
        cout << "bottom -> ";

        for (int i=0;i<=top_;i++){
                cout << nodes_[i].data << " -> ";
        }

        cout << "top" << endl;
}
int main(){
        ArrayStack<int>* arrayStack = new ArrayStack<int>(10);
        for (int i=0;i<5;i++){
                arrayStack->push(i+1);
        }
        arrayStack->printAll();
        while (!(arrayStack->isEmpty())){
                arrayStack->pop();
        }
        arrayStack->printAll();
}

출력 결과
bottom -> 1 -> 2 -> 3 -> 4 -> 5 -> top
pop : 5
pop : 4
pop : 3
pop : 2
pop : 1
bottom -> top

---

c++로 구현한 linked list Stack

#include <iostream>
using namespace std;
template <typename T>
struct Node{
        T data;
        struct Node* next;
};
template <typename T>
class Stack{
        private:
                Node<T>* top_;
                int size_;
        public:
                Stack();
                ~Stack();

                Node<T>* createNode(T newData);
                void destroyNode(Node<T>* node);
                void pop();
                T top();
                void push(Node<T>* newNode);
                int getSize();
                bool isEmpty();
                void printAll();
};
template <typename T>
Stack<T>::Stack():top_(nullptr), size_(0){};
template <typename T>
Stack<T>::~Stack(){
        Node<T>* current = top_;

        while (current != nullptr){
                Node<T>* temp = current;
                current = current->next;
                destroyNode(temp);
        }
}
template <typename T>
Node<T>* Stack<T>::createNode(T newData){
        Node<T>* newNode = new Node<T>;

        newNode->data = newData;
        newNode->next = nullptr;

        return newNode;
}
template <typename T>
void Stack<T>::destroyNode(Node<T>* node){
        node->next = nullptr;
        delete node;
}
template <typename T>
void Stack<T>::pop(){
        Node<T>* temp = top_;
        top_ = top_->next;

        cout << "pop : " << temp->data << endl;

        destroyNode(temp);
        size_--;
}
template <typename T>
T Stack<T>::top(){
        return top_->data;
}
template <typename T>
void Stack<T>::push(Node<T>* newNode){
        if (top_ == nullptr){
                top_ = newNode;
        }
        else {
                newNode->next = top_;
                top_ = newNode;
        }
        size_++;
}
template <typename T>
int Stack<T>::getSize(){
        return size_;
}
template <typename T>
bool Stack<T>::isEmpty(){
        return top_ == nullptr;
}
template <typename T>
void Stack<T>::printAll(){
        Node<T>* current = top_;

        cout << "top -> ";
        while (current != nullptr){
                cout << current->data << " -> ";
                current = current->next;
        }
        cout << "bottom" << endl;
}
int main()
{
        Stack<int>* myStack = new Stack<int>;
        Node<int>* newNode = new Node<int>;
        for (int i=0;i<3;i++){
                newNode = myStack->createNode(i+1);
                myStack->push(newNode);
        }

        cout << "Stack에 저장된 노드의 수 : " << myStack->getSize() << endl;
        myStack->printAll();

        for (int i=0;i<3;i++){
                newNode = myStack->createNode(i+4);
                myStack->push(newNode);
        }
        cout << "Stack에 저장된 노드의 수 : " << myStack->getSize() << endl;
        myStack->printAll();

        for (int i=myStack->getSize()-1;i>=0;i--){
                myStack->pop();
        }
        cout << "Stack에 저장된 노드의 수 : " << myStack->getSize() << endl;
        myStack->printAll();
}

출력
Stack에 저장된 노드의 수 : 3
top -> 3 -> 2 -> 1 -> bottom
Stack에 저장된 노드의 수 : 6
top -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> bottom
pop : 6
pop : 5
pop : 4
pop : 3
pop : 2
pop : 1
Stack에 저장된 노드의 수 : 0
top -> bottom

---