스택

📌 스택

스택은 가장 마지막에 추가한 요소가 먼저 제거되는 선형 자료구조이다.
즉, 후입 선출 자료구조이다. 추가나 제거에 제한이 있기 때문에 접근이 제한된 자료구조라고도 한다.

스택의 두 가지 동작, 푸시와 팝

• 푸시 : 스택에 요소를 뒤에 추가하는 것
• 팝 : 스택에 마지막으로 추가된 요소를 꺼내는 것이다.

➕ 픽 : 마지막 요소를 제거하지 않고, 접근만 하는 동작이다.

스택의 종류

• 제한된 스택 : 추가할 수 있는 요소의 수에 제한이 있다.
• 무제한 스택 : 추가할 수 있는 요소의 수에 제한이 없다.

스택의 시간 복잡도

	접근	탐색	삽입	삭제
스택	O(n)	O(n)	O(1)	O(1)

• 스택은 데이터 삽입,삭제에 효율적이다.
• 전체 데이터 접근에는 비효율적이다.

🤔 스택의 전체 요소 접근은 O(2n)?

스택은 푸시와 팝으로만 이루어져있어서 전체 요소를 꺼내면서 출력하면, 스택이 빈 상태가 된다.
따라서 임시 스택에 꺼낸 요소를 저장하고, 모든 요소를 옮긴 후 다시 원래 스택으로 되돌려야한다.
따라서 걸리는 시간이 두배가 되고, 메모리도 더 많이 쓰게된다.

스택을 사용해야할 때

• 스택에서는 요소를 추가하고 제거하는 작업이 O(1)으로 이런 작업이 빈번할 때 이상적이다.
• 실행취소나 다시실행에 쓰인다.

파이썬으로 스택 만들기 - 리스트로 스택 클래스

class Stack_list:
    def __init__(self):
        self.items=[]

    def push(self,data):
        self.items.append(data)

    def pop(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

    def is_empty(self):
        return len(self.items) == 0

    def peek(self):
        return self.items[-1]

stack = Stack_list()

stack.push(1)
stack.push(3)
stack.push(5)

print(stack.pop())  #5
print(stack.pop())  #3
print(stack.pop())  #1

파이썬으로 스택 만들기 - 링크드 리스트로 스택 클래스

class Node:
    def __init__(self,data,next=None):
        self.data = data
        self.next = next

class Stack_linked_list:
    def __init__(self):
        self.head = None
    def push(self,data):
        if self.head is None:
            self.head = Node(data)
        else:
            new = Node(data)
            new.next = self.head
            self.head = new

    def pop(self):
        if self.head is None:
            return False
        re = self.head.data
        self.head = self.head.next
        return re

stack = Stack_linked_list()
stack.push(1)
stack.push(3)
stack.push(5)

print(stack.pop())  #5
print(stack.pop())  #3
print(stack.pop())  #1
print(stack.pop())  #False

파이썬으로 스택 만들기 - 클래스를 만들지 않고도

• 간단하지만 동작을 강제할 수 없다.

stack = []
stack.append(1)
stack.append(3)
stack.append(5)

print(stack.pop())	#5
print(stack.pop())	#3
print(stack.pop())	#1

🔍 스택 활용

스택을 사용해 문자열 뒤집기

문자열을 뒤집는 대표적인 방법은 다음 두가지가 있다.

#리스트로
a = "안녕?"
a = a[::-1] #?녕안
print(a)

#.join을 이용해서
b = ''.join(reversed("안녕하세요"))
print(b)       #요세하녕안

그러나 스택을 사용해서 문자열을 뒤집는 방법도 있다.

스택 사용해서 문자열 뒤집기 - 성공코드

def reverse_string(a_string):
    stack = []
    s = ""
    for i in a_string:
        stack.append(i)
    while len(stack) != 0:
        s += str(stack.pop())
    return s
    
a_list = "안녕하십니까"
print(reverse_string(a_list))	#까니십하녕안

😅 실패한 이유 -

    for i in stack:
        print(i)
        s += str(stack.pop())
    return s

for문은 앞에서부터 카운트한다. pop은 뒤에서부터 꺼낸다.
for문이 한번씩 실행될때마다 stack의 길이가 줄어든다.

최소 스택

푸시와 팝과 같은 스택 동작으로 가장 작은 요소를 반환하는 메서드를 가진 자료구조 설계

class MinStack():
    def __init__(self):
        self.main = []
        self.min = []

    def push(self,n):
        if len(self.main) == 0:
            self.min.append(n)
        elif n < self.min[-1]:
            self.min.append(n)
        else:
            self.min.append(self.min[-1])
        self.main.append(n)

    def pop(self):
        self.min.pop()
        return self.main.pop()

    def get_min(self):
        return self.min[-1]


stack = MinStack()
stack.push(3)
stack.push(2)
stack.push(8)
stack.push(1)

print(stack.get_min())      #1
stack.pop()
print(stack.get_min())      #2

스택과 괄호

"문자열에 들어있는 괄호의 짝이 맞는지 확인해보세요. 다시말해 여는 괄호가 있으면 닫는 괄호도 있어야합니다."

def check_parentheses(a_lsit):
    stack = []
    for i in a_lsit:
        if i == "(":
            stack.append(i)
        elif i ==")":
            if len(stack) != 0:
                stack.pop()
            else:
                return False
    if len(stack) != 0:
        return False
    return True

print(check_parentheses("()()()"))  #True
print(check_parentheses("()())"))   #False
print(check_parentheses("()()"))    #True
print(check_parentheses("))"))      #False