[Data Structure] 연결 스택과 연결 큐

연결 스택 (Linked Stack)

연결 리스트를 사용해 스택을 구현한 것

http://www.btechsmartclass.com/data_structures/stack-using-linked-list.html

스택에 Push 할 때는 새로운 노드의 포인터를 top을 가리키게 해 스택의 맨 위에 올라오게 한 후, 새로운 노드를 top으로 설정한다.
Pop하는 경우 top을 다음 노드로 옮긴 후, 맨 위에 있는 노드를 삭제한다.

코드

#include "../Node.hpp"
#include <iostream>

template <typename T>
class LinkedStack
{
public:
    bool IsEmpty()
    {
        if (top == nullptr) 
            return true;
        else 
            return false;
    }

    Node<T>* Top()
    {
        if (!IsEmpty())
        {
            return top;
        }
        
        std::cout << "Stack is empty\n";
        return nullptr;
    }

    void Push(const T value)
    {
        Node<T>* newNode = new Node(value);

        if (top) 
            newNode->next = top;
        top = newNode;
    }

    void Pop()
    {
        if (IsEmpty())
        {     
            std::cout << "Stack is empty\n";
            return;
        }
        Node<T>* temp = top;
        top = top->next;
        delete temp;
    }

    void Print()
    {
        if (IsEmpty())
        {     
            std::cout << "Stack is empty\n";
            return;
        }
        
        Node<T>* currNode = top;

        while (currNode != nullptr)
        {
            std::cout << currNode->data << "\n";
            currNode = currNode->next;
        }
    }
private:
    Node<T>* top = nullptr;
};

연결 큐 (Linked Queue)

연결 리스트를 사용해 큐를 구현한 것

https://www.scaler.com/topics/c/implementation-of-queue-using-linked-list/

front와 rear를 가지고 있으므로, Push와 Pop 하기 쉽다.

코드

#include <iostream>
#include "../Node.hpp"

template <typename T>
class LinkedQueue
{
public:
    bool IsEmpty()
    {
        if (front == nullptr)
            return true;
        else
            return false;
    }

    Node<T>* Front()
    {
        if (IsEmpty())
        {
            std::cout << "Queue is empty\n";
            return nullptr;
        }

        return front;
    }

    Node<T>* Rear()
    {
        if (IsEmpty())
        {
            std::cout << "Queue is empty\n";
            return nullptr;
        }

        return rear;
    }

    void Push(const T value)
    {
        Node<T>* newNode = new Node(value);

        if (IsEmpty())
        {
            front = rear = newNode;
        }
        else
        {
            rear->next = newNode;
            rear = newNode;
        }
    }

    void Pop()
    {
        if (IsEmpty())
        {
            std::cout << "Queue is empty\n";
            return;
        }

        // front 삭제
        Node<T>* temp = front;
        front = front->next;
        delete temp;
    }

    void Print()
    {
        if (IsEmpty())
        {
            std::cout << "Queue is empty\n";
            return;
        }

        Node<T>* currNode = front;
        while (currNode != nullptr)
        {
            std::cout << currNode->data << " ";
            currNode = currNode->next;
        }
        std::cout << "\n";
    }

private:
    Node<T>* front = nullptr;
    Node<T>* rear = nullptr;
};