[Stacks]11. Array-based Stack(배열 기반 스택) 구현

목차

1. Array-based Stack(배열 기반 스택) 구현

2. 실제 구현

3. size()

4. empty()

5. top()

6. push()

7. pop()

8. 테스트

 

1. Array-based Stack(배열 기반 스택) 구현

 Array를 기반으로 Stack ADT 알고리즘을 구현할 경우

1. 임의의 크기의 array를 선언한다

2. 해당 array의 0번째 부터 들어오는 element를 저장한다.

3. 현재 위치를 t로 저장하며, 해당 위치에서 element를 호출되는 기능에 따라 추가하고, 삭제한다.

 

 Array를 기반으로 Stack ADT 알고리즘을 구현할 경우, 가장 큰 문제점이 바로 Array의 최대값에 다다랐을 경우입니다. 이와 같은 경우를 ADT에서 설명하지는 않지만, 구현하고자 하려면 Array가 가득 찰 시 더 큰 크기의 Array를 할당하는 방법으로 해결할 수 있습니다.

 

2. 실제 구현

class Stack_array: # 배열을 기반으로 한 스택
    def __init__(self): # 파이썬에서는 list의 크기 제한이 없으므로, 자유롭게 사용한다.
        self.stack = [] # 배열
        self.t = -1 # 초기 top의 index -1로 초기화

 

3. size()

    def size(self)-> int: # 스택의 원소 개수를 반환하는 함수
        return len(self.stack)

 

4. empty()

    def empty(self)-> bool: # 스택이 비었는지 확인하는 함수
        return len(self.stack) == 0

 

5. top()

    def top(self)-> int: # 스택의 맨 위 원소를 확인하는 함수
        if self.empty(): # 스택이 비어있다면
            return -1
        else:
            return self.stack[self.t] # index t의 값 반환

 

6. push()

    def push(self, n: int): # 스택의 새로운 값을 push하는 함수
        self.stack.append(n) # python은 리스트의 크기 제한이 없으므로, 바로 append
        self.t += 1 # top index + 1 하기

 

7. pop()

    def pop(self)-> int: # 스택의 top의 값을 삭제하고 반환하는 함수
        if self.empty(): # 스택이 비어있다면
            return -1
        else:
            self.t -= 1 # top index - 1 하기
            return self.stack.pop(-1) # pop함수 실행

 

8. 테스트

if __name__ == "__main__": # 테스트 케이스
    stack = Stack_array()
    print('made stack')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()
    
    stack.push(1)
    print('push 1')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()
    
    stack.push(2)
    stack.push(3)
    stack.push(4)
    print('push 2, 3, 4')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()
    
    print('pop')
    print(f'stack.pop: {stack.pop()}')
    print(f'stack.empty: {stack.empty()}')
    print(f'stack.size: {stack.size()}')
    print(f'stack.top: {stack.top()}')
    print()

 

이에 따른 출력 값:

'''
made stack
stack.empty: True
stack.size: 0
stack.top: -1

push 1
stack.empty: False
stack.size: 1
stack.top: 1

push 2, 3, 4
stack.empty: False
stack.size: 4
stack.top: 4

pop
stack.pop: 4
stack.empty: False
stack.size: 3
stack.top: 3
'''

 

전체 코드는 github에 올려두었습니다.

github.com/imgzon3/algorithm/blob/main/Stack/stack_array.py

imgzon3/algorithm