자료구조 스택에 대해서 설명해주세요.
🤔 스택이란 무엇인가요?
안녕하세요! 오늘은 프로그래밍의 기본 자료구조 중 하나인 스택(Stack)에 대해 알아보겠습니다.
스택은 접시를 쌓는 것처럼 데이터를 순서대로 쌓아올리는 구조입니다. 가장 중요한 특징은 후입선출(LIFO: Last In, First Out) 방식으로 동작한다는 점입니다.
📚 스택의 주요 특징과 용어
핵심 동작
- push(item) 👆: 스택의 맨 위에 요소를 추가합니다
- pop() 👇: 스택의 맨 위에 있는 요소를 제거하고 반환합니다
- peek() 👀: 스택의 맨 위 요소를 제거하지 않고 확인만 합니다
- isEmpty() 🕳️: 스택이 비어있는지 확인합니다
주의해야 할 상황
- 스택 오버플로우(Stack Overflow) 💥: 스택의 용량을 초과하여 데이터를 넣으려 할 때 발생
- 스택 언더플로우(Stack Underflow) 🕳️: 비어있는 스택에서 데이터를 꺼내려 할 때 발생
💻 자바스크립트로 스택 구현하기
자바스크립트에서는 배열을 사용하여 쉽게 스택을 구현할 수 있습니다:
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) return "스택이 비어있습니다!";
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
🚀 스택의 실생활 활용 사례
1. 🔙 브라우저 뒤로가기 기능
브라우저에서 방문한 페이지를 스택에 저장하여 뒤로가기 기능을 구현할 수 있습니다.
class BrowserHistory {
constructor() {
this.history = new Stack();
this.current = null;
}
visitPage(url) {
if (this.current) this.history.push(this.current);
this.current = url;
console.log(`현재 페이지: ${url}`);
}
goBack() {
if (this.history.isEmpty()) {
console.log("더 이상 뒤로 갈 수 없습니다!");
return;
}
this.current = this.history.pop();
console.log(`뒤로가기: ${this.current}`);
}
}
// 사용 예시
const browser = new BrowserHistory();
browser.visitPage("홈페이지");
browser.visitPage("상품목록");
browser.visitPage("상품상세");
browser.goBack(); // 상품목록으로 돌아감
browser.goBack(); // 홈페이지로 돌아감
2. ↩️ 언두(Undo) 기능
텍스트 에디터나 그래픽 프로그램의 작업 취소 기능도 스택으로 구현할 수 있습니다.
class TextEditor {
constructor() {
this.content = "";
this.history = new Stack();
}
type(text) {
this.history.push(this.content); // 현재 상태 저장
this.content += text;
console.log(`현재 내용: ${this.content}`);
}
undo() {
if (this.history.isEmpty()) {
console.log("더 이상 실행취소할 수 없습니다!");
return;
}
this.content = this.history.pop();
console.log(`실행취소 후: ${this.content}`);
}
}
// 사용 예시
const editor = new TextEditor();
editor.type("안녕하세요! ");
editor.type("스택은 ");
editor.type("정말 유용합니다.");
editor.undo(); // "안녕하세요! 스택은 "으로 돌아감
editor.undo(); // "안녕하세요! "로 돌아감
3. 🔍 괄호 검사
코드 에디터에서 괄호의 짝이 맞는지 검사할 때도 스택을 활용합니다:
function checkBrackets(code) {
const stack = new Stack();
const openBrackets = "({[";
const closeBrackets = ")}]";
for (let char of code) {
if (openBrackets.includes(char)) {
stack.push(char);
} else if (closeBrackets.includes(char)) {
if (stack.isEmpty()) return false;
const last = stack.pop();
// 짝이 맞는지 확인하는 로직
if ((last === '(' && char !== ')') ||
(last === '{' && char !== '}') ||
(last === '[' && char !== ']')) {
return false;
}
}
}
return stack.isEmpty(); // 모든 괄호가 짝을 이룬 경우
}
4. 📊 웹 앱에서 상태 관리
React 애플리케이션에서 상태 변화를 기록하고 되돌릴 때도 스택이 유용합니다:
function DrawingApp() {
const [canvas, setCanvas] = useState([]);
const [history, setHistory] = useState([]);
const addShape = (shape) => {
setHistory([...history, canvas]); // 현재 상태를 히스토리에 저장
setCanvas([...canvas, shape]);
};
const undo = () => {
if (history.length === 0) return;
const lastState = history[history.length - 1];
setCanvas(lastState);
setHistory(history.slice(0, -1));
};
return (
<div>
{/* 그림 그리는 인터페이스 */}
<button onClick={undo}>실행 취소</button>
</div>
);
}
📝 자바에서 스택 사용 시 주의사항
자바에서 Stack 클래스 대신 Deque 인터페이스를 사용하는 것이 좋은 이유:
- 더 명확한 스택 동작 ✅: Deque는 후입선출 특성에 맞는 메소드만 제공
- 성능 최적화 🚀: 불필요한 동기화 작업 없이 사용 가능
- 확장성 📈: 필요에 따라 동기화 구현체 선택 가능
// 권장되지 않는 방식
Stack<String> oldStack = new Stack<>();
// 권장되는 방식
Deque<String> stack = new ArrayDeque<>();
stack.push("요소");
String top = stack.pop();
🎯 결론
스택은 매우 단순하지만 강력한 자료구조입니다. 특히 "되돌리기"나 "순서 추적"이 필요한 기능에서 빛을 발합니다. 웹 개발이나 데이터센터 관리 시스템과 같은 복잡한 애플리케이션에서도 스택의 원리를 이해하고 활용하면 더 효율적인 코드를 작성할 수 있습니다.
스택의 핵심은 "나중에 들어온 것이 먼저 나간다"는 간단한 원칙이지만, 이 원칙이 만들어내는 응용 가능성은 무궁무진합니다! 🚀
자료구조 스택에 대해서 설명해주세요.
스택(Stack) 은 후입선출이라는 개념을 가진 선형 자료구조입니다. 스택 자료구조에서 삭제(pop)는 가장 최상단(top)에서만 이루어집니다. 비어있는 스택에서 값을 추출하려고 시도하는 경우를 스택 언더플로우라고 하며, 스택이 넘치는 경우를 스택 오버플로우라고 합니다. 대표적인 활용 사례는 스택 메모리, 브라우저 뒤로가기 기능, 언두 기능, 수식 괄호 검사 등이 있습니다.
자바에서 스택은 어떻게 사용할 수 있나요?
Stack이라는 클래스를 사용할 수 있습니다. 하지만, Deque 인터페이스 구현체를 사용하는 것이 권장됩니다. 왜냐하면, Stack 클래스는 내부적으로 Vector를 상속 받고 있기 때문입니다. Vector를 상속받은 Stack은 인덱스를 통한 접근, 삽입, 제거 등이 실질적으로 가능합니다. 이는 후입선출 특징에 맞지 않기 때문에 개발자가 실수할 여지가 있습니다.
또한, Vector의 메소드들은 synchronized로 구현되어 있어 멀티 스레드 환경에서는 동기화의 이점이 있으나, 단일 스레드 환경에서는 불필요한 동기화 작업으로 인해 성능 측면에서 좋지 않습니다. 반면에, Deque 인터페이스는 후입선출의 특성을 완전히 유지하면서도 동기화 작업을 가지는 구현체와 그렇지 않은 구현체를 선택할 수 있습니다. 이는 개발자가 필요에 따라 동기화 작업의 오버헤드를 회피하고 성능을 최적화할 수 있도록 합니다.