스택(Stack)

스택 

한쪽 끝에서만 삽입과 삭제가 이루어지는 선형 자료구조(linear data structure)이다. 가장 나중에 삽입된 데이터가 먼저 삭제되는 LIFO를 따른다. 

 

스택 자료구조

 

스택의 장점과 단점

장점 : 구현이 쉬움, 삽입과 삭제가 빠르다(O(1)), 재귀적 상황을 자연스럽게 표현 가능

단점 : 중간요소 접근 불가, LIFO 구조로 인해 일부 알고리즘에 부적합하다, 크기 제

 

스택을 왜 사용할까?

 

• 후입선출 구조가 필요한 문제 해결
• 함수 호출 관리 (Call Stack)
• 괄호 검사, 수식 계산기
• DFS(깊이 우선 탐색)와 백트래킹
• Undo/Redo 기능 (웹브라우저, 텍스트 에디터 등)

 

 

스택 주요 연산

함수 이름	기능	시간복잡도
push()	삽입	O(1)
pop()	삭제 및 반환	O(1)
is_empty()	비어있는지 확인	O(1)
size()	스택 크기 확인	O(1)
peek() or top()	맨 위 원소 조회	O(1)

 

배열로 구현(python)

class Stack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.top = -1 
        self.data = [0]*capacity

    def topElement(self):
        if self.top < 0:
            print("Stack is Empty")
            return False
        else:
            return self.data[self.top]

    def isEmpty(self):
        if self.top == -1:
            print("Stack is Empty")
            return True
        else:
            print("Stack is not Empty")
            return False

    def push(self, element):
        if self.top >= self.capacity - 1:
            print("Stack OverFlow")
            return False

        self.top += 1
        self.data[self.top] = element
        print(element, "is pushed")
        return True

    def pop(self):
        if self.top < 0:
            print("Stack UnderFlow")
            return False

        delete = self.data[self.top]
        self.top -= 1
        print(delete, "is popped")
        return delete

    def isFull(self):
        if self.top == self.capacity - 1:
            print("Stack is Full")
            return True
        else:
            print("Stack is not Full")
            return False

 

스택은 간단하지만 강력한 자료구조로서, 다양한 문제에 핵심도구로 사용됨.