[자료구조] 스택(Stack)

스택(Stack)

Stack은 데이터를 제한적으로 접근할 수 있는 구조이며 입력과 출력이 한쪽 끝에서만 발생한다. 즉 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조이다. LIFO (Last In First Out)

구조가 단순하고 구현이 쉽지만 데이터의 최대 허용 개수를 미리 정해야 하며 이로인한 저장 공간의 낭비가 발생할 수 있다.  (파이선의 경우 재귀 호출은 1000번까지만 가능하다.) 

---

Stack의 기본적인 구현

파이선의 list 클래스의 메서드로 아주 간단하게 Stack을 구현할 수 있다. 

// 파이선 리스트에서 지원하는 메서드로 스택 만들기
// Push : append()
// Pop : pop()

data_stack = list()

data_stack.append(1)
data_stack.append(2)

data_stack	
// 출력 : [1, 2]

data_stack.pop()
// 출력 : 2

---

List 변수로 Stack을 다루는 Push, Pop 기능의 직접 구현

아래와 같이 push와 pop을 직접 구현해볼수도 있다. push는 append()를 그대로 사용 할 수 있다. 

pop 함수에서는 마지막 값을 리턴하되 사용된 마지막 값을 삭제해줘야 한다.

stack_list = list()

def push(data):
    stack_list.append(data)
    
def pop():
    data = stack_list[-1]	// [ ]에 -1을 입력하면 리스트의 가장 마지막 값이 나온다.
    del stack_list[-1]
    return data
    
// 스택에 0~9 입력
for index in range(10):
    push(index)
    
    
pop()		// 9
pop()		// 8
pop()		// 7
pop()		// 6
pop()		// 5