자료구조 - 스택(stack)

언어는 python을 사용하였습니다.

3. 스택(Stack)

• 스택은 데이터를 임시 저장할 때 사용하는 자료구조로서, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 입니다.
• 기본적으로 가장 나중에 넣은 데이터를 가장 먼저 뺄수있는 LIFO(Last- in, First-Out) 구조 입니다.

삽입 삭제

• 데이터를 스택에 넣기 push()
• 데이터를 스택에서 빼기 pop()

장, 단점

• (장점) 구조가 단순해서 구현하고 쉽고, 덕분에 데이터의 저장 읽기 속도가 빠르다
• (단점) 데이터의 갯수를 미리 정해 그에따른 저장공간을 확보해야 한다, 따라서 공간의 낭비가 발생할수도 있다.
• 파이썬의 경우 재귀 함수는 최대 1000번까지만 호출이 가능하다.

파이썬 리스트를 통한 스택 구현

#리스트 생성
data_stack = list() 

#append 함수를 통한 데이터 push
data_stack.append(1)
data_stack.append(2)

#pop 함수를 통한 데이터 pop
data_stack.pop()

스택의 대표적인 예시 재귀함수

def recursive(data):
    if data<0:
        print("END")
    else:
        print(data)
        recursive(data-1)
        print("returned", data)

# recursive(2) 입력시 출력
2
1
0
END
returned 0
returned 1
returned 2

리스트를 통한 stack 기능 구현

# 리스트 생성
stack_list = list() 
# 리스트에 데이터 삽입
def push(data):
    stack_list.append(data)
# 리스트에서 데이터 뽑기
def pop():
    data = stack_list[-1] # 리스트에서 -1 은 항상 가장 마지막의 원소를 의미 
    del stack_list[-1] # 가장 마지막  data를 뽑은 후에는 비워줘야 하므로 del 를 통해 가장 마지막 원소 삭제
    return data

References

Do it! 점프 투 파이썬
Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬편
잔재미코딩