스택이란?
- 스택은 후입선출의 특성을 가지는 자료구조이다.
- top은 맨 위의 값을 나타낸다.
- 값을 집어 넣는 PUSH, 값을 빼내는 POP, 값을 조회하는 PEEK이 존재한다.
그래서 스택이 무엇인가?
게임 같은 것을 즐긴다면 '~~ 스택 쌓는다' 라는 말 정도는 한번 쯤 들어보았을 것이다. 영단어 그대로 해석하자면 '쌓다' 라는 뜻이다. 자료구조에서 스택은 동전을 쌓는 것과 비슷하다고 생각하면 된다. 100원짜리 위에 100원짜리를 올리고, 또 올리고 올리다 보면 일자로 길게 쌓인 동전탑을 만들 수 있다. 그렇다면 여기서 중간에 있는 동전을 뺄 수 있을까? 불가능 할 것이다.
위에서부터 맨 마지막에 쌓은 동전부터 맨 처음 쌓은 동전 순서대로 빼낼 수 있을 것이다. 스택은 이렇게 후입 선출로 작동한다.
구현
파이썬의 클래스를 통해 구현해 줄 것이다. 스택이라는 클래스는 __init__과 push,pop,peek 이 3개의 함수로 구현해줄 것이다.
1. __init__
__init__은 해당 클래스가 기본적으로 가지고 있는 값을 설정해준다고 생각하면 된다.
크기가 정해진 배열을 통해서 스택을 구현할 것이다. 그러므로 그 크기를 전달받아야 하고, 그 크기만큼의 크기를 갖는 배열, 그리고 맨 마지막에 들어온 값의 위치를 나타내줄 변수가 필요할 것이다. 이것을 코드로 작성하면 다음과 같다.
def __init__(self,maxsize): # init은 변수=STACK(값) 이렇게 전달받을 때 전달되는 그 값이 init으로 들어온다.
# 기본적으로 들어와야 한 값이라 생각하면 된다.
self.maxsize=maxsize
# 스택의 최대 사이즈를 self.maxsize에 저장해주었다.
self.top=-1
# 가장 위에 있는 값의 위치를 나타내줄 변수이다.
# 배열의 시작 위치는 0이고 맨 처음에는 비어있으므로 0이 아닌 -1을 넣어준다.
# 스택은 후입 선출 ( 나중에 들어온 것이 먼저 나감 )이고
# 값의 들어오고 나가는 것이 모두 top에서 일어난다.
# top이 증가하면 삽입, top이 감소하면 삭제가 이루어진다.
self.arr=[0]*self.maxsize
# 실제로 값이 쌓이거나 빠져나갈 배열
# 해당 배열은 0으로 초기화 해주었지만 이 코드가 어떻게 작동하는지 안다면
# 0으로 초기화 하든 10억으로 초기화 하든 문자를 넣든 상관 없다는 것을 알 것이다.top의 경우 0으로도 시작할 수 있지만 나는 -1을 사용했다. 비어있는 경우가 아니라면 항상 맨 위의 값을 나타내고 있다.
크기가 8인 배열을 선언했다면 다음과 같은 상태일 것이다.
| 배열 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 |
2. PUSH
스택이 비어있지 않다면 top은 스택의 맨 위의 값을 가르키고 있다. 새로운 값을 추가하려면 top에 1을 더해준 뒤 그 위치에 값을 저장해주면 된다.
| 배열 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 |
해당 배열에 2와 3을 삽입한다고 생각해보자.
2가 삽입될 경우 top(-1)에 1이 더해지게 된다. top=0
그리고 배열의 0번째 인덱스에 2를 저장한다
| 배열 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 | top |
이제 3을 삽입한다고 생각을 해보자. 마찬가지로 top에 +1을 해준다.
| 배열 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 | top |
top=1, 배열의 1번째 인덱스에 3을 저장한다.
| 배열 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 | top |
만약 배열이 가득 차게 된 경우, 값을 더 삽입할 수 없고 배열의 크기가 8인 경우 배열의 인덱스는 0~7이므로 그 때의 top의 위치는 최대 크기보다 1 작다는 것을 이용해 예외처리 해줘야 한다.
이것을 코드로 작성하면 다음과 같다.
def PUSH(self,num): # num이라는 정수를 전달받아 스택에 넣어주는 함수이다.
# 일단 값의 삽입 이전에 배열이 가득 차있는지 확인해야 한다.
if self.top==self.maxsize-1: # 배열의 크기는 maxsize이므로 마지막 값이 위치하는 값은 maxsize-1이다.
# top이 maxsize-1을 가르킨다면 값이 모두 차있다는 것을 의미하게 된다.
print('스택이 가득 차있습니다')
else: # 만일 가득 차지 않았다면
# 맨 처음의 경우 top은 -1을 가르키고 있다. 이제 값이 추가될 것이고 항상 top은 맨 위의 값을 가르켜야 한다.
# 그러므로 배열에 첫 원소가 삽입되면 top을 +1 시켜주고 그 위치에 값을 넣어주면 된다.
# arr[0]=num이 될 것이고 top의 값은 0이 될 것이다.
# top의 경우 기존의 위치, top+1 은 넣어줘야 할 위치를 가르킨다.
self.top+=1 # 값이 들어왔으므로 top은 +1
self.arr[self.top]=num # top위치에 전달받은 num값 저장
3. POP
스택이 비어있는 경우가 아니라면 맨 위의 값, top이 가르키는 값을 가져올 수 있다.
만약 비어있는 경우 top은 -1이므로 top이 -1인 경우를 예외처리 해주면 된다.
비어있지 않은 경우 배열의 top번째 인덱스에 위치한 값을 변수에 저장해두고 top에서 1을 빼준 뒤 저장해둔 값을 반환해준다.
이렇게 구현을 하게 되면 다음과 같이 진행이 된다.
예시로 4,5,6이 들어있는 스택을 이용해 설명하겠다.
| 배열 | 4 | 5 | 6 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 | top |
위는 맨 처음 배열의 상태이다. 이 상태에서 pop을 하게 되면 다음과 같다.
일단 현재 top번째 인덱스의 값인 6을 변수에 저장해놓는다.
그리고 top에서 1을 빼준다.
| 배열 | 4 | 5 | 6 | 0 | 0 | 0 | 0 | 0 |
| top의 위치 | top |
그렇다면 스택의 상태는 다음과 같아지고 변수에 저장해놓은 6을 반환함으로써 pop 함수의 작동을 끝낸다.
POP을 통해 6을 삭제하려고 했는데 배열에는 6이 남아있다. 이것은 괜찮은 것인가 라는 생각이 들수도 있다.
중요한 것은 top 이후의 값들은 아무 상관이 없다는 것을 알아야 한다.
다시 지금 6이 있는 2번째 인덱스에 가게 된다면 그때는 APPEND를 통해서 접근을 하게 되고, 그 때 추가하려는 값으로 갱신이 이루어지므로 저 배열에 어떤 값이 들어있던 그것은 아무 상관도 없는 것이다.
코드는 다음과 같다.
def POP(self): # PUSH의 경우 값을 전달받아야 했지만 POP의 경우 맨 위의 값을 제거 한뒤 반대로 전달해준다.
# 일단 값을 삭제하기 위해서는 배열이 비어있지 않아야 한다.
if self.top==-1: # 배열이 비어있다면 top의 값은 -1
print('스택이 비어있습니다')
else: # 만일 비어있지 않다면
# 앞선 경우는 top+1이 넣어줘야 하는 위치이므로 top+=1이 먼저였지만 삭제의 경우 top의 위치에서 뺀 뒤 top의 위치를 -1시켜준다.
# 기존의 top을 삭제되고 top-1의 값이 새로운 top이 되어야 하므로 top의 위치를 -1 해주는 것이다.
value=self.arr[self.top] # 맨 위의 값을 value라는 변수에 저장
self.top-=1 # 맨 위의 값에 제거되었으므로 top의 값은 -1
return value
# 순서를 잘 파악하자. top에서 -1을 먼저 하고 value에 넣으면 top의 위치의 값이 아닌 top-1의 위치의 값이 들어간다.
# top의 위치의 값을 먼저 반환한다면(return) 함수가 종료되므로 top-=1이 실행되지 않는다.
# 그러므로 top의 위치의 값을 저장해 놓고 top에서 1을 빼준 뒤 그 값을 반환해주면 된다.
4. PEEK
PEEK의 경우 POP과 비슷하지만 맨 위의 값의 삭제가 아닌 맨 위의 값의 값만 얻어오는 것이다. 그러므로 POP을 살짝 변형시키면 된다.
마찬가지로 배열이 비어있다면 가져올 수 있는 값이 없다. top==-1인 경우 예외처리 해주자.
앞서 말했듯 배열이 차있다면 top은 항상 맨 위의 값을 가지고 있다.
따라서 top 값의 변경 없이 그냥 배열의 top번째 인덱스를 반환해주면 되는 것이다.
def PEEK(self): # top에 해당하는 데이터를 읽는 함수, POP과 달리 값의 삭제가 이루어지지는 않는다.
# POP과 마찬가지로 스택이 비어있다면 top에 해당하는 데이터가 없다.
if self.top==-1:
print('스택이 비어있습니다')
else:
return self.arr[self.top] # 배열의 top 위치에 존재하는 값 반환 그러나 top 값에는 변화를 주지 않음
전체코드
class STACK:
# self는 지역변수 ( class라는 영역 안에서 쓸 수 있게 해주는 변수라고 이해하자 )
def __init__(self,maxsize): # init은 변수=STACK(값) 이렇게 전달받을 때 전달되는 그 값이 init으로 들어온다.
# 기본적으로 들어와야 한 값이라 생각하면 된다.
self.maxsize=maxsize
# 스택의 최대 사이즈를 self.maxsize에 저장해주었다.
self.top=-1
# 가장 위에 있는 값의 위치를 나타내줄 변수이다.
# 배열의 시작 위치는 0이고 맨 처음에는 비어있으므로 0이 아닌 -1을 넣어준다.
# 스택은 후입 선출 ( 나중에 들어온 것이 먼저 나감 )이고
# 값의 들어오고 나가는 것이 모두 top에서 일어난다.
# top이 증가하면 삽입, top이 감소하면 삭제가 이루어진다.
self.arr=[0]*self.maxsize
# 실제로 값이 쌓이거나 빠져나갈 배열
# 해당 배열은 0으로 초기화 해주었지만 이 코드가 어떻게 작동하는지 안다면
# 0으로 초기화 하든 10억으로 초기화 하든 문자를 넣든 상관 없다는 것을 알 것이다.
def PUSH(self,num): # num이라는 정수를 전달받아 스택에 넣어주는 함수이다.
# 일단 값의 삽입 이전에 배열이 가득 차있는지 확인해야 한다.
if self.top==self.maxsize-1: # 배열의 크기는 maxsize이므로 마지막 값이 위치하는 값은 maxsize-1이다.
# top이 maxsize-1을 가르킨다면 값이 모두 차있다는 것을 의미하게 된다.
print('스택이 가득 차있습니다')
else: # 만일 가득 차지 않았다면
# 맨 처음의 경우 top은 -1을 가르키고 있다. 이제 값이 추가될 것이고 항상 top은 맨 위의 값을 가르켜야 한다.
# 그러므로 배열에 첫 원소가 삽입되면 top을 +1 시켜주고 그 위치에 값을 넣어주면 된다.
# arr[0]=num이 될 것이고 top의 값은 0이 될 것이다.
# top의 경우 기존의 위치, top+1 은 넣어줘야 할 위치를 가르킨다.
self.top+=1 # 값이 들어왔으므로 top은 +1
self.arr[self.top]=num # top위치에 전달받은 num값 저장
def POP(self): # PUSH의 경우 값을 전달받아야 했지만 POP의 경우 맨 위의 값을 제거 한뒤 반대로 전달해준다.
# 일단 값을 삭제하기 위해서는 배열이 비어있지 않아야 한다.
if self.top==-1: # 배열이 비어있다면 top의 값은 -1
print('스택이 비어있습니다')
else: # 만일 비어있지 않다면
# 앞선 경우는 top+1이 넣어줘야 하는 위치이므로 top+=1이 먼저였지만 삭제의 경우 top의 위치에서 뺀 뒤 top의 위치를 -1시켜준다.
# 기존의 top을 삭제되고 top-1의 값이 새로운 top이 되어야 하므로 top의 위치를 -1 해주는 것이다.
value=self.arr[self.top] # 맨 위의 값을 value라는 변수에 저장
self.top-=1 # 맨 위의 값에 제거되었으므로 top의 값은 -1
return value
# 순서를 잘 파악하자. top에서 -1을 먼저 하고 value에 넣으면 top의 위치의 값이 아닌 top-1의 위치의 값이 들어간다.
# top의 위치의 값을 먼저 반환한다면(return) 함수가 종료되므로 top-=1이 실행되지 않는다.
# 그러므로 top의 위치의 값을 저장해 놓고 top에서 1을 빼준 뒤 그 값을 반환해주면 된다.
def PEEK(self): # top에 해당하는 데이터를 읽는 함수, POP과 달리 값의 삭제가 이루어지지는 않는다.
# POP과 마찬가지로 스택이 비어있다면 top에 해당하는 데이터가 없다.
if self.top==-1:
print('스택이 비어있습니다')
else:
return self.arr[self.top] # 배열의 top 위치에 존재하는 값 반환 그러나 top 값에는 변화를 주지 않음
def SHOW(self): # STACK이 어떤식으로 작동하는지 확인하기 위해 만들어본 함수, 원래 존재하는 특징은 아니다.
for i in range(self.top+1): # 배열의 n번째 까지 출력하기 위해서는 n+1 그러므로 top까지 출력하기 위해서는 top+1
print(self.arr[i],end=' ')
print()
stack=STACK(5) # 크기가 5인 스택
for i in range(6): # 0,1,2,3,4,5,6 순서대로 스택에 삽입
print('삽입하려는 값',i)
stack.PUSH(i)
print('현재 스택 :',end=' ')
stack.SHOW()
print('top에 존재하는 값',stack.PEEK()) # PEEK을 통해 맨 위의 값을 삭제하지 않고 얻어옴
print('현재 스택 :',end=' ')
stack.SHOW()
for i in range(6): # POP 6번 실시
topvalue=stack.POP()
print('top에 있던 값',topvalue)
print('현재 스택 :',end=' ')
stack.SHOW()
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [PYTHON] 배열을 통해 구현한 선형 큐 / 원형 큐 (0) | 2022.01.29 |
|---|