[자료구조] 스택 (Stack)

스택이란?

스택 (Stack)이란 마지막에 들어간 자료가 가장 먼저 나오는 자료구조인데, 이를 LIFO (Last In First Out) 구조라고 말한다. 스택은 쌓는다는 의미를 갖기도 하는데, 순서대로 쌓은 것을 꺼낼 때는 역순으로 꺼낸다고 생각하면 된다. 예를 들어, 스택에 요소들을 A, B, C 순으로 저장했을 때, 꺼낼 때는 C, B, A 순으로 꺼내야 한다. 

 

실생활에서 워드나 한글 같은 편집기에서 처리한 작업을 되돌리기 하는 경우, 가장 나중에 한 작업부터 순서대로 되돌리기 되는데, 이도 스택의 원리를 이용한 것이라고 볼 수 있다.

 

 

스택의 연산

스택이라는 자료형에서의 연산은 어떻게 이루어질까? 앞서 말했듯이 스택에서는 새로운 자료를 스택에 넣는 기능과, 스택 상단에 있는 자료를 꺼내는 기능이 필요하다. 즉, 삽입과 삭제가 가장 핵심적인 연산으로, 이들은 스택의 상태를 변화시킨다. 다음은 스택에서 사용될 수 있는 연산들이다.

연산	연산의 기능
push(e)	새로운 요소 e를 스택의 최상단에 추가
pop()	스택의 맨 위에 있는 요소를 꺼내서 변환
isEmpty()	스택이 비어 있으면 True를, 아니면 False를 반환
isFull()	스택이 가득 차 있으면 True를, 아니면 False를 반환
size()	스택에 들어 있는 전체 요소의 수를 반환
peek()	스택의 맨 위에 있는 항목을 삭제하지 않고 반환

 

스택에서 삽입과 삭제를 담당하는 연산이 바로 push와 pop이다. 그런데 push의 경우에는 상단에 어떤 요소를 쌓을 지 그 정보를 입력해주어야 하지만, pop의 경우는 무조건 가장 상단의 요소를 삭제하는 것이므로 별도의 입력이 필요없다.

출처 : https://hong-devbox.tistory.com/4

 

peek는 pop과 비슷하게 상단 요소를 반환하지만, 연산 후에도 스택의 상태는 변하지 않는다. 만약 스택이 peek 연산을 지원하기 않는다면 pop으로 꺼내서 확인한 후 push로 다시 넣으면 원래 상태가 유지된다.

 

isEmpty와 isFull은 각각 스택의 공백 상태와 포화 상태를 검사하는데, 결과는 True 또는 False이다. 

 

배열 구조로 스택 구현하기

배열구조란 : 자료들을 배열에 모아 저장하는 방법을 말한다. 모든 요소는 인접한 메모리 공간에 저장되는데, 각 요소를 찾아 쉽게 사용할 수는 있지만, 스택이 가득 차게 되면 더는 저장할 수 없다.

 

배열을 이용한 스택의 구조는 다음과 같다.

• array[] : 스택 요소들을 저장할 배열
• capacity : 스택의 최대 용량, 저장할 수 있는 요소의 최대 개수
• top : 상단 요소의 위치 (변수, 인덱스)

배열은 요소를 저장할 공간이고, 용량은 이 공간의 크기로 고정된 상수이다. top은 가장 최근에 저장된 요소의 위치를 가리키는 변수이다.

capacity = 10	# 용량이 10인 스택
array = [None] * Capacity	#[None, None, ... , None] (길이 10)
top = -1	#상단의 인덱스 (초기값 -1)

 

1.  isEmpty()와 isFull() 연산

스택이 공백이거나 포화인지를 확인하기 위해 top의 값을 확인할 수 있는데, 공백이면 top = -1일 것이고, 포화면 top = capacity - 1의 값을 가질 것이다.

def isEmpty():
	if top == -1:	#공백이면 True
    	return True
    else:			#공백 아니면 False
    	return False 
        
def isFull():
	return top == capacity - 1	#비교 연산 결과 바로 반환

 

 

2.  push(e) 연산

삽입을 하기 위해서는 우선 top을 하나 증가시켜야 한다. 그 다음 그 위치에 삽입할 요소를 복사하면 삽입이 완료된다. 그러나 한 가지 전제조건이 필요한데 바로 포화상태가 아니어야 한다는 것이다. 만약 포화상태라면 오버플로우 상태가 되어 삽입이 불가능하기 때문이다. 따라서 스택에서는 삽입하기 전에 먼저 스택이 포화상태인지 아닌지를 검사할 필요가 있다.

 

def push(e):
	if not isFull():	#포화 상태 아닌 경우
    	top += 1		#top 증가 (global top 선언 필요)
    	array[top] = e		#top 위치에 e 복사
        
    else:				
    	print("stack overflow")	#포화 상태 : overflow
        exit()

 

 

3.  pop() 연산

이번에는 삭제 연산을 구현해보겠다. 삭제가 가능하려면 스택에 최소 하나 이상의 요소가 있어야 하므로 pop연산에서는 스택이 공백 상태가 아닌지를 따져봐야 한다. 공백이 아니면 top - 1을 해주고, top + 1의 요소를 반환하면 된다. 만약 공백이면 언더플로우 오류가 발생한다.

 

def pop():
	if not isEmpty():		#공백 상태가 아닌 경우
    	top = -1			#top 감소
        return array[top + 1]		#이전 (top + 1)의 위치 요소 반환
        
    else: 
    	print("stack underflow")	#공백 상태 ; underflow
        exit()

 

 

4. peek() 연산

peek 역시 공백이 아니어야 가능한데, 단순히 top 위치의 요소만 반환하면 된다.

def peek():
	if not isEmpty():		#공백 상태가 아닌 경우
    	return array[top]
    else:		
    	pass

 

 

5. size() 연산

def size():
	return top + 1

 

 

파이썬에서 스택 사용하는 법

만약 파이썬에서 코딩하다가 스택이 필요하다면? 직접 위처럼 함수들을 짜도 되지만 그냥 제공되는 것들을 사용해서 빨리 해결하자.

1) 파이썬 List를 스택처럼 사용하기

연산	Stack	파이썬 list
삽입	push()	append()
삭제	pop()	pop()
요소 수	size()	len(L)
공백상태 검사	isEmpty()	len(L) == 0
상단 들여다보기	peek()	L[-1] 또는 L[len(L) -1]

 

2) queue 모듈의 LifoQueue 사용하기

파이썬에서는 queue 모듈에서 큐(Queue)나 스택(LifoQueue), 우선순위 큐(Priority Queue) 등을 클래스로 제공해준다. 따라서 이 모듈의 LifoQueue를 사용하면 손쉽게 스택을 사용할 수 있다.

import queue
s = queue.LifoQueue(maxsize = 20)

 

제공 연산:

• 삽입, 삭제: put(), get()
• 공백/포화 상태 검사: empty(), full()
• 상단 들여다보기: 제공하지 않음

 

Class를 통해 구현한 전체 스택 코드

Stack 구현" target="_blank" rel="noopener" data-mce-href="http://Stack 구현">http://Stack 구현

GitHub - taekyounglee1224/DS_ALGO: Code snippets for Data Structure and Algorithm using Python