[Section 3] 스택 알고리즘 _ 배열 스택(Array Stack)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

배열 스택(Array Stack)은 스택 중에서 가장 구현이 쉽고 간단하다는 특징을 가지고 있다. 이번에는 배열 스택 알고리즘을 구현하기 위해 필요한 ADT를 정리하고, 그 알고리즘을 구현화해보자.

1.  배열 스택 ADT 정리

스택 배열의 구현은 가장 먼저 팝과 푸쉬에 있다. 배열에 데이터를 삽입하고 삭제하는 기능이 주 ADT라 할 수 있겠다. 그리고 보조 ADT는 스택의 사이즈 혹은 탑 포인터의 위치 반환, 데이터가 비어있는지 확인하는 기능, 그리고 스택이 가득 차있는지 확인하는 기능 등을 구현하는 것이 기본이다. 

 

여기에서는 가장 단순한 배열을 기본으로 스택을 구현하고자 한다. 스택의 구현을 하기 전에 가장 먼저 스택의 기본 배열 구조를 알고 넘어가자. 배열 스택은 다음과 같은 리스트 구조로 구현된다.  

 

배열 스택의 구조

 

이곳에서는 위 구조를 기본으로 하여 왼쪽에서 오른쪽으로 차례로 데이터의 삽입 과정을 확인하고, 이 과정에서 탑 인덱스가 어떻게 변화하는지 확인하고자 한다.

2.  배열 스택 알고리즘 _ 데이터의 팝과 푸쉬

배열 스택을 위한 기본 알고리즘은 다음과 같다.

 

예시 코드:

class StackA:
    def __init__(self,limit=None):
        self.S=[]
        self.L=limit
    def push(self,data):
        if len(self.S) >= self.L:
            print("Overflow: Stack")
        else:
            self.S.append(data)
    def pop(self):
        if len(self.S) <= 0:
            print("Underflow: Stack")
            return 0
        else:
             return self.S.pop()

 

코드 결과:

코드 결과

 

* 배열 스택은 먼저 들어간 게 끝에서 삭제되는 구조이므로 FILO 리스트라고 할 수 있다.

 

3.  배열 스택 알고리즘 _ 끝 데이터 반환과 배열 사이즈 확인 기능

보조 ADT 중 배열의 끝에 있는 데이터를 반환하는 기능과 사이즈 확인 기능을 다음과 같이 추가하도록 하자.

 

예시 코드:

    def LastD(self):
        if len(self.S) <= 0:
            print("Underflow: Stack")
            return 0
        else:
            return self.S [-1]
    def size(self):
        return len(self.S)

 

코드 결과:

코드 결과

 

* 시간 복잡도 분석하기 _ 스택 사이즈가 n인 경우

 

배열 스택의 시간 복잡도는 모든 ADT가 O(1)이다. 하지만, 공간 복잡도는 O(n)이다.