[자료 구조] 스택 & 큐 (Stack & Queue)

스택(Stack)

스택(Stack)이란?

Stack

• 후입선출의 원칙을 따르는 자료구조로 차곡차곡 쌓아올리는(Stack) 것
• 삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간 복잡도

사용 예

• 브라우저의 뒤로가기
• 실행 취소 (Ctrl + z)
• 재귀 함수
• 역순 문자열 (문자열 거꾸로 뒤집기)

구현

# structures.py

'''
연결리스트를 응용해서, 대신 제일 앞이 아니라 제일 위여야 하므로 가장 처음 걸 top으로 한다.
O
↓
O
↓
O
↓
O
↓
O
형태가 된다.
'''
class Node:
    def __init__(self, val = 0, next = None):
        self.val = val #상자
        self.next = next

class Stack:
    def __init__(self):
        self.top = None

    '''
    스택은 쌓으므로 append가 아닌 push,
    연결리스트와 다른 점 : 새로 들어온 게 항상 top
    '''
    def push(self, val):
        # node = Node(val,None) : 새로 들어오면
        # node.next = self.top : 기존에 가장 위에(top)였던 애를 다음 노드로
        # self.top = node : 그리고 지금 새로 만든 노드를 top으로
        # 결국 val,next 에서 top 이었던 것을 next로 만드는 것이므로 한줄로 표현하면
        self.top = Node(val,self.top)

    def pop(self):
        if not self.top: # 없을 때
            return None # None을 넣어준다
        # pop 이므로 top 을 위에서 두번째걸로, 즉 다음걸로 바꿔줘야 함
        node = self.top
        self.top = node.next
        # 그리고 선택된 노드(아직 제일 위에거이지만 top은 다음으로 넘겨준)를 반환한다.
        return node.val
    def is_empty(self):
        return self.top is None # pop 에서 넣어준 None 이 리턴되었다면 -> 없다면!

# test.py

def test_stack():
    stack = Stack()

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)
    '''
    현재 스택
    5
    4
    3
    2
    1
    '''
    # 스택에서 pop 하면 제일 위에 거 (마지막 거이기 때문에)
    assert stack.pop() == 5
    assert stack.pop() == 4
    assert stack.pop() == 3
    assert stack.pop() == 2
    assert stack.pop() == 1
    assert stack.pop() is None
    assert stack.is_empty()

예제

Q
'(', ')', '{', '}', '[' 및 ']' 만 포함된 문자열이 주어졌을 때 입력 문자열이 유효한지 확인하는 프로그램을 작성하세요.

열린 괄호가 제대로 닫혔는지 확인 -> 내가 연 순서의 반대로 닫으면 됨
ex) ({[]})

• 여는 괄호가 나올 때 마다 스택에 담고, 여는 게 끝나면 스택 제일 위부터 꺼내서 짝을 비교하면(딕셔너리 사용) 제대로 닫혔는지 확인할 수 있다.
• 실제 문제풀이 할 때는 리스트를 스택처럼 써서 푼다.

# prac.py

def test_problem_stack(s):
    pair = {
        '}': '{',
        ')': '(',
        ']': '[',
    }
    opener = "({["
    stack = []

    for char in s:
        if char in opener: # 여는 거일 때
            stack.append(char)
        else: # 닫는 거일 때
            if not stack: # 여는 게 끝났는데 닫는 게 남아있다면
                return False
            top = stack.pop()
            if pair[char] != top:
                return False

    return not stack

# test.py

assert test_problem_stack("()")
assert test_problem_stack("()[]{}")
assert test_problem_stack("({[][]})")
assert test_problem_stack("({[]})")
assert not test_problem_stack("(]")
assert not test_problem_stack("(()]")
assert not test_problem_stack("(((])")
assert not test_problem_stack("((())")

큐 (Queue)

종류

1. 선형 큐 (Linear Queue) (대부분 큐라고 하면 선형 큐를 의미한다.)
2. 우선순위 큐 (Prioity Queue)
3. 원형 큐 (Circular Queue)
4. 덱 (Deque, Double-ended Queue)

선형 큐(Linear Queue)란?

Linear Queue

• 한 쪽에서는 데이터 삽입, 다른 한 쪽에서는 데이터의 삭제만 가능한, 선입선출 원칙을 따르는 자료구조
• 삽입과 삭제에는 O(1), 탐색에는 O(n) 의 시간 복잡도

구현

• 스택처럼 쌓기 때문에 넣을 땐 똑같지만
• 뺄 때는 맨 뒤에서, 즉 처음 넣은 것을 뺀다. front를 빼는 게 아니다.

# structures.py

'''
노드 클래스는 연결리스트, 스택과 동일하다.
class Node:
    def __init__(self, val=0, next=None):
        self.val = val # 상자
        self.next = next # 화살표
'''

'''
가장 앞에 있는 게 중요하므로 front
'''
class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        if not self.front: # 맨 앞에가 없으면
            self.front = Node(value) # 노드 만들어서 front로
            return

        #맨 앞이 있으면
        node = self.front # 제일 앞 노드를 잡아서
        while node.next: # 다음 노드가 있는 동안 (다음 노드가 없을 때 까지)
            node = node.next # 다음 노드를 계속 잡는다. 
        '''
        다음 노드가 없으면 새로 상자를 만들어서 들어온 value를 대입, 
        그리고 다음 노드로 가리키게 해준다(화살표를 만든다. next는 화살표를 의미함)
        '''
        node.next = Node(value) 

    def pop(self):
        if not self.front: # 꺼낼 게 없으면
            return None

        node = self.front # 꺼낼 게 있으면 
        self.front = self.front.next # 맨 앞부터 (처음 넣은 것 부터) 꺼낸다.
        return node.val

    def is_empty(self):
        return self.front is None

# test.py

def test_queue():
    queue = Queue()

    queue.push(1)
    queue.push(2)
    queue.push(3)
    queue.push(4)
    queue.push(5)

    assert queue.pop() == 1
    assert queue.pop() == 2
    assert queue.pop() == 3
    assert queue.pop() == 4
    assert queue.pop() == 5
    assert queue.pop() is None
    assert queue.is_empty()

예제

Q
1부터 N까지 차례대로 줄을 섰을 때, 맨 앞에 선 사람만 들여보내주고 그 다음 순서인 사람은 제일 뒤로 보내는 특이한 줄서기가 있습니다.

예를 들어 N=6인 경우, 123456 이 순서대로 줄을 서있을 것입니다. 이때 제일 먼저 1이 입장하고 남은 순서는 23456이 됩니다. 2는 두 번째 순서이므로 제일 뒤로 보내서 34562가 됩니다. 다시 3이 입장하여 4562가 되고, 4가 두 번째 순서이므로 5624가 되빈다. 5가 입장하고 246, 2가 입장하고 64, 6이 입장하여 4, 마지막으로 4가 입장하게 됩니다.

N이 주어질 때 제일 마지막으로 입장하는 숫자를 계산하는 프로그램을 작성하세요.

• deque를 사용한다.

# prac.py
from collections import deque

def test_problem_queue(n):
    deq = deque([i for i in range(1, num + 1)])

    while len(deq) > 1: # 요소가 2개 이상 남아있는 동안 (하나 남을 때 까지)
        deq.popleft() # deque의 앞에서 꺼낸다.
        deq.append(deq.popleft()) # 두번째는 앞에서 꺼내서 맨뒤에 붙인다.
    return deq.popleft()

# test.py

assert test_problem_queue(2) == 2
assert test_problem_queue(3) == 2
assert test_problem_queue(4) == 4
assert test_problem_queue(5) == 2
assert test_problem_queue(6) == 4
assert test_problem_queue(7) == 6