stack

Stack

• stack은 자료를 꺼낼 때 맨 위부터 꺼낸다.
• 후입선출(Last In First Out) 구조
• list로도 구현할 수 있지만, 단일 연결 리스트를 활용해 구현해 보았다.

# list로 구현한 stack
class stack:
    def __init__(self): 
        self.list = []

    def push(self, item):  # 요소 추가
        self.list.append(item)

    def pop(self):  # 요소 삭제
        return self.list.pop()

    def peek(self):  # 요소 리턴
        return self.list[-1]

    def is_empty(self):  # 스택이 비었는지 확인(비었으면 True 리턴)
        return not self.list

활용

class Node:
    def __init__(self, val=None):
        self.val = val
        self.next = None
        
        
class Stack:
    def __init__(self):
        self.top = None
        
    def __str__(self):
        if not self.top:
            return "stack이 존재하지 않습니다."
        
        node = self.top
        output = ""
        
        while node.next:
            output += f"{str(node.val)} -> "
            node = node.next
        output += str(node.val)
        
        return output
        
    def push(self, val):
        node = Node(val)
        
        if not self.top:
            self.top = node
        else:
            node.next = self.top
            self.top = node
            
    def pop(self):
        if not self.top:
            return "제거할 요소가 존재하지 않습니다."
            
        node = self.top
        self.top = node.next
        
        return f"`{node.val}` 노드 제거"
        
    def peek(self):
        if not self.top:
            return "맨 위 노드가 존재하지 않습니다."
        return self.top.val
        
    def is_empty(self):
        return not self.top
            
        
stack = Stack()
print(f"stack이 없는가? {stack.is_empty()}")
print(f"stack에 제거할 요소가 있는가? {stack.pop()}")
print(f"맨 위 노드 => {stack.peek()}")
print()
stack.push("1번")
stack.push("2번")
stack.push("3번")
stack.push("4번")
stack.push("5번")

print("[기존 stack]")
print(stack)
print(f"맨 위 노드 => {stack.peek()}")
print(f"stack이 없는가? {stack.is_empty()}")
print()

print("[pop한 stack]")
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
print(f"맨 위 노드 => {stack.peek()}")
print(f"stack이 없는가? {stack.is_empty()}")

>>> stack이 없는가? True
	stack에 제거할 요소가 있는가? None
	맨 위 노드 => None

	[기존 stack]
	5번 -> 4번 -> 3번 -> 2번 -> 1번
	맨 위 노드 => 5번
	stack이 없는가? False

	[pop한 stack]
	5번
	4번 -> 3번 -> 2번 -> 1번
	4번
	3번 -> 2번 -> 1번
	3번
	2번 -> 1번
	맨 위 노드 => 2번
	stack이 없는가? False

실습

• 위에서 짜놨던 코드를 조금 수정한다.

class Node:
    def __init__(self, val=None):
        self.val = val
        self.next = None
        
        
class Stack:
    def __init__(self):
        self.top = None
        
    def __str__(self):
        if not self.top:
            return "None"
        
        node = self.top
        output = ""
        
        while node.next:
            output += f"{str(node.val)} -> "
            node = node.next
        output += str(node.val)
        
        return output
        
    def push(self, val):
        node = Node(val)
        
        if not self.top:
            self.top = node
        else:
            node.next = self.top
            self.top = node
            
    def pop(self):
        if not self.top:
            return None
            
        node = self.top
        self.top = node.next
        
        return node.val
        
    def peek(self):
        if not self.top:
            return None
        return self.top.val
        
    def is_empty(self):
        return not self.top

단어 역순 출력

• stack은 가장 처음 들어온 단어가 가장 뒤로 가게 된다. 즉, 가장 나중에 들어온 단어가 stack의 요소를 pop() 하면 가장 처음으로 나오게 된다.
• 그러므로 들어온 단어를 차례대로 stack에 저장한 후, 다시 차례대로 빼주면 쉽게 해결할 수 있다.

def reverse_word(word):
    output = ""
    stack = Stack()
    
    [stack.push(w) for w in word]
    
    # 생성된 stack 확인
    print(f"stack: {stack}")
    
    while stack.is_empty():
        output += stack.pop()
    
    return output
    
    
print(reverse_word("weekend"))

>>> stack: d -> n -> e -> k -> e -> e -> w
	dnekeew

괄호의 짝 확인

• stack의 특성을 최대한 활용해보려 했다. 하지만 코드에 뭔가 구멍이 있을 것 같다.
• 소괄호 한 종류만 온다고 하면 그냥 push와 pop만 하면 되지만, 종류가 다르기 때문에 dictionary에 세 종류의 괄호 짝을 만들어놓고 활용했다.

def pair_of_bracket(syntax):
    stack = Stack()
    pair = {"(": ")", "{": "}", "[": "]"}
    
    for string in syntax:
        if string in pair.keys():
            stack.push(string)
        elif string in pair.values():
            if stack.peek():   # 맨 앞에 닫히는 괄호가 올 경우 대비
                if pair[stack.peek()] == string:
                    stack.pop()
            else:
                return False
    
    return stack.is_empty()
            
            
print(pair_of_bracket("(((()))"))
print(pair_of_bracket("(())"))
print(pair_of_bracket("{([()]]}"))
print(pair_of_bracket("{([()])}"))
print(pair_of_bracket("]{([()])}"))
print(pair_of_bracket("{([()])}]"))

>>> False
	True
	False
	True
	False
	False