[DS] 연결리스트(Linked list)를 이용한 스택(Stack)

 

↓↓↓        연결 리스트(Linked list)와 스택(stack) 먼저 공부하기      ↓↓↓

 

https://yyyeji.tistory.com/360

[DS] 스택(Stack)이란?

 

https://yyyeji.tistory.com/365

[DS] 연결 리스트(Linked List)란?

 

 

 

연결 리스트(linked list)를 이용한 스택(stack)을 구현하기 위한 ADT 정의

---

class node{
public:
    string name;
    double score;
    node *link;
    void set_data(string n, double d);
};

데이터와 포인터를 포함한 node 클래스를 만들어줍니다.

포인터는 node 클래스를 가르키기 때문에 node type으로 정의합니다.

 

 

class linked_stack {
    node *top;
public:
    linked_stack();
    void push(node t);
    node pop();
    bool stack_empty();
};

linked_stack - 연결 리스트(linked list)를 생성한 초기 상태

push - stack에 원소 한 개 추가

pop - stack에서 원소 한 개 제거

stack_empty - 현재 stack이 empty인지에 대한 상태 확인

 

 

 

함수 구현

---

void node::set_data(string n, double d) {
    name = n;
    score = d;
}

node class의 data를 셋팅(setting)해주는 메소드(method)입니다.

 

 

linked_stack::linked_stack() {
    top = NULL;
}

linked stack class의 생성자(constructor)에서는 top을 NULL로 초기화시켜 줍니다.

 

 

void linked_stack::push(node t) {
    node *p;
    p = new node;
    (*p) = t;

    p->link = top;
    top = p;
}

스택(stack)에서는 top에서만 원소가 추가되거나 제거되기 때문에 top만 신경 써주면 됩니다.

새로운 원소가 추가될 때 new node의 link는 top에 연결해주고 top에는 new node를 넣어줍니다.

 

 

node linked_stack::pop() {
    node tmp;
    node *t;

    t = top;
    tmp = *top;

    top = top->link;
    delete t;

    return tmp;
}

top = top->link;

현재 top의 위치가 연결리스트(linked list)의 앞에 있기 때문에 node가 하나 제거될 때 t

op은 top과 연결된 node의 link를 따라가야 됩니다.

 

 

bool linked_stack::stack_empty() {
    if(top == NULL) return true;
    else return false;
}

stack_empty는 연결 리스트(linked list)로 구현된 스택(stack)이 empty 상태인지 확인하는 함수입니다.

현재 top이 NULL이면 true를 return 해줍니다.

 

 

 

main 함수 구현

---

int main() {
    linked_stack ls;
    node tmp;

    tmp.set_data("A", 100);
    ls.push(tmp);
    tmp.set_data("B", 90);
    ls.push(tmp);
    tmp.set_data("C", 80);
    ls.push(tmp);
    tmp.set_data("D", 70);
    ls.push(tmp);

    tmp = ls.pop();
    cout << tmp.name << " : " << tmp.score << endl;
    tmp = ls.pop();
    cout << tmp.name << " : " << tmp.score << endl;
}

원소가 제거될 때 최근에 들어간 원소가 제거되기 때문에 결과가 제대로 출력된 것을 확인할 수 있습니다.

 

 

 

◡̈