C# 자료구조 (스택2)

전 페이지에서는 배열을 활용한 스택 구조를 구현했으니 이번엔 링크드 리스트를 이용해 구현해 보겠다.

 

일단 그림을 보고 시작하자.

 

 

링크드 리스트를 이용한 스택 출처 C#으로 이해하는 자료구조

 

링크드 리스트는 가장 최근에 넣은 top 노드와 다음 노드를 가르키는 Next 포인터가 있는데

Next가 가르켜야 하는 노드는 top에다 또 노드를 넣으면 방금 넣었던 노드를 top으로 바꾸고 top.Next에다 아까 전

top 노드를 가르키는 방식이다.

 

코드로 구현해보겠다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StackLinkedList
{
    class Node<T>
    {
        public T data;
        public Node<T> Next { get; set; }

        public Node(T data)
        {
            this.data = data;
            Next = null;
        }
    }

    class StackUsingLinkedList<T>
    {
        Node<T> top;
        private int count;

        public StackUsingLinkedList()
        {
            top = null;
            count = 0;
        }

        public void Push(T data)
        {
            if (count == 0)
            {
                top = new Node<T>(data);
                count++;
            }
            else
            {
                Node<T> node = new Node<T>(data);

                node.Next = top;
                top = node;
                count++;
            }
        }

        public T Pop()
        {
            if (count == 0)
            {
                throw new ApplicationException("Empty");
            }

            T data = top.data;

            top = top.Next;

            count--;

            return data;

        }

        public void Peek()
        {
            if (count == 0)
            {
                throw new ApplicationException("Empty");
            }

            Console.WriteLine(top.data);
        }

        public int Count()
        {
            return count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            StackUsingLinkedList<int> stack = new StackUsingLinkedList<int>();

            stack.Push(5);
            stack.Push(4);
            stack.Push(3);
            stack.Push(2);

            stack.Peek();
            Console.WriteLine(stack.Count());

            Console.WriteLine(stack.Pop());
            Console.WriteLine(stack.Pop());

            Console.WriteLine(stack.Pop());
            Console.WriteLine(stack.Pop());
        }
    }
}

 

 

이번엔 객체의 개수를 세는 Count() 기능도 넣어놨다.

 

일단 data와 포인터를 가르킬 Node 클래스를 생성을 한다.

 

그다음은 스택을 구현할 StackUsingLinkedList클래스를 생성하고 기능들을 생성한다.

 

이제는 기능들을 설명해보겠다.

 

Push()

 

Push()는 똑같이 데이터를 넣는것이고 처음에 Count가 0이면 top에다 새로운 노드를 생성시킨후 그 안에다 data를 넣는다.

만약에 Count가 0보다 클때 node라는 Node클래스를 data를 넣고 생성을 한후 node.Next 전 데이터인 top을 넣고 top 포인터를 node를 가르키게 한다.

 

Peek()

 

Peek()메서드는 가장 최근에 넣은 데이터를 출력시키고 Count가 0이면 예외처리를 하고 아니면 top.data를 출력시키게 하였다.

 

Pop()

 

Pop() 메서드는 가장 최근에 넣은 데이터를 빼는것으로 일단 Count가 0이면 예외처리를 하고 아니면 T data를 선언한후 현재 뺴야할 top.data를 할당시킨후 top은 top.Next로 포인터를 가르키게 한후 data를 반환한다.

 

Count()

 

Count()는 현재 스택의 들어있는 데이터 개수를 반환하는 메서드로 데이터를 추가할때나 뺼때 같이 ++,--가 되는 전역변수에다 count를 선언하고 count변수를 반환한다.

 

링크드 리스트는 배열과 다르게 데이터를 무제한으로 넣고 뺄수가 있어서 시간복잡도가 O(1)로 축소되는걸 볼수있다.

 

하지만 C#에서 지원하는 Stack은 원형 배열로 구현 되있다고 한다.