✔ Stack 개념 이해✍

SWExperAcademy Stack

◽ stack이란?

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조임
• 스택에 저장된 자료는 선형구조(자료 간의 관계가 1:1의 관계) 를 가짐
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있음
• 마지막에 삽입한 자료를 가장 먼저 꺼냄
• 후입선출(LIFO, last-In-First-Out)이라고 부름
  ex) 1,2,3 순으로 자료를 삽입한 후 꺼내면 역순으로 3,2,1순으로
  꺼낼 수 있음

◽ 자료구조

자료를 선형을 저장할 저장소가 필요함

• 파이썬에서는 리스트를 사용할 수 있음
• 저장소 자체를 스택이라 부르기도 함
• 스택에서 마지막 삽입된 원소의 위치를 top이라 부름

◽ 연산

• 삽입 : 저장소에 자료를 저장하고 보통 push라고 부름
• 삭제: 저장소에서 자료를 꺼냄 보통 pop
• isEmpty: 스택이 공백인지 아닌지를 확인하는 연산
• peek: 스택에 top에 있는 item(원소)을 반환하는 연산

# push
def push(item):
s.append(item)

# pop
def pop():
  if len(s) ==0 : //스택이 비워있는 경우임 
  # underflow
  return
  else:
  	return  s.pop(-1)  // 마지막 값을 삭제하고 return 받음 

스택 구현해보기

def push(item):
	s.append(item)
def pop():
    if len(s) ==0:
        print('Stack is Empty!!') 
        return
    else:
    	return s.pop(-1)
s= []
push(1)
push(2)
push(3)
print("pop item =>" , pop())
print("pop item =>" , pop())
print("pop item =>" , pop())

리스트를 사용하여 스택을 구현하는 경우
=> 리스트의 크기를 변경하는 작업은 내부적으로 큰 overhead 발생
작업으로 많은 시간이 필요함.

🤗따라서 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해놓고 사용하거나 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현해야함!

stack 응용

피보나치 수를 DP에 적용한 알고리즘

def fibo2(n):
	f =[0,1]
    for i in range(2,n+1):
    	f.append(f[i-1]+f[i-2])
    return f[n]

DFS(깊이 우선 탐색)

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 (깊이 우선 탐색, 너비 우선 탐색)

1. 깊이 우선 탐색

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
• 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
• 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용