C# 자료구조 (스택)

스택

 

스택은 큐와 비슷한 선형 자료구조이며 마지막에 넣은 데이터를 먼저 꺼내는 Last in First Out 형식이다.

스택의 활용중에 하나는 컴퓨터가 연산자 피연산자를 계산할때 컴퓨터가 읽기 쉬운 후위표기로 변환을 하기위해 사용한다고 한다.

 

 

스택도 큐와 똑같이 배열 또는 링크드리스트로 구현을 하며 스택은 넣을때의 Push() 뺄때의 Pop()형식으로 되어있다.

 

일단 배열을 이용한 스택을 보겠다.

배열을 이용한 스택 출처 C#으로 이해하는 자료구조

 

그림에서는 크기가 고정된 배열을 생성한후 Push() 즉 데이터를 넣을때마다 top 인덱스를 ++시키고 Pop() 데이터를 뺄때

top 인덱스에 있는 데이터를 리턴시키고 top을 --한다.

 

이제 직접 구현을 보겠다.

 

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

namespace StackArray
{
    class StackUsingArray<T>
    {
        int top = -1;
        T[] array;

        public StackUsingArray(int a = 16)
        {
            array = new T[a];
        }


        public void Push(T data)
        {
            if (top == array.Length - 1)
            {
                T[] a = new T[array.Length * 2];

                for(int i = 0; i < array.Length; i++)
                {
                    a[i] = array[i];
                }

                array = a;
            }
            
            top++;
            array[top] = data;
        }
        public void Peek()
        {
         if (top == -1)
            {
                throw new ApplicationException("Empty");
            }
            
            Console.WriteLine(array[top]);
        }
        public T Pop()
        {
            if (top == -1)
            {
                throw new ApplicationException("Empty");
            }

            T data = array[top];
            top--;
            
            T[] a = new T[array.Length - 1];

            for (int i = 0; i < a.Length; i++)
            {
                a[i] = array[i];
            }

            array = a;


            return data;
        }

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

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

            stack.Peek();

        }
    }
}

 

일단 Stack을 구현할 StackUsingArray클래스를 생성하고 아직 가리킬 데이터가 없으니 top변수에는 -1로 해놓고 array배열은 데이터들을 저장할 제네릭 T를 선언을 해놓는다.

 

그다음에 생성자 안에다 배열의 크기를 저장할 파라미터를 미리 16으로 할당해놓고 array에다 크기를 생성한다.

 

이제 기능들을 설명하겠다.

 

Push()

 

Push()는 아까도 말했듯이 데이터를 넣는 메서드로 데이터를 넣을때 top 인덱스를 ++한뒤 data를 array[top]에 할당을한다.

그 다음에 top 변수가 array.Length - 1이랑 같다면 크기를 2배 늘려준 배열을 다시 생성한후 복사한뒤 array배열을 2배 늘려준 배열에다 포인터를 가리키게 한다.

 

Peek()

 

Peek() 메서드는 내가 마지막에 넣었던 데이터를 출력시키는 메서드이다.

 

만약에 스택이 비어있다면 예외처리를 하게 하였다.

 

Pop()

 

Pop()은 최근에 넣은 데이터를 꺼내는 기능으로 스택이 비어있을땐 예외처리를 하고 비어있지 않을땐

T data를 선언하고 현재 top인덱스에 있는 array배열 데이터를 할당하게 하고 그 다음엔 top 변수를 -- 시키고

나중에 또 Push를 할수있으니 array.Length - 1의 배열을 생성하고 그걸 복사한뒤 다시 할당시키게 해놓고

T data를 리턴하는 방식으로 해놓았다.

 

이렇게 설명하면서 배열은 역시 고정된 크기를 가지고 해야되고 데이터를 지울수가 없으니 시간 복잡도가 O(n)이 되는걸 볼수있다.

 

링크드 리스트를 이용한 스택 구현은 다음 페이지에서 해보겠다.