스택(Stack)이란?

스택(stack)은 데이터가 한쪽 끝에서만 들어오고 나가는 자료구조다.

쉽게 말해, 마지막에 넣은 데이터가 가장 먼저 나오는 구조로 동작한다. 이를 LIFO(Last In, First Out) 구조라고도 한다.

 

예를 들어, 책을 쌓아 올릴 때 가장 위에 놓인 책을 먼저 꺼내는 것과 같은 방식이다.

데이터를 넣는 것을 push(푸쉬), 데이터를 꺼내는 것을 pop(팝)이라고 한다.

 

https://ko.wikipedia.org/wiki/스택

 

스택의 동작 원리

1. 데이터를 스택에 넣으면(top이 가리키는 위치에 추가) push 연산이 수행된다.
2. 데이터를 스택에서 꺼내면(top이 가리키는 데이터를 제거) pop 연산이 수행된다.
3. 가장 마지막에 추가된 데이터가 가장 먼저 제거된다.
4. 스택이 비었는지 확인할 수도 있다.

 

스택의 연산

스택에서 기본적으로 제공하는 연산은 다음과 같다.

• push(x): 데이터를 스택의 가장 위(top)에 추가한다.
• pop(): 스택의 가장 위(top) 데이터를 제거하고 반환한다.
• top(): 스택의 가장 위(top) 데이터를 반환하지만 제거하지 않는다.
• is_empty(): 스택이 비어 있는지 확인하여, 비었다면 True, 아니라면 False를 반환한다.

 

스택의 구현

스택은 프로그래밍 언어별로 다양한 방식으로 구현할 수 있다.

Python에서는 ist의 append()와 pop()을 사용하여 쉽게 구현할 수 있고, JavaScript에서는 Array의 push()와 pop()을 활용할 수 있다.

 

Python 스택 구현 예제

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, x):
        self.stack.append(x)
    
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return "Stack is empty"
    
    def top(self):
        if not self.is_empty():
            return self.stack[-1]
        return "Stack is empty"
    
    def is_empty(self):
        return len(self.stack) == 0

# 스택 사용 예제
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.top())  # 3
print(s.pop())  # 3
print(s.is_empty())  # False

 

JavaScript 스택 구현 예제

class Stack {
    constructor() {
        this.stack = [];
    }
    
    push(x) {
        this.stack.push(x);
    }
    
    pop() {
        return this.stack.length ? this.stack.pop() : "Stack is empty";
    }
    
    top() {
        return this.stack.length ? this.stack[this.stack.length - 1] : "Stack is empty";
    }
    
    is_empty() {
        return this.stack.length === 0;
    }
}

// 스택 사용 예제
const s = new Stack();
s.push(1);
s.push(2);
s.push(3);
console.log(s.top());  // 3
console.log(s.pop());  // 3
console.log(s.is_empty());  // false

 

스택의 활용

스택은 다양한 곳에서 활용된다. 대표적인 예시는 다음과 같다.

• 웹 브라우저의 뒤로 가기(Back) 기능: 방문한 페이지를 스택에 저장하고, pop을 통해 이전 페이지로 이동한다.
• 수식 계산(연산자 우선순위 처리): 중위 표기법을 후위 표기법으로 변환하는 과정에서 사용된다.
• 재귀 함수(함수 호출 스택): 프로그램이 함수 호출을 관리할 때 내부적으로 스택을 사용한다.
• 문자열 괄호 검사: 여는 괄호를 push, 닫는 괄호를 pop 하면서 올바른 괄호 조합을 판별한다.

스택은 간단하지만 강력한 자료구조다. 알고리즘 문제를 풀 때도 자주 사용되니 개념을 확실히 이해하고 직접 구현해보는 것이 좋다!

 

---

 

눈떠보니 코딩테스트 전날 강의 | 제주코딩베이스캠프 - 인프런