[자료구조] Stack 스택

Stack

스택(Stack)은 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조.
스택은 마지막에 추가된 요소가 가장 먼저 제거되는 후입선출(LIFO, Last In First Out)구조로, 스택의 한 쪽 끝(top)을 통해서만 접근할 수 있어서 인덱스 접근이 제한됨.
*stack : noun. a pile of objects

동작	설명	시간복잡도
push	스택 맨 끝(맨 위)에 항목을 삽입한다. 새 요소 추가	O(1)
pop	스택의 최상위 요소를 제거하고 제거된 요소를 반환한다	O(1)
top/peek	스택 맨 위 항목을 반환(조회)한다	O(1)
isEmpty	스택이 비어있는지 확인한다. 비어있으면 True.	O(1)
size	스택 크기(저장된 요소의 수)를 확인한다	O(1)

스택은 실행 취소 메커니즘을 구현하거나 이전 상태로 되돌리기 위해, 그래프에서 깊이 우선 검색을 위한 알고리즘을 만들거나 역추적에 사용할 수 있음. 출력 순서가 입력 순서의 역순으로 이루어질 때 사용되는 자료구조.

Array를 이용한 Stack

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, element):
        self.stack.append(element)
    
    def pop(self):
        if self.isEmpty():                 # 빈 리스트에는 pop을 할 수 없음. IndexError: pop from empty list
            return "Stack is empty"
        return self.stack.pop()
    
    def peek(self):
        if self.isEmpty():                 # 빈 리스트에서는 에러. IndexError: list index out of range
            return "Stack is empty"
        return self.stack[-1]
    
    def isEmpty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

# 스택 생성
myStack = Stack()

myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Stack: ", myStack.stack)
print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.size())

Stack:  ['A', 'B', 'C']
Pop:  C                                   # 요소가 제거된 리스트가 아니라 제거된 요소 반환
Peek:  B
isEmpty:  False                           # 값이 있으면 False
Size:  2

Array를 이용한 Stack의 장점

• 메모리 효율성 : Array는 LinkedList처럼 다음 요소의 주소를 유지하지 않음.
• 구현 및 이해가 용이함

Array를 이용한 Stack의 단점

• 고정된 크기: Array는 고정된 크기. Array가 가득 차면 더 이상 요소를 담을 수 없음.

Linked List를 이용한 Stack

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

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def push(self, value):
        new_node = Node(value)              # 스택에 추가될 새 노드
        if self.head:                       # 만약 스택이 비어있지 않다면
            new_node.next = self.head       # head를 새 노드의 next로 변경
        self.head = new_node                # 스택의 head를 새 노드로 변경
        self.size += 1                      # 스택 요소 증가
    
    def pop(self):
        if self.isEmpty():
            return "Stack is empty"
        popped_node = self.head             # 제거될 요소는 스택의 head
        self.head = self.head.next          # 스택의 head는 head의 다음노드
        self.size -= 1                      # 스택 요소 감소
        return popped_node.value            # 제거된 요소 반환
    
    def peek(self):
        if self.isEmpty():
            return "Stack is empty"
        return self.head.value              # 스택의 head 반환
    
    def isEmpty(self):
        return self.size == 0
    
    def stackSize(self):
        return self.size

myStack = Stack()
myStack.push('A')
myStack.push('B')
myStack.push('C')
print("Pop: ", myStack.pop())
print("Peek: ", myStack.peek())
print("isEmpty: ", myStack.isEmpty())
print("Size: ", myStack.stackSize())

Pop:  C
Peek:  B
isEmpty:  False
Size:  2

Linked List를 이용한 Stack의 장점

• 동적크기 : Array와 달리 동적으로 확장하고 축소할 수 있음.

Linked List를 이용한 Stack의 단점

• 메모리 : 다음 노드에 대한 주소를 포함해야함.
• 가독성 : Array에 비해 코드가 더 길고 복잡함.

백준 10773번 제로 문제 풀어보기

# 풀이
count = int(input())
stack = []

for _ in range(count): 
    num = int(input())
    if(num == 0):          # num이 0이면 pop
        stack.pop()
    else:                  # num이 0이 아니라면 push
        stack.append(num)
        
# 합 출력      
print(sum(stack))