[자료구조] stack- Array based vs Linked List

stack

---

what is stack?

stack은 말 그대로 데이터를 쌓아올리는 형태의 자료구조를 말한다. 접시 100장을 차례대로 쌓거나 책을 쌓는 것 등등으로 이해 가능. 선형구조로 배열, 연결리스트로 구현 가능하다.

---

stack의 특징

• 마지막으로 추가되는 자료가 가장 먼저 나오는 특성을 가진다 -> LIFO라고도 함 (Last In First Out)

  접시 100장을 쌓으면 맨 밑에 있는 접시를 가장 안전하게 뺄 수 있는 방법은 위에서 부터 차례대로 빼서 맨 밑의 접시에 도달하는 방법 밖에 없음

• top 지시자에 한해서만 데이터에 접근 가능 (push, pop 함수 모두)

---

stack class

Array based vs Linked LIst

stack에서 데이터를 쌓을 때 두가지 형태로 쌓을 수 있다. Array based 와 Linked List의 가장 큰 차이는 데이터의 크기를 정하는 시점이다.

• Array based: 데이터의 크기를 정해놓고, 즉 배열의 크기를 미리 정해놓고 연산을 시작한다. 동적할당도 마찬가지로 입력으로 크기를 받아서 미리 데이터의 크기를 정해놓아야 함. 데이터들이 연결되어 있어서 지역성이 좋고 순회에 걸리는 시간이 적음

• Linked List: 데이터를 입력 받을 때 마다 크기를 늘려감. 데이터를 입력 받아 저장하고, 그 데이터의 주소를 가리키는 포인터를 필요로 함. 데이터들이 연결되어 있지 않음. 다음 데이터가 어디에 생길지 모름.

---

Array based Stack implement

class stack {
public:
    stack() {
        top = -1;    // static 구현
    }
    stack(int n) {
        items = new int(n);     // dynamic 생성자
    }
    ~stack() {
        delete[] items;        // dynamic 소멸자
    }

    bool isempty() {
        return (top == -1);
    }
    bool isfull() {
        return (top == max - 1);
    }
    int TOP() {
        return itmes[top];
    }
    int push(int item) {
        if (!isfull()) {
            top++;
            items[top] = item;
        }
    }
    int pop() {
        if (!isempty()) {
            top--;
        }
    }

private:
    int items[max];    // static 구현
    int *items        // dynamic 구현
    int top;
};

member function

• stack() - static 생성자의 역할. top의 값에 -1을 넣어서 초기화를 시켜준다.
• stack(int n) - 동적으로 배열의 크기를 할당할 시 n을 크기로 설정해주는 생성자
• ~stack() - 동적배열을 할당 해제 해주는 소멸자 !! 꼭 필요함 그래야 heap 영역에서 발생하는 메모리 leak을 방지함
• isempty() / isfull() - stack이 비어있는지 차있는지 확인해서 push와 pop함수에서 발생하는 에러를 방지
• TOP() - 가장 맨 위에 있는 데이터를 반환
• push(int) - top의 값을 +1 한 후에 데이터를 저장
• pop() - top의 값을 -1 한다

member data

• items[max] - 배열의 크기를 max로 설정 (static 구현)
• *items - 동적 할당을 위한 변수 (dynamic 구현)
• top - items 데이터에 접근하기 위한 변수

---

Linked List Stack implement

LL로 구현한 stack은 array based에 비해 신경써야할 포인트가 몇가지 있다. 첫째, 포인터의 값 할당 및 해제. 둘째, 데이터 간의 연결이다. 특히 두번째 사항은 pop 연산자를 구현할 때 중요하다. array based stack은 전체 클래스를 만들고 밑에 함수 별 추가설명을 했지만, linked list는 하나하나 살펴보도록 하겠다.

class stack {
public:
    stack();    // 생성자
    ~stack();    // 소멸자
    bool isEmpty() const; 
    bool isFull() const;
    void push(int n);
    void pop();
    int Top();
private:
    Node* top;  // top 데이터의 주소를 가리키는 포인터
};

struct Node {
    int info;    // data를 저장
    Node* next;    // 다음 data의 주소를 가리키는 포인터
};

member function

 

• stack 생성자

    stack() {
        top = NULL;
    }

너무 쉬워서 일단 설명을 간단히 하자면, 맨 처음에는 포인터가 가리킬 데이터가 없기 때문에 null 할당해준다

 

• stack 소멸자

    ~stack() {
        while (!isEmpty()) {
            Node* node;
            node = top;
            top = top->next;
            delete node;
        }
    }

-> stack이 소멸자를 불러오면서 포인터 변수만 없애면 heap영역에 생긴 나머지 data들을 잃어버리게 된다. 따라서 stack이 소멸자를 불러올 때 나머지 데이터들도 다 없애줘야 한다.

-> Node구조체의 node 객체를 만들고 자료구조가 stack이기 때문에 top주소를 대입한다. 그리고 top은 다음 데이터인 top->next를 가리 키도록 한다. 그 다음 node를 지우면 제일 위에 있던 top 데이터를 지운것이 된다. 이를 stack이 empty상태일 때까지 진행한다.

 

• isEmpty

    bool isEmpty() {
        return (top == NULL);
    }

isEmpty 함수도 마찬가지로 매우 쉽기 때문에 간단하게 설명하겠다. stack이 비어있는 상태는 top포인터가 가리키는 주소가 없을 때 이므로 null인지 확인한다.

 

• isFull

    bool isFull() {
        Node* node;
        try {
            node = new Node;
            delete node;
            return false;
        }
        catch(std::bad_alloc){
            return true;
        }
    }

사실 LL로 구현하게 된다면 isFull 함수가 제일 애매한 부분이다. upper limit이 없기 때문에 true를 얻기 힘들고 왠만해서는 오류도 잘 안난다. 굳이굳이 구현하자면 핵심은 객체가 heap에 잘 할당이 된다면 full 상태가 아니고 bad_alloc이라면 full 상태인 것이다.

이를 try catch 구문으로 구현했다. node가 new Node로 할당이 잘 되면 node를 지우고 false를 return 한다. 아니라면 full 상태이므로 true return

(new 사용시 메모리 할당 과정에서 bad_alloc이라는 예외를 만드는 new이다. 자세한 건 bad_alloc에 대해 검색)

 

• push (int n)

    void push(int n) {
        if (!isFull()) {
            Node* node = new Node;
            node->info = n;
            node->next = top;
            top = node;
        }
    }

push 함수도 메인 아이디어는 굉장히 간단하다. 새로운 Node 타입 객체를 만들어준다. 객체의 info에는 추가할 데이터 n을 넣고, 객체의 포인터 값에는 top 주소를 넣어서 객체와 stack의 첫번째 객체가 연결이 되도록 한다.

 

• pop

void pop() {
    if (!isEmpty()) {
        Node* node;
        node = top;
        top = top->next;
        delete node;
    }
}

pop 함수도 간단하다. 포인트는 코드의 순서이다. node에 top의 주소를 넣어준다. 그리고 top은 그 다음 데이터의 주소를 가리키도록 한다. 마지막에 top의 주소가 들어간 node를 지우면 끝. 순서가 바뀌면 데이터를 heap에서 잃어버리고 난리가 나므로 주의해서 써야한다.

 

• Top

    int Top() {
        return top->info;
    }

Top은 너무 쉬우므로 설명 생략.

 

 

 

stack 자료구조는 queue와 더불어서 가장 기본적인 자료구조이므로 이를 잘 알아두면 활용할 곳이 많다.

다음에는 stack을 활용해서 푸는 백준 문제 풀이를 들고오겠다