: 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
배열을 사용해 구현 가능
저장소 자체를 스택이라 부르기도 함
스택에서 마지막 삽입된 원소의 위치
스택의 연산
스택의 삽입/삭제 과정

스택 구현
push 연산
append 메소드를 통해 리스트의 마지막에 데이터를 삽입
def my_push(item):
s.append(item)
인덱스 연산을 활용한 구현
def my_push(item, size):
global top
top += 1
if top == size:
print('overflow!')
else:
stack[top] = item
단순한 push 연산 (크기가 정해진 리스트와 인덱스 연산 활용)
size = 10
stack = [0] * size
top = -1
push(10, size)
top += 1 # push(20)
stack[top] = 20
pop 연산
남은 데이터 중 가장 늦게 저장된 데이터를 삭제하는 연산
def my_pop():
if len(s) == 0:
# underflow
return
else:
return s.pop() # 리스트 s의 마지막 원소 삭제
인덱스 연산을 이용한 연산
def my_pop():
global top
if top == -1:
print('underflow')
return 0
else:
top -= 1
return stack[top+1]
print(pop())
if top > -1: # pop()
top -= 1
print(stack[top+1])
스택 구현 고려 사항
1차원 배열을 사용하여 구현할 경우
해결 방법 : 저장소를 동적으로 할당하여 스택을 구현하는 방법
(동적 연결리스트를 이용하여 구현하는 방법)
<aside> 💡
동적 메모리 할당
: 필요한 만큼 메모리를 할당하고 해제하여 유연하게 크기를 조절 가능
연결리스트
: 데이터와 다음 노드의 주소를 함께 저장하여 요소들이 순차적으로 연결된 자료구조
메모리
: 컴퓨터에서 데이터를 저장하고 처리하기 위해 사용하는 일시적인 저장 공간
</aside>
괄호 종류
[ ]{ }( )조건
① 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함
② 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함
③ 괄호 사이에는 포함 관계만 존재함
스택을 이용한 괄호 검사

문자열의 괄호를 차례대로 확인하면서 왼쪽 괄호를 만나면 스택에 삽입,
오른쪽 괄호를 만나면 스택의 top 괄호를 삭제하고 오른쪽 괄호와 짝이 맞는지 검사함
스택이 비어 있으면 조건 ① 또는 조건 ②에 해당, 괄호의 짝이 맞지 않으면 조건 ③에 해당함
마지막 괄호까지 조사한 후 스택에 괄호가 남아 있으면 조건 ①에 해당함