C++ Stack(스택) 연결 리스트로 구현

Stack

스택의 기본은 top이다.

말그대로 '쌓는' 자료 구조라고 보면 되는데 top(맨 위)에만 놓을 수 있는 것이다.

따라서 top에 원소를 넣고, 추가로 원소를 넣고 싶으면 top을 하나 더 증가 시켜야 한다.

implementation using Linked List

#include <iostream>
 
using namespace std;
 
struct Node {
    int data;
    Node* next;
};
 
Node* top = NULL;
 
void push(int data) {
    Node* node = new Node();
    node->data = data;
    node->next = top;
    top = node;
}
 
void Top() {
    if (top != NULL) {
        cout << "top : " << top->data;
    }
    else {
        cout << "top is NULL";
    }
    cout << endl;
}
 
void pop() {
    if (top == NULL) {
        cout << "stack underflow" << endl;
    }
    else {
        cout << "pop : " << top->data << endl;
        top = top->next;
    }
}
 
void display() {
    Node* ptr;
    if (top == NULL) {
        cout << "stack is empty";
    }
    else {
        ptr = top;
        cout << "stack element : ";
        while (ptr != NULL) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
    cout << endl;
}
 
int main() {
 
    display();
    Top();
 
    push(1);
    push(2);
    push(3);
    
    display();
    Top();
 
    pop();
    pop();
 
    display();
    Top();
 
    push(5);
 
    display();
    Top();
 
    return 0;
}

실행 결과

처음에는 아무 원소도 없으므로 empty 출력

1, 2, 3을 순서대로 넣었으니 현재

3

2

1

top은 가장 마지막에 넣은 3

pop 함수로 top(3) 꺼냄 -> 현재 top은 2

pop 함수로 top(2) 꺼냄 -> 현재 top은 1

스택에 현재 원소는 1밖에 없고 top도 1

5 push -> 현재

5

1

현재 top은 가장 나중에 push한 5가 된다.

추후에 배열도 추가 예정

더 자세한 내용은 tutorialspoint (https://www.tutorialspoint.com/cplusplus-program-to-implement-stack-using-linked-list)