[코딩테스트 합격자 되기 06] 스택

스택

스택의 어원은 'stack' , '쌓는다' 이다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 가장 나중에 꺼낼 수 있는 자료구조 이다. 이때 스택에 삽입하는 연산을 푸시 push , 꺼내는 연산을 팝 pop 이라고 한다.

push(1), push(3) 이후 pop(3),pop(1) 예시

 

 

ADT : acstract data type

추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다. 일종의 자료형의 설계도. 

그렇다면 스택은 어떤 정의가 필요한 자료구조일까?

 

언어에 따라 표준 라이브러이에서 스택 제공 여부는 다르다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 'append():가장 마지막에 원소를 넣음' 로 스택을 대체할 수 있다. 덱(deque)은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조 이다. 이런 덱의 특징을 조금만 응용하면 스택처럼 활용할 수 있다. 

 

스택의 ADT

스택에는 푸시, 팝, 가득 찼는지 확인, 비었는지 확인 과 같은 연산을 정의해야 한다. 그리고 최근에 삽입한 데이터의 위치를 저장할 변수인 탑top 도 있어야 한다.

1. push
2. pop
3. isFull 
4. isEmpty 
5. top

이를 표로 정리하면 다음과 같다.

	정의	설명
연산	void push (ItemType item)	스택에 item을 푸시
	ItemType pop ()	최근에 푸시한 item 을 pop 하고 그 데이터를 반환
	Boolean isFull ()	스택에 들어있는 데이터가 maxsize인지 확인해 boolean값을 반환
	Boolean isEmpty ()	스택에 들어있는 데이터가 0인지 확인해 boolean 값을 반환
상태	Int top ()	스택에서 최근에 푸시한 데이터의 위치를 기록
	ItemType Data[maxSize]	스택의 데이터를 관리하는 배열. 최대 maxSize

여기서는 스택의 내부 구조를 배열로 관리하는 모습을 예로 들었다. 하지만 스택의 원소는 배열이 아니라 다른 자료구조로 관리할 수 있다.

 

 

 

스택 구현

• 파이썬에서의 구현:
  • 파이썬의 리스트를 사용하여 스택을 구현할 수 있다.
  • 기본적인 스택 함수는 다음과 같이 구현된다
  • 리스트는 동적으로 크기를 조정하므로, max_size와 같은 제한은 필요하지 않다. 따라서 isEmpty( ) 함수는 len(stack) == 0으로 검사한다.

stack = []  # 스택 리스트 초기화

def push(stack, item):
    stack.append(item)

def pop(stack):
    if len(stack) == 0:
        return None
    return stack.pop()

사용 팁

• 문제 인식:
  • 문제에서 스택을 사용할 필요성을 인식하는 것이 중요하다.
  • 데이터의 순서와 최근에 삽입된 데이터에 대한 처리가 필요할 때 스택을 고려해야 한다.

 

프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없다.

 

스택 내부 동작에 대해 조금 더 자세히 알아보기

스택에 데이터를 추가하는 경우를 생각해보자. 푸시 연산을 수행할 때 스택 내부에서 일어나는 과정이다. 그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습이다.

 

연산과정은

1. push(3)을 호출하면 내부적으로 isFull()을 수행해 우선 data 배열에 데이터가 가득 찼는지 확인하고,
2. 그렇지 않다면 top을 1만큼 증가시킨 후
3. top이 가리키는 위치data[0]에 3을 추가한다.

 

 

반대로 pop()연산을 수행한다면 어떨까?

1. isEmpty 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고
2. 데이터가 있다면 top을 1만큼 감소시키고
3. 데이터 '3'을 반환한다.

여기서 '3이 남아있는데?' 라고 생각할 수도 있다. 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라고 했다. 즉 top이 가리키는 위치는 -1이므로 실제 data 배열에 데이터가 남아있더라도 스택은 비어있다고 보아도 된다.

 

 

스택 구현하기

데이터를 그냥 저장하고 순서와 상관 없이 임의 접근하기만 해도 되면 배열을 사용하면 되지만, 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리는 것이 좋다. 

 

앞서 정의한 스택 ADT 를 구현하면 다음과 같다.

stack = [ ]    # 스택 리스트 초기화
max_size = 10  # 스택의 최대 크기

def isFull(stack):
  # 스택이 가득 찼는지 확인하는 함수
  return len(stack) == max_size

def isEmpty(stack):
  # 스택이 비어 있는지 확인하는 함수
  return len(stack) == 0

def push(stack, item):
  # 스택에 데이터를 추가하는 함수
  if isFull(stack):
    print("스택이 가득 찼습니다.")
  else:
    stack.append(item)
    print("데이터가 추가되었습니다.")

def pop(stack):
  # 스택에서 데이터를 꺼내는 함수
  if isEmpty(stack):
    print("스택이 비어 있습니다.")
    return None
  else:
    return stack.pop( )

 

 

그러나 python 의 리스트는 크기를 동적으로 관리하므로 max_size 나 isFull()함수, isEmpty()함수는 실제 문제를 풀 때 구현하지 않는다. len() 을 이용하거나 len(stack) == 0으로 검사한다.

 

또한 push() 와 pop() 메서드를 보면 실제 이 함수들이 하는 일은 리스트의 append()메서드, pop()메서드를 호출하는 것이 전부이다. 그러므로 push()와 pop() 메서드는 구현하지 않아도 된다.

stack = [ ]

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼냄
top_element = stack.pop( ) 
next_element = stack.pop( ) 

# 스택의 크기를 구함
stack_size = len(stack)

# top_element : 3
# next_element : 2

---

ref : 

https://wikidocs.net/book/13314

[되기] 코딩 테스트 합격자 되기 - 파이썬 편(~179스택까지)