[자료구조] 스택(Stack) - 링크드 리스트를 이용한 구현

스택(Stack)

스택 이란?

• 가장 마지막에 들어간 데이터가 제일 먼저 나온다 (Last In - First Out) LIFO
• 가장 먼저들어간 데이터는 가장 나중에 나온다 (First In - Last Out) FILO
• 변수를 선언 후 수명주기가 끝나면 자동으로 제거해주는 메모리도 스택으로 구현되어 있다.

스택의 주요 기능

헤드의 앞부분에 노드를 삽입 해준다.

존재하는 노드의 뒤쪽에 추가를 하는게 아닌 헤드의 앞쪽에 삽입 해준다.

위의 이미지는 싱글 링크드 리스트를 이용하여 스택을 구현한 그림이다.

처음 데이터를 헤드앞부분에 추가를 해주고 그다음 들어오는 데이터 또한 헤드 앞부분에 추가를 해준다.

그럼 처음 들어온 데이터는 자연히 뒤쪽으로 가게 되며 나중에 들어온 데이터는 헤드의 다음노드를 가르키는 포인터가

자연히 첫 데이터가 된다. 이를 이용하여 스택의 기능을 구현 할 수가 있다.

• 삽입
• 제거

링크드 리스트를 이용한 스택 클래스

#include <iostream>
 struct StackNode
{
    int Data;
    StackNode* Next;
};

class MyStack
{
public:
    MyStack();
private:
    StackNode* Head;

public:

    int Pop();
    void Push(const int& NewData);
    bool IsEmpty();
    void Clear();
    void Show();
};

저는 단순히 구조체를 이용했지만 노드를 클래스화 하고 프렌드를 사용해도 똑같을 것 이다.

링크드 리스트를 이용한 스택  삽입

위 그림처럼 헤드 앞부분에 삽입을 해주어야 한다.

그래야 스택처럼 먼저 들어온 데이터는 뒤쪽에 저장이되고 나중에 들어온 데이터를 헤드의 다음노드를 가르키는 부분부터 참조하여 먼저 빼낼 수 가 있다.

새로운 데이터를 삽입하여 적용 된 링크트 리스트의 그림

void MyStack::Push(const int& NewData)
{
    StackNode* NewNode = new StackNode();
    NewNode->Data = NewData;
    NewNode->Next = Head->Next;
    Head->Next = NewNode;
}

링크드 리스트를 이용한 스택  제거

스택에서 Pop은 제일 마지막에 들어온 데이터를 제거해준다.

위의 그림에서 제일 마지막에 들어온 데이터는 30을 가진 노드이다. 이 노드를 삭제 하기전에

헤드의 다음노드를 가르키는 포인터를 삭제되는 다음 노드를 가르키는 포인터쪽에 재설정을 해주어야 한다.

그럼 위의 그림처럼 30을 가진 데이터는 빠져나가고 순서대로 10의 데이터 20의데이터를 가진 리스트를 볼 수 있다.

int MyStack::Pop()
{
    if (!IsEmpty())
    {
        if (Head->Next != nullptr)
        {
            StackNode* RemoveNode = Head->Next;
            Head->Next = RemoveNode->Next;
            int Data = RemoveNode->Data;
            delete RemoveNode;
            return Data;
        }
    }
    return -1;
}

 

링크드 리스트를 이용한 스택  전체 제거

void MyStack::Clear()
{
    if (IsEmpty())
    {
        std::cout << "데이터가 없습니다" << std::endl;
        return;
    }

    StackNode* CurrentNode = Head;
    StackNode* RemoveNode = nullptr;

    while (CurrentNode->Next != nullptr)
    {
        RemoveNode = CurrentNode->Next;
        CurrentNode->Next = RemoveNode->Next;

        int Data = RemoveNode->Data;
        std::cout << Data << "삭제" << std::endl;

        delete RemoveNode;
    }
}

메인 코드

int main()
{
    MyStack* Stack = new MyStack();
    Stack->Push(1);
    Stack->Push(2);
    Stack->Push(3);
    Stack->Pop();
    Stack->Show();
    Stack->Clear();
}

Push함수를 통해 1,2,3을 집어넣으면 리스트엔 헤드부분 부터 3,2,1 순으로 저장되어있다.

그리고 Pop함수를 호출하면 3이 빠져나가고 2,1이 저장되거 있을 것 이다.

이를 Show함수를 통해 출력하면 2,1이 출력되고 Clear함수를 통해 리스트의 데이터를 지워버리면

헤드의 앞부분 부터 차례대로 지워질 것 이다.