스택(Stack) 자료구조

스택(Stack)이란?

스택은 데이터를 후입선출(First-In Last-Out) 방식으로 저장하는 자료구조이다. 데이터를 제한적으로 접근 할 수 있는 구조이며, 한쪽 긑에서만 자료를 넣거나 뺄 수 있는 구조이다.

 

스택은 콜 스택(Call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조로써 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(Stack Buffer Overflow)라고 부른다. 프로그래밍 관련 질의응답 사이트인 스택오버플로의 명칭도 여기서 유래했다.

 

스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조로서, 스택과 연관된 알고리즘을 제대로 이해하느냐 못하느냐에 따라 기본 알고리즘을 설계할 수 있느냐 없느냐가 결정되기도 한다.

 

배열을 이용한 스택의 구현

스택 구조

• 스택은 LIFO 또는 FILO의 데이터 관리 방식을 따름
• 대표적인 스택의 활용: 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 주요기능
  • push(): 데이터를 스택에 넣기
  • pop(): 데이터를 스택에서 꺼내기
• 스택의 크기: 스택에 쌓을 수 있는 데이터의 최대 개수

 

스택의 push()

스택의 pop()

스택의 장단점

장점

• 구조가 단순해서 구현이 쉽다.
• 데이터 저장/읽기 속도가 빠르다.

단점 (배열로 스택 구현시)

• 데이터 최대 갯수를 미리 정해야 한다.
• 저장 공간의 낭비가 발생한다. -> 미리 최대 갯수만큼 저장공간을 확보해야 함

스택의 경우 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.

이 경우, 위에서 열거한 단점이 있을 수 있다.

 

C# 예제 코드

namespace testProject
{
    class Stack<T>
    {
        private T[] array;
        int top;

        public Stack(int size)
        {
            array = new T[size];
            top = -1;
        }

        public bool IsEmpty()
        {
            return top == -1;
        }

        public void Push(T item)
        {
            array[++top] = item;
        }

        public T Pop()
        {
            return array[top--];
        }
    }
}

 

참조 사이트

알고리즘 - 자료구조(1) 스택, 큐

[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법