Stack ・LIFO(Last In First Out)

 

 

Stack 설명 

Stack은 먼저 들어온 데이터는 제일 늦게 나가게 되고, 맨 마지막에 들어온 자료가 제일 먼저 나가는 자료구조이다.

후입선출(LIFO: Last In First Out) 구조라고 한다.

 

Stack은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있도록 제한된 선형으로 나열된 자료구조이다. 

 

Python에서 stack의 자료구조는 배열 순서에 따른 배열 리스트(array list)와

논리 순서에 따른 연결 리스트(linked list) 두 가지로 활용되는데,

알고리즘 코딩테스트에서는 주로 배열 리스트(array list) 형식인 list 자료구조로 stack을 사용한다.

 

 

Stack 기본 연산

Stack의 입출력은 .append() 리스트 제일 뒤에 데이터 입력과

.pop() 리스트 제일 뒤에 데이터 출력을 사용한다.

 

.pop(-1): 맨 앞에 있는 원소를 삭제한다.

.pop(i): 리스트의 i번째 원소를 삭제한다.

 

.push() : stack에 원소를 추가한다

.pop(): stack 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.

.peek(): stack 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다)

.empty(): stack이 비어있다면 1, 아니면 0을 반환한다.

 

 

Stack 라이브러리 

Python 내장모듈에서는 따로 stack 라이브러리가 존재하지 않는다.

보통 deque 라이브러리를 import 하거나 list를 stack 대신 사용한다.

from collections import deque

dq = deque() # 덱 생성

dq.append() # 가장 오른쪽에 원소 삽입
dq.appendleft() # 가장 왼쪽에 원소 삽입

dq.pop() # 가장 오른쪽 원소 반환 
dq.popleft() # 가장 왼쪽 원소 반환

dq.clear() # 모든 원소 제거

dq.copy() # 덱 복사

dq.count(x) # x와 같은 원소 개수 계산

 

---

문제 유형 

문자와 괄호가 섞여있는 문자가 입력되면 괄호 안에 들어있지 않은 문자만 출력하는 프로그램을 완성하시오. 

(괄호는 열었으면 반드시 닫았다는 전제를 가진다)

 

입력: (QO)D(A)

출력: D

 

 

풀이

1. 리스트 자료구조를 활용하여 stack으로 문제를 해결한다.

2. 문자열을 반복문으로 앞에서부터 순회하며 stack에 append를 하고,

닫는 괄호 ')'가 나오면 여는 괄호'('가 pop될 때까지 pop을 한다.

3. 괄호를 pop하면 괄호 사이의 문자도 pop 되고,

stack에 남은 것은 괄호 안에 없었던 문자만 stack에 쌓인다. 

 

n = input()
stack = []

for i in n:
    if i == ')' 
    	while True: # while문을 활용하여 열린괄호가 나올 때까지 pop하여 제거한다
            p = stack.pop()
            if p == '(':
            	break
    else: 
    	stack.append(i)

for i in stack:
    print(i, end = ' ')
    
# 입력 : ((Z)OP(DL)A)D(W)I(DL(HV))K
# 출력 : D I K

 

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력
print(stack[-1]) # 최상단 원소(top) 출력

---

 

문제 유형 

[단어를 역순으로 출력하기]

주어진 문자열을 역순으로 반환하는 함수를 작성하시오.

 

입력: aircraft

출력: tfarcria 

 

 

[괄호의 짝이 맞는지 확인하기]

괄호의 짝이 바르면 True, 바르지 않으면 False를 반환하는 함수를 작성하시오. 

 

입력: ((a*(b+c))-d) / e 

출력: True

 

입력: (((a*(b+c))-d) / e

출력: False

 

 

[소괄호, 중괄호, 대괄호의 짝이 맞는지 검사하기]

 

 

[짝지어 제거하기]

알파벳으로 이루어진 문자열에서 같은 알파벳이 2개 붙어있는 짝을 찾고 제거한다.

앞뒤로 문자열을 이어 붙이는 과정을 반복할 때, 문자열이 모두 제거한다면 1을 출력한다.

 

입력: S = baabaa 

출력: 1