스택 ( stack )
스택은 데이터를 넣는 곳과 빠지는 곳의 위치가 같은 자료구조를 말한다. 즉, 맨 아래에 있는 데이터를 꺼내기 위해서는 그 위의 데이터를 모두 꺼내야 할 것이다. 이런 구조를 후입선출 구조(LIFO; Last In First Out)라고 부른다.
stack은 크게 5가지 함수 사용이 가능하다.
1. push(x) # x를 stack의 맨 위에 올려 놓는다.
2. size() # stack 위에 쌓인 블럭의 개수를 반환한다.
3. empty() # stack 위가 비어있다면 true, 비어있지 않다면 false를 반환한다.
4. top() # stack의 맨 위에 있는 숫자 값을 반환한다. 단, stack에서 그 블럭을 제거하지는 않는다.
5. pop() # stack의 맨 위에 있는 숫자 값을 반환한다. 단, 동시에 stack에서 그 블럭을 제거한다.
스택에서 데이터를 넣고 빼는 작업은 다른 데이터에 영향을 주지 않는다.
따라서, 스택 자료구조 또한 삽입과 삭제 연산의 시간복잡도는 O(1)이라고 볼 수 있다.
스택은 쌍을 이루고 있는 것들이 올바르게 배치되어 있는지 확인할 때 유용하게 사용할 수 있다.
배열을 스택처럼 사용한다면, 일반적인 스택과 달리 중간 데이터를 확인할 수 있다는 엄청난 장점이 생긴다. 그렇지만 배열을 생성할 때 정의한 길이보다 스택에 들어가는 값이 더 많다면 문제가 생길 수 있다는 단점이 생긴다.
function push(arr, E)
if arr.size == maxsize // 배열에 이미 원소들이 가득 채워져 있다면,
throw exception() // 에러 메세지를 던져줍니다.
arr.append(E) // 정상적인 상황이라면, E를
// 마지막 위치에 추가해줍니다.
function pop(arr)
if arr.size == 0 // 배열에 아무런 원소도 없다면
throw exception() // 에러 메세지를 던져줍니다.
set last = arr[arr.size - 1] // 정상적인 상황이라면, 마지막 값을 변수에 저장해두고
delete arr[arr.size - 1] // 맨 끝에 있는 값을 실제로 제거한 뒤
return last // 마지막에 있었던 값을 반환해줍니다.
python에는 stack이라는 class가 따로 없다. 따라서, stack 자료구조를 사용하기 위해서는 직접 다음과 같이 class를 만들어주어야한다.
class Stack:
def __init__(self): # 빈 스택 하나를 생성합니다.
self.items = []
def push(self, item): # 스택에 데이터를 추가합니다.
self.items.append(item)
def empty(self): # 스택이 비어있으면 True를 반환합니다.
return not self.items
def size(self): # 스택에 있는 데이터 수를 반환합니다.
return len(self.items)
def pop(self): # 스택의 가장 위에 있는 데이터를 반환하고 제거합니다.
if self.empty():
raise Exception("Stack is empty")
return self.items.pop()
def top(self): # 스택의 가장 위에 있는 데이터를 제거하지 않고 반환합니다.
if self.empty():
raise Exception("Stack is empty")
return self.items[-1]또한, 재귀함수는 먼저 호출된 함수가 나중에 종료되어야 하므로, 스택이 표현하기에 적절한 자료구조이다.
문제
괄호 문자열은 두 개의 괄호 기호인 ' ( ' 와 ' ) ' 만으로 구성되어 있는 문자열 입니다. 괄호 문자열은 다음과 같이 2가지로 분류할 수 있습니다.
- 올바른 괄호 문자열 : 괄호를 열고 닫음이 분명한 문자열을 말합니다.
ex)
"()"
"(())"
"(()())"
- 올바르지 못한 괄호 문자열 : 괄호를 열고 닫음이 분명하지 못한문자열을 말합니다.
ex)
"(("
"(()(
"(((())"
입력으로 주어진 괄호 문자열이 올바른지, 그렇지 못한지를 판단하여 결과를 출력하는 프로그램을 작성하여 보세요.
import sys
class Stack:
def __init__(self): # 빈 스택 하나를 생성합니다.
self.items = []
def push(self, item): # 스택에 데이터를 추가합니다.
self.items.append(item)
def empty(self): # 스택이 비어있으면 True를 반환합니다.
return not self.items
def size(self): # 스택에 있는 데이터 수를 반환합니다.
return len(self.items)
def pop(self): # 스택의 가장 위에 있는 데이터를 반환하고 제거합니다.
if self.empty():
raise Exception("Stack is empty")
return self.items.pop()
def top(self): # 스택의 가장 위에 있는 데이터를 제거하지 않고 반환합니다.
if self.empty():
raise Exception("Stack is empty")
return self.items[-1]
# 변수 선언 및 입력:
string = input()
s = Stack()
for char in string:
if char == '(':
s.push('(')
else:
if s.empty():
print("No")
sys.exit(0)
s.pop()
if s.empty():
print("Yes")
else:
print("No")큐 ( Queue )
큐는 선입선출 구조(FIFO; First In First Out) 이다.
queue는 크게 5가지 함수 사용이 가능하다.
1. push(x) # x를 queue의 맨 뒤에 추가한다.
2. size() # queue 안에 들어있는 데이터의 개수를 반환한다.
3. empty() # queue 안에 남아있는 데이터가 없다면 true, 있다면 false를 반환한다.
4. front() # queue의 맨 앞에 있는 숫자 값을 반환한다. 단, queue에서 해당 데이터를 제거하지는 않는다.
5. pop() # queue의 맨 앞에 있는 숫자 값을 반환한다. 단, 동시에 queue에서 해당 데이터를 제거한다.
비록 데이터의 삽입과 삭제가 동일한 장소에서 수행되지는 않지만, 다른 값들의 이동이 필요하지 않기 때문에 여전히 삭제와 삽입의 시간복잡도는 으로 동일하다.
덱 ( Deque )
큐와 스택은 각각의 상황에 맞춰서 값을 넣고 뺄 수 있지만, 그외의 경우는 그러지 못한다는 단점이 있다. 이런 문제를 해결하기 위해 스택과 큐의 특성을 합친 새로운 자료구조는 덱이다.
덱은 스택과 큐와 달리 맨 앞/뒤에서 삽입/삭제가 모두 가능하며, 배열과 달리 네 메소드의 시간복잡도가 모두 다. 예를 들어 연결리스트를 사용하여 덱을 구현하면 양쪽 끝에서 삽입 삭제하는데 걸리는 시간이 이 되기 때문에 이러한 시간복잡도를 갖는 덱이라는 자료구조를 만들어낼 수 있다.
deque를 이용할 때 자주 사용되는 것은 다음과 같다.
python에서는 deque라는 package가 있다. deque는 collections라는 모듈에 있으며, 사용을 위해서는 from collections import deque를 가장 위에 적어줘야 한다.
dq = deque()로 정의되어있다는 가정하에 다음과 같이 이용해보자
1. dq.appendleft(a) # 맨 앞에 데이터 a를 추가한다.
2. dq.append(a) # 맨 뒤에 데이터 a를 추가한다.
3. dq.popleft() # 맨 앞에 있는 데이터를 제거하며, 해당 원소의 값을 반환한다.
4. dq.pop() # 맨 뒤에 있는 데이터를 제거하며, 해당 원소의 값을 반환한다.
5. len(dq) # 현재 deque에 들어있는 데이터의 수를 반환한다.
6. if dq # 현재 deque가 비어있는지 않은지 확인한다.
7. if not dq # 현재 deque가 비어있는지 확인한다.
8. dq[0] # deque의 맨 앞에 있는 데이터를 반환한다.
9. dq[-1] # deque의 맨 뒤에 있는 데이터를 반환한다.