자료구조 - 순차적 자료구조 : 스택(Stack)(2022.09.22~10.12)

1. 스택(Stack)

---

LIFO방식(Last In First Out) : 뷔페에서 볼 수 있는 쌓아둔 그릇을 생각하면 이해가 쉽다. 가장 나중에 들어온 데이터가 가장 먼저 나가는 방식이다.

 

즉 스택의 모든 연산은 스택의 최상단에서 이루어진다.

 

스택의 연산들에 대해 알아보자. (파이썬)

 

- 삽입연산  :   push를 이용해 스택에 값을 삽입한다.(리스트에서는 append를 사용)

 

- 삭제연산 : pop을 이용하며 가장 나중에 들어온 데이터가 삭제된다.

pop을 사용할 때는 스택이 비워져 있을 때, 즉 pop할 아이템이 없을 상황을 대비해야 한다. (pop할 아이템이 없으면 indexError가 발생한다.) 이 때는 try & except 를 이용한다.

 

class stack

	def __init__(self):
    	self.items = []
        
	def pop(s):
    	try
        	return self.items.pop()
        except IndexError:
        	print("Stack is empty")

 

리스트(list)를 세워서 생각하면 위에서 알아본 스택과 유사해보인다. 다만, 리스트(list)에는 스택에 없는 다양하고 강력한 연산들이 있다는 점에서 차이가 있다. 리스트를 스택처럼 쓰다보면 append, pop이 아닌 다른 함수를 이용해 변경해 버릴 수 있으니 이런 실수를 줄이기 위해 애초에 제공되는 연산을 지정해서 그 연산을 사용하는 것이 좋다.

 

 

삽입, 삭제 연산 외에도 다른 연산들이 필요할 때도 있다. 

 

- top : return items[-1]  # 반환할 아이템이 없을 때를 대비하여 try&except 를 활용한다.

-  len( )  # stack의 item 수 반환

 

1) 예제 :  괄호 맞추기

 

왼쪽,오른쪽 괄호의 문자열이 입력됐을 때, 이 괄호들의 쌍이 맞춰져 있으면 True, 아니면 False를 반환하도록 한다.

 

- 관찰

왼쪽 괄호가 등장하면 이 왼쪽 괄호의 짝꿍인 오른쪽 괄호가 나타나야 짝이 맞춰진다.

따라서 오른쪽 괄호가 등장할 때까지 스택 안에서 대기하도록 한다.

 

예를 들어 ' ( ( ) ( ) ) ' 가 입력됐다면,  아래 그림과 같은 과정으로 스택에 쌓였다가 pop되는 과정이 반복될 것이다.

 

이번에는 '(  ( ) ' 와 같은 문자열이 입력됐다고 생각해보자.

 

입력된 문자열의 괄호가 쌍을 이루지 않으므로 왼쪽과 오른쪽 괄호가 만나 pop이 되었음에도 마지막에 스택이 비어있지 않게 된다. 따라서 이 문자열은 false가 나와야한다.

 

즉, 왼쪽 괄호가 나오면 스택에 push, 오른쪽 괄호가 나오면 짝이 되는 왼쪽 문자열을 pop을 하도록 한다. (이 때, 가장 top에 왼쪽 괄호가 있어야 pop이 가능하다.)

모든 문자열에 대해 위 과정을 시행한 후에 스택이 비어있으면 true를 결과값으로 반환, 아닐 경우 false를 반환하도록 해야한다.

 

위 내용대로 코드를 작성해보자. 

def parChecker(parSeq):
	S = Stack()
	for each symbol in parseq:
		if symbol == '(':
     		S.push(symbol)
     
   elif symbol ==')':
  	 	if S is empty: 
        	return False
        else: 
        S.pop()
  If S is empty: 
  		return True
  else: 
  		return False

 

위 내용대로 Visual Studio Code를 활용해 코드를 구현해보려 했으나 자꾸 오류가 발생하였다. 따라서 파이썬 공부를 개인적으로 좀 더 했고(아직 함수를 활용하기에는 내가 부족함을 느낀다.) 백준 문제를 풀면서 아래와 같이 코드를 작성해보았다.(게시물 업로드가 늦어진 이유,,,)

 

S = int(input())
stack = []

for s in range(S):
	stack.clear()
    flag = 0
    parseq = input()
    
    for i in parseq:
    	if i == "(":
        	stack.append("(")
        else:
        	try:
            	stack.pop()
            except:
            	flag=1
                break
    if len(stack) == 0 and flag == 0:
    	print("YES")
    else:
    	print("NO")

위 코드는 백준의 문제에 맞추어 작성한 코드로써, 기존에 True 또는 False로 값을 반환한 것과 달리, 괄호의 짝이 맞으면 'YES'를 출력하고 아닐 경우 'NO'를 반환하도록 작성하였다.

 

위 코드를 작성하며 겪은 여러 시행착오가 있으나 자세한 내용은 파이썬 폴더의 백준 풀이에서 설명하겠다.

 

 

 

 

 

 

 

---

 

본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.

 

자료구조 과목 소개 - YouTube