728x90
728x170
스택(Stack)
스택(Stack)
- 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)의 특징을 갖는 자료구조
- 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다.
- 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 데이터를 추출하는 동작을 pop(팝)이라고 한다.
- 스택에서는 top(톱)이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다.
스택의 간단 구현
- 스택은 배열 형태로 구현할 수 있다.
- 스택은 초기에 크기를 지정하고 배열로 생성할 수 있다.
- 스택의 맨 위쪽을 표현하는 top은 아직 데이터가 없으므로 -1로 초기화한다.
- top이 -1이라는 것은 스택이 비었다는 의미로 해석하면 된다.
stack = [None, None, None, None, None]
top = -1
데이터 삽입 : push
stack = [None, None, None, None, None]
top = -1
top += 1
stack[top] = "커피"
top += 1
stack[top] = "녹차"
top += 1
stack[top] = "꿀물"
print("---- 스택 상태 ----")
for i in range(len(stack)-1, -1, -1) :
print(stack[i])
더보기
None
None
꿀물
녹차
커피
데이터 추출 : pop
stack = ["커피", "녹차", "꿀물", None, None]
top = 2
print("--- 스택 상태-----")
for i in range(len(stack)-1, -1, -1) :
print(stack[i])
print("-------------------")
data = stack[top]
stack[top] = None
top -= 1
print("pop -->", data)
data = stack[top]
stack[top] = None
top -= 1
print("pop -->", data)
data = stack[top]
stack[top] = None
top -= 1
print("pop -->", data)
print("-------------------")
print("--- 스택 상태-----")
for i in range(len(stack)-1, -1, -1) :
print(stack[i])
더보기
--- 스택 상태-----
None
None
꿀물
녹차
커피
-------------------
pop --> 꿀물
pop --> 녹차
pop --> 커피
-------------------
--- 스택 상태-----
None
None
None
None
None
스택의 일반 구현
① 스택의 초기화
SIZE = 5 # 스택의 크기
stack = [None for _ in range(SIZE)]
top = -1
② 데이터 삽입
스택이 꽉 찼는지 확인하는 함수
- 먼저 스택이 꽉 찼는지 확인한 후 스택에 여유 공간이 있을 때 데이터를 삽입해야 한다.
- top 값이 '스택 크기-1' 과 같다면 스택이 꽉 찬 상태이다.
if (top값 == 스택크기-1) :
스택이 꽉 찼음.
함수 완성하기
def isStackFull() :
global SIZE, stack, top
if (top >= SIZE-1) :
return True
else :
return False
SIZE = 5
stack = ["커피", "녹차", "꿀물", "콜라", "환타"]
top = 4
print("스택이 꽉 찼는지 여부 ==>", isStackFull())
더보기
스택이 꽉 찼는지 여부 ==> True
스택에 데이터를 삽입하는 함수
- 먼저 스택이 꽉 찼는지 확인하고, 여유가 있을 경우 데이터를 삽입한다.
def isStackFull() :
global SIZE, stack, top
if (top >= SIZE-1) :
return True
else :
return False
def push(data) :
global SIZE, stack, top
if (isStackFull()) :
print("스택이 꽉 찼습니다.")
return
top += 1
stack[top] = data
SIZE = 5
stack = ["커피", "녹차", "꿀물", "콜라", None]
top = 3
print(stack)
push("환타")
print(stack)
push("게토레이")
더보기
['커피', '녹차', '꿀물', '콜라', None]
['커피', '녹차', '꿀물', '콜라', '환타']
스택이 꽉 찼습니다.
isStackFull() 함수를 없애고, push() 함수만으로 기능 구현하기
def push(data) :
global SIZE, stack, top
if (top >= SIZE - 1): # *
print("스택이 꽉 찼습니다.")
return
top += 1
stack[top] = data
SIZE = 5
stack = ["커피", "녹차", "꿀물", "콜라", None]
top = 3
print(stack)
push("환타")
print(stack)
push("게토레이")
③ 데이터 추출
- 데이터를 추출하기 전에 먼저 스택에 데이터가 있는지 확인해야 한다.
- 스택에 데이터가 없는데도 데이터를 추출하려고 시도할 때는 별도의 조치를 취해야 한다.
스택이 비었는지 확인하는 함수
- top 값이 -1이라면 스택은 비어 있는 상태이다.
if (top값 == -1) :
스택이 비었음.
함수 완성하기
def isStackEmpty() :
global SIZE, stack, top
if (top == -1) :
return True
else :
return False
SIZE = 5
stack = [None for _ in range(SIZE)]
top = -1
print("스택이 비었는지 여부 ==>", isStackEmpty())
더보기
스택이 꽉 찼는지 여부 ==> True
스택에서 데이터를 추출하는 함수
def isStackEmpty() :
global SIZE, stack, top
if (top == -1) :
return True
else :
return False
def pop() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
data = stack[top]
stack[top] = None
top -= 1
return data
SIZE = 5
stack = ["커피", None, None, None, None]
top = 0
print(stack)
retData = pop()
print("추출한 데이터 -->", retData)
print(stack)
retData = pop()
더보기
['커피', None, None, None, None]
추출한 데이터 --> 커피
[None, None, None, None, None]
스택이 비었습니다.
isStackEmpty() 함수를 없애고, pop() 함수만으로 기능 구현하기
def pop() :
global SIZE, stack, top
if (top == -1) : # *
print("스택이 비었습니다.")
return
data = stack[top]
stack[top] = None
top -= 1
return data
SIZE = 5
stack = ["커피", None, None, None, None]
top = 0
print(stack)
retData = pop()
print("추출한 데이터 -->", retData)
print(stack)
retData = pop()
④ 데이터 확인
- top 위치의 데이터를 확인만 하고 스택에 그대로 두는 것을 Peek(픽)이라고 한다.
def isStackEmpty() :
global SIZE, stack, top
if (top == -1) :
return True
else :
return False
def peek() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
return stack[top]
SIZE = 5
stack = ["커피", "녹차", "꿀물", None, None]
top = 2
print(stack)
retData = peek()
print("top의 데이터 확인 -->", retData)
print(stack)
더보기
['커피', '녹차', '꿀물', None, None]
top의 데이터 확인 --> 꿀물
['커피', '녹차', '꿀물', None, None]
스택 완성
def isStackFull() :
global SIZE, stack, top
if (top >= SIZE-1) :
return True
else :
return False
def isStackEmpty() :
global SIZE, stack, top
if (top == -1) :
return True
else :
return False
def push(data) :
global SIZE, stack, top
if (isStackFull()) :
print("스택이 꽉 찼습니다.")
return
top += 1
stack[top] = data
def pop() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
data = stack[top]
stack[top] = None
top -= 1
return data
def peek() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
return stack[top]
SIZE = int(input("스택의 크기를 입력하세요 ==> "))
stack = [ None for _ in range(SIZE) ]
top = -1
if __name__ == "__main__" :
select = input("삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> ")
while (select != 'X' and select != 'x') :
if select=='I' or select =='i' :
data = input("입력할 데이터 ==> ")
push(data)
print("스택 상태 : ", stack)
elif select=='E' or select =='e' :
data = pop()
print("추출된 데이터 ==> ", data)
print("스택 상태 : ", stack)
elif select=='V' or select =='v' :
data = peek()
print("확인된 데이터 ==> ", data)
print("스택 상태 : ", stack)
else :
print("입력이 잘못됨")
select = input("삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> ")
print("프로그램 종료!")
더보기
스택의 크기를 입력하세요 ==> 5
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 커피
스택 상태 : ['커피', None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 녹차
스택 상태 : ['커피', '녹차', None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 꿀물
스택 상태 : ['커피', '녹차', '꿀물', None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> V
확인된 데이터 ==> 꿀물
스택 상태 : ['커피', '녹차', '꿀물', None, None]
삽입(I)/추출(E)/확인(V)/종 (X) 중 하나를 선택 ==> E
추출된 데이터 ==> 꿀물
스택 상태 : ['커피', '녹차', None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==> 녹차
스택 상태 : ['커피', None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 하나를 선택 ==> E
추출된 데이터 ==> 커피
스택 상태 : [None, None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 나를 선택 ==> E
스택이 비었습니다.
추 된 데이터 ==> None
스택 상태 : [None, None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> X
프로그램 종료!
스택의 활용
① 웹 서핑에서 이전 페이지 돌아가기
- 웹 서핑을 할 때, 여러 웹 페이지를 방문하다가 웹 브라우저 왼쪽 위에 있는 [이전 페이지] 버튼을 클릭하면, 마지막 방문한 웹 페이지부터 차례대로 다시 방문한다.
- 이를 간단하게 스택으로 구현할 수 있다.
- 웹 브라우저로 여러 웹 사이트를 방문하면, 방문한 URL을 스택에 push 해 놓는다.
- 그리고 [이전 페이지] 버튼을 클릭한 개념으로 pop 해서 방문한 URL을 역순으로 재방문한다.
프로그램 구현
import webbrowser
import time
def isStackFull() :
global SIZE, stack, top
if (top >= SIZE-1) :
return True
else :
return False
def isStackEmpty() :
global SIZE, stack, top
if (top == -1) :
return True
else :
return False
def push(data) :
global SIZE, stack, top
if (isStackFull()) :
print("스택이 꽉 찼습니다.")
return
top += 1
stack[top] = data
def pop() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
data = stack[top]
stack[top] = None
top -= 1
return data
def peek() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
return stack[top]
SIZE = 100
stack = [ None for _ in range(SIZE) ]
top = -1
if __name__ == "__main__" :
urls = [ 'naver.com', 'daum.net', 'nate.com']
for url in urls :
push(url)
webbrowser.open('http://'+url)
print(url, end = '-->')
time.sleep(1)
print("방문 종료")
time.sleep(5)
while True :
url = pop()
if url == None :
break
webbrowser.open('http://'+url)
print(url, end = '-->')
time.sleep(1)
print("방문 종료")
더보기
naver.com-->daum.net-->nate.com-->방문 종료
nate.com-->daum.net-->naver.com-->방문 종료
② 괄호의 매칭 검사
- 스택을 활용하여 간단하게 괄호의 매칭 검사를 수행할 수 있다.
- 여는 괄호를 만나면 push 하고, 닫는 괄호를 만나면 pop 한다 는 규칙을 적용한 후, push 또는 pop 하는 과정에서 다음의 조건을 확인하면 된다.
① 닫는 괄호를 만났을 때 스택은 비어 있지 않아야 한다.
② 닫는 괄호를 만났을 때 추출한 괄호는 여는 괄호여야 한다.
③ ②를 만족해도 두 괄호의 종류(소괄호, 중괄호, 대괄호)가 같아야 한다.
④ 모든 수식의 처리가 끝나면 스택은 비어 있어야 한다.
- 열린 괄호라면 무조건 push 한다.
- 닫는 괄호일 때는 스택에서 하나를 꺼내서 현재 괄호와 짝이 맞는지 확인한다.
if '(', '[', '{', '<' 중 하나면
push()
elif ')', ']', '}', '>' 중 하나면
열린 괄호 pop()
if 두 괄호의 쌍이 맞으면
통과
else
오류
- 그리고 모든 수식의 글자를 처리한 후, 다음과 같이 스택이 비었는지 확인한다.
if 스택이 비었으면
정상
else
오류
프로그램 구현
def isStackFull() :
global SIZE, stack, top
if (top >= SIZE-1) :
return True
else :
return False
def isStackEmpty() :
global SIZE, stack, top
if (top == -1) :
return True
else :
return False
def push(data) :
global SIZE, stack, top
if (isStackFull()) :
print("스택이 꽉 찼습니다.")
return
top += 1
stack[top] = data
def pop() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
data = stack[top]
stack[top] = None
top -= 1
return data
def peek() :
global SIZE, stack, top
if (isStackEmpty()) :
print("스택이 비었습니다.")
return None
return stack[top]
def checkBracket(expr) :
for ch in expr:
if ch in '([{<':
push(ch)
elif ch in ')]}>':
out = pop()
if ch == ')' and out == '(':
pass
elif ch == ']' and out == '[':
pass
elif ch == '}' and out == '{':
pass
elif ch == '>' and out == '<':
pass
else:
return False
else :
pass
if isStackEmpty() :
return True
else :
return False
SIZE = 100
stack = [ None for _ in range(SIZE) ]
top = -1
if __name__ == "__main__" :
exprAry = ['(A+B)', ')A+B(', '((A+B)-C', '(A+B]', '(<A+{B-C}/[C*D]>)']
for expr in exprAry :
top = -1
print(expr, '==>', checkBracket(expr))
더보기
(A+B) ==> True
스택이 비었습니다.
)A+B( ==> False
((A+B)-C ==> False
(A+B] ==> False
(<A+{B-C}/[C*D]>) ==> True
728x90
그리드형(광고전용)
'Computer Science > Data Structure' 카테고리의 다른 글
[Python] 재귀 호출(Recursion) (0) | 2022.06.05 |
---|---|
[Python] 그래프(Graph) (0) | 2022.06.04 |
[Python] 이진 트리(Binary Tree) (0) | 2022.06.04 |
[Python] 큐(Queue) (0) | 2022.06.03 |
[Python] 원형 연결 리스트(Circular Linked List) (0) | 2022.04.21 |
[Python] 단순 연결 리스트(Singly Linked List) (0) | 2022.04.21 |
[Python] 선형 리스트(Linear List) (0) | 2022.04.21 |
[C++] 디스조인트-셋(Disjoint-Set) ; 유니언-파인드(Union-Find), 서로소 집합, 상호 배타적 집합 (0) | 2021.06.26 |