연결 리스트를 이용한 스택 구현

2022.04.22 - [C++/자료구조] - 배열을 이용한 스택 구현

연결 리스트를 이용한 스택 구현

위에서는 스택을 배열을 이용하여 구해보았다. 

스택은 아래와 같이 연결리스트를 이용하여도 구현할 수 있다. 

이러한 스택을 linked stack이라고 한다. 

장점: 크기가 제한되지 않는다

단점: 동적 메모리 할당이나 해제를 해야 하므로 삽입이나 삭제 시간이 좀 더 걸린다. 

 

각각 파란색으로 표시된 할당된 공간을 노드라 한다.

노드엔 data 값과 다음 노드의 주소값을 가리키는 포인터가 들어 있다

 

 

 

그림은 linked stack의 PUSH와 POP연산을 그림으로 표현한 것이다. . 

PUSH

 

POP

 

 

삽입 연산에서는 먼저 동적 메모리 할당으로 노드를 만들고 이 노드를 첫 번째 노드로 삽입한다.

삭제 연산에서는 top의 값을 바꾸고 기존의 탑이 가리키는 노드를 동적 메모리 해제하면 된다. 

 

 

코드 구현

//linked_stack.h

typedef int element; //int형 자료형에 element라 별칭 붙임.

typedef struct Node
{
    element Data;   //스택 데이터를 정수 타입으로 가정
    Node *Next; //다음 노드를 가리키는 포인터 변수

}node;  //노드는 구조체 타입

class LinkedStack
{
public:
    LinkedStack();  //생성자 함수
    ~LinkedStack(); //소멸자 함수

    void Push(element item);    //item값을 스택에 삽입
    int Pop();                  //스택 탑의 데이터 값을 리턴함
    bool IsEmpty(); //비어 있는지 확인
    bool IsFull();  //꽉차 있는지 확인

private:
    node* Top;  //첫 노드를 가르키는 포인터
};

 

//linked_stack.cpp
#include <iostream>
#include "linked_stack.h"

using namespace std;


LinkedStack::LinkedStack()
{
    Top = nullptr;  //탑 포인터 값을 널로 세팅
}

LinkedStack::~LinkedStack() //소멸자 함수
{
    int Temp;
    while(!IsEmpty())   //스택이 완전히 빌 때 까지
        Temp = Pop();   //계속해서 팝
}

bool LinkedStack::IsEmpty() //스택이 비어있는지 확인하는 함수
{
    return bool(Top == nullptr);    //Top이 Null 이면 True
}

bool LinkedStack::IsFull()  //꽉차 있는지 확인
{
    return !IsEmpty();    //isEmpty 함수가 True면 False
}


void LinkedStack::Push(element item)    //스택의 삽입 함수
{
    node *NewTop = new node;    // 새로운 노드 공간 할당
    NewTop->Data = item;        // 넘어온 데이터 복사
    NewTop->Next = Top;         // 새 노드가 현재 상태의 첫 노드를 가리킨다. 
    Top = NewTop;               // 탑이 새로운 노드를 가리킨다. 
}

element LinkedStack::Pop()
{
    if(IsEmpty())
        cout<<"스택이 비어있습니다."<<endl;
    else
    {
        node* Temp = Top;   //탑 포인터 백업
        element Item = Temp->Data;  //탑 노드의 데이터 백업
        
        Top = Top->Next;    //탑이 다음 노드를 기리키게 한다. 
        delete Temp; // 이전 탑 공간 반납
        return Item; // 이전 탑 데이터 리턴 
    }
}