스택 (Stack) & 큐 (Queue)

1. 스택 (Stack)

스택 정의

스택은 데이터가 쌓인 형태의 자료구조로써 그 자체가 리스트는 아니지만 파이썬에서 리스트를 가지고 스택처럼 사용할 수 있다. 가장 중요한 것은 후입선출! Last In - First Out (LIFO) 이다. 마지막에 입력 (push) 되어지는 원소는 가장 위에 위치하게 되며 top이라고 불린다.  후에 DP, Backtracking, DFS 등의 알고리즘 풀이에서 스택을 사용하게 된다. 

스택의 요소 및 메소드

• top : 스택에 마지막 삽입된 원소의 위치
• push : 저장소에 자료를 넣는 것, 후입선출
• pop : top만 pop 가능, 저장소에서 자료를 꺼내는 것, 자료구조에서 사라짐
• isEmpty : 스택이 공백인지 아닌지 확인
• peak : 스택의 top에 있는 원소를 반환하는 연산, 자료구조 내에 남아있음

스택을 이용한 괄호 검사

마지막에 괄호 하나가 남는다면 연산 과정에서 괄호의 갯수가 잘못되었음을 확인할 수 있다. 대부분의 괄호 에러는 이런 식으로 구분한다. 

 

2. 큐 (Queue)

큐 정의

스택과 동일하게 데이터가 쌓인 자료구조지만, 차이점은 선입선출! First In - First Out (FIFO) 이다.

큐의 요소 및 메소드

• front(head) : 데이터를 dequeue 할 수 있는 위치
• rear(tail) : 데이터를 enqueue 할 수 있는 위치
• enqueue : 큐에 데이터를 넣는 작업 (스택의 push에 해당)
• dequeue : 큐에서 데이터를 꺼내는 작업 (스택의 pop에 해당)
• num : 큐의 데이터 갯수를 반환하며 큐가 공백인지 아닌지 확인 가능