C++ Fundamentals of Data Structures(C++ 자료구조론) 4.6 링크드 스택, 링크드 큐

[linkedStack]

/*

링크드리스트를 이용해서 스택을 구현했습니다

*/

#include <iostream>

using namespace std;

 

template <typename T> class LinkedStack;

 

template <typename T>

class ChainNode //기존에 정의한 ChainNode 클래스 그대로 사용함

{

private:

        T data;

        ChainNode<T> *link;

public:

        ChainNode(T element = 0, ChainNode *next = NULL) :data(element), link(next)

        {

        }

        /*

        T getData()

        {

        return data;

        }

        ChainNode *Link()

        {

        return link;

        }

        */

        friend LinkedStack<T>;

        template <typename T>

        friend ostream &operator<<(ostream &os, LinkedStack<T> &ls);

};

 

template <typename T>

class LinkedStack

{

private:

        ChainNode<T> *top;

public:

        LinkedStack()

        {

               top = NULL;

        }

        bool isEmpty()

        {

               return top == NULL; //비어있는지 확인

        }

        void Push(const T &item)

        {

               top = new ChainNode<T>(item, top);

               cout << item << "이 추가되었습니다" << endl;

        }

        void Pop()

        {

               ChainNode<T> *delNode = top;

               cout << top->data << "가 삭제되었습니다" << endl;

               top = top->link;

               delete delNode;

        }

        T &Top()

        {

               return top->data; //top 반환

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, LinkedStack<T> &ls);

};

 

template <typename T>

ostream &operator<<(ostream &os, LinkedStack<T> &ls)

{

        ChainNode<T> *cur = ls.top; //Pop에 영향을 주지 않기 위해

        while (1)

        {

               if (cur->link == NULL)

               {

                       os << cur->data;

                       break;

               }

               os << cur->data << "->";

               cur = cur->link;

        }

        os << endl;

        return os;

}

 

int main(void)

{

        LinkedStack<int> intLS;

        for (int i = 0; i < 5; i++)

               intLS.Push(i + 1);

        cout << "스택 출력" << endl;

        cout << intLS;

        cout << "Top: " << intLS.Top() << endl;

        for (int i = 0; i < 5; i++)

               intLS.Pop();

        return 0;

}

 

[linkedQueue]

/*

링크드리스트를 이용해서 큐를 구현했습니다

*/

#include <iostream>

using namespace std;

 

template <typename T> class LinkedQueue;

 

template <typename T>

class ChainNode //기존에 정의한 ChainNode 클래스 그대로 사용함

{

private:

        T data;

        ChainNode<T> *link;

public:

        ChainNode(T element = 0, ChainNode *next = NULL) :data(element), link(next)

        {

        }

        /*

        T getData()

        {

        return data;

        }

        ChainNode *Link()

        {

        return link;

        }

        */

        friend LinkedQueue<T>;

        template <typename T>

        friend ostream &operator<<(ostream &os, LinkedQueue<T> &lq);

};

 

template <typename T>

class LinkedQueue

{

private:

        ChainNode<T> *front;

        ChainNode<T> *rear;

public:

        LinkedQueue()

        {

               front = rear = NULL;

        }

        bool isEmpty()

        {

               return (front == NULL && rear == NULL);

        }

        T &Front()

        {

               return front->data;

        }

        T &Rear()

        {

               return rear->data;

        }

        void Enqueue(const T &item)

        {

               if (isEmpty())

               {

                       cout << item << "추가" << endl;

                       front = rear = new ChainNode<T>(item, 0); //empty queue

               }

               else

               {

                       cout << item << "추가" << endl;

                       rear = rear->link = new ChainNode<T>(item, 0); //rear에 추가 InsertRear

               }

        }

        void Dequeue()

        {

               if (isEmpty())

               {

                       cout << "큐는 비어있다. 더 이상 Dequeue 불가" << endl;

                       return;

               }

               ChainNode<T> *delNode = front;

               cout << front->data << "삭제" << endl;

               front = front->link;

               delete delNode;

        }

        template <typename T>

        friend ostream &operator<<(ostream &os, LinkedQueue<T> &lq);

};

 

template <typename T>

ostream &operator<<(ostream &os, LinkedQueue<T> &lq)

{

        ChainNode<T> *cur = lq.front;

        while (1)

        {

               if (cur == lq.rear)

               {

                       os << cur->data << " ";

                       break;

               }

               os << cur->data << "->";

               cur = cur->link;

        }

        os << endl;

        return os;

}

 

int main(void)

{

        LinkedQueue<int> intLQ;

        for (int i = 0; i < 5; i++)

               intLQ.Enqueue(i + 1);

        cout << "큐 출력" << endl;

        cout << intLQ;

        cout << "Front: " << intLQ.Front() << endl;

        cout << "Rear: " << intLQ.Rear() << endl;

        for (int i = 0; i < 5; i++)

               intLQ.Dequeue();

        return 0;

}

 

[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서

*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.