데이터를 저장하고 관리하는 방식은 프로그램의 효율성과 복잡성에 큰 영향을 미친다. 다양한 자료구조 중 스택(Stack)은 ‘후입선출(Last In First Out, LIFO)’이라는 단순하지만 강력한 원칙을 따르는 추상 자료형(Abstract Data Type)이다. 이 원칙은 가장 나중에 삽입된(Pushed) 데이터가 가장 먼저 제거되는(Popped)구조를 의미한다
스택의 기본 개념과 원리
스택의 작동 방식을 이해하기 좋은 비유는 쌓여있는 접시 더미이다. 설거지 후 접시를 쌓을 때, 가장 먼저 놓은 접시는 맨 아래에 깔리고, 그 위에 접시를 계속 쌓아 올린다. 접시를 사용할 때는 가장 위에 있는 접시부터 꺼내게 된다. 이처럼 가장 나중에 놓인 접시가 가장 먼저 사용되는 데이터 구조가 스택이다
TOP (가장 최근에 PUSH된 데이터) +-----+ | D | +-----+ | C | +-----+ | B | +-----+ | A | +-----+ BOTTOM (가장 오래된 데이터)
후입선출(LIFO) 원칙은 스택의 핵심이며, 다음과 같은 주요 연산으로 구현된다
- push: 스택의 가장 위에 데이터를 삽입(추가)한다
- pop: 스택의 가장 위에 있는 데이터를 제거하고 반환한다
- peek: 스택의 가장 위에 있는 데이터를 제거하지 않고 참조(확인)만 한다
- isEmpty: 스택이 비어있는지 여부를 확인한다
스택의 구현 방식
스택은 후입선출(LIFO) 원칙만 충족한다면, 내부적으로 어떤 자료구조를 사용하여 구현하든 상관없다. 주로 배열(Array)이나 연결 리스트(Linked List)를 사용하여 구현한다
여기서는 연결 리스트를 활용하여 스택을 구현하는 아이디어를 살펴보보자. 연결 리스트는 head 노드를 통해 모든 노드를 관리하는데, 이 head를 스택의 ‘TOP’으로 활용하면 스택을 효율적으로 만들 수 있다
- push 연산: 데이터를 삽입할 때, 무조건 연결 리스트의 가장 앞(head)에 새로운 노드를 추가한다
- pop 연산: 데이터를 제거할 때, 무조건 연결 리스트의 가장 앞(head)에 있는 노드를 제거한다
정수 1, 2, 3, 4를 스택에 PUSH (연결 리스트)
- push(1): [1] (1이 head)
- push(2): [2, 1] (2가 새로운 head, 1의 앞에 연결)
- push(3): [3, 2, 1] (3이 새로운 head)
- push(4): [4, 3, 2, 1] (4가 새로운 head)
스택에서 데이터 POP
- pop(): 4가 제거된다. 스택은 [3, 2, 1]이 되고 3이 head가 된다
- pop(): 3이 제거된다. 스택은 [2, 1]이 되고 2가 head가 된다
- pop(): 2이 제거된다. 스택은 [1]이 되고 1이 head가 된다
- pop(): 1이 제거된다. 스택은 []이 된다
이렇게 한쪽 끝(연결 리스트의 head)에서만 삽입과 제거를 수행하면 간단하게 후입선출(LIFO) 원칙을 따르는 스택이 된다
스택 활용 사례
언뜻 보기에는 순서가 역행하는 스택은 쓸모없어 보일 수 있지만, 스택은 다양한 컴퓨터 과학 분야에서 매우 중요한 역할을 한다
실행 취소 (Undo) 기능
포토샵이나 그림판 같은 프로그램을 사용할 때, 실수하면 Ctrl+Z를 눌러 작업을 되돌린다. 이 ‘실행 취소’ 기능은 스택을 활용한 대표적인 예시이다. 컴퓨터는 사용자의 모든 작업을 스택에 순서대로 기록한다. 사용자가 Ctrl+Z를 누르면, 스택의 가장 위에 있는(가장 최근에 들어온) 작업 내역을 꺼내어 실행 취소하고 버리게 된다. 이 기능을 구현하는 데 스택이 없다면 개발자는 많은 시행착오를 겪어야 할 것이다
괄호 매칭 검사
프로그래밍 언어의 문법 검사기나 컴파일러는 코드 내의 괄호{(, ), {, }, [, ])가 올바르게 짝을 이루는지 검사할 때 스택을 활용한다
예시: { int a = (1 + 100); } 코드 검사
- { 발견: 여는 중괄호를 스택에 push 한다. Stack: [ { ]
- ( 발견: 여는 소괄호를 스택에 push 한다. Stack: [ {, ( ]
- ) 발견: 닫은 소괄호를 만났다. 스택에서 가장 위에 있는 요소 [ ( ]를 pop 하여 이 닫는 괄호의 짝이 맞는지 확인한다. 짝이 맞으므로 통과한다. Stack: [ { ]
- } 발견: 닫는 중괄호를 만났다. 스택에서 가장 위에 있는 요소 [ { ]를 pop 하여 짝이 맞는지 확인한다. 짝이 맞으므로 통과한다. Stack: []
코드를 전부 검사한 후 스택이 비어있다면 문법 에러가 없다고 판단한다. 만약 스택에 데이터가 남아있거나, 닫는 괄호를 만났는데 스택이 비어있거나 짝이 맞지 않는다면 문법에 문제가 있는 것으로 판단하여 에러를 발생시킨다.
Java를 이용한 스택 구현 (연결 리스트 기반)
이전에 구현한 Node와 LinkedList 클래스를 활용하여 Java로 스택을 구현해 보자
public class Stack {
private LinkedList list;
public Stack() {
this.list = new LinkedList();
System.out.println("스택이 생성되었습니다.");
}
/**
* 스택의 가장 위에 데이터를 삽입(push)한다
* 연결 리스트의 가장 앞(head)에 데이터를 추가하는 방식으로 구현한다
* @param data 삽입할 데이터
*/
public void push(int data) {
list.insertAt(0, data); // 연결 리스트의 0번 인덱스에 삽입 (가장 앞)
System.out.println(data + "를 스택에 PUSH 했습니다.");
}
/**
* 스택의 가장 위에 있는 데이터를 제거하고 반환(pop)한다
* 연결 리스트의 가장 앞(head)에 있는 데이터를 제거하는 방식으로 구현한다
* 스택이 비어있으면 null을 반환한다. (EmptyStackException 같은 예외를 던질 수도 있지만 여기서는 간단히 null 반환)
* @return 제거된 노드 (데이터 포함), 스택이 비어있으면 null 반환
*/
public Node pop() {
if(isEmpty()) {
System.out.println("스택이 비어있어 POP 할 데이터가 없습니다. (null 반환)");
return null;
}
Node poppedNode = list.deleteAt(0); // 연결 리스트의 0번 인덱스 노드 제거
System.out.println(poppedNode.getData() + "를 스택에서 POP 했습니다.");
return poppedNode;
}
/**
* 스택의 가장 위에 있는 데이터를 제거하지 않고 참조(peek)만 한다
* 연결 리스트의 가장 앞(head)에 있는 데이터를 참조하는 방식으로 구현한다
* 스택이 비어있으면 null을 반환한다. (혹은 EmptyStackException 발생도 가능)
* @return 가장 위에 있는 노드 (데이터 포함), 스택이 비어있으면 null 반환
*/
public Node peek() {
if (isEmpty()) {
System.out.println("스택이 비어있어 PEEK 할 데이터가 없습니다. (null 반환)");
return null;
}
Node topNode = list.getNodeAt(0); // 연결 리스트의 0번 인덱스 노드 참조
System.out.println("스택의 TOP 데이터: " + topNode.getData());
return topNode;
}
/**
* 스택이 비어있는지 여부를 확인한다
* @return 스택이 비어있으면 true, 그렇지 않으면 false
*/
public boolean isEmpty() {
return list.getSize() == 0;
}
}
Stack push
public class StackMain {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
}
}
/*
스택이 생성되었습니다.
1을 인덱스 0에 삽입했습니다. // 연결 리스트 메시지
1을 스택에 PUSH 했습니다.
2를 스택에 PUSH 했습니다.
3을 스택에 PUSH 했습니다.
4를 스택에 PUSH 했습니다.
*/
Stack pop
public class StackMain {
public static void main(String[] args) {
Stack stack = new Stack();
Node node;
node = stack.pop(); // 4
if (node != null) System.out.println("POP된 데이터: " + node.getData());
node = stack.pop(); // 3
if (node != null) System.out.println("POP된 데이터: " + node.getData());
node = stack.pop(); // 2
if (node != null) System.out.println("POP된 데이터: " + node.getData());
node = stack.pop(); // 1
if (node != null) System.out.println("POP된 데이터: " + node.getData());
}
}
/*
인덱스 0의 노드 (4)를 제거했습니다. // 연결 리스트 메시지
4를 스택에서 POP 했습니다.
POP된 데이터: 4
3를 스택에서 POP 했습니다.
POP된 데이터: 3
2를 스택에서 POP 했습니다.
POP된 데이터: 2
1를 스택에서 POP 했습니다.
POP된 데이터: 1
*/
Stack peek
public class StackMain {
public static void main(String[] args) {
Stack stack = new Stack();
// PEEK을 확인하기 위해 PUSH
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
// PEEK
node = stack.peek(); // 40
if (node != null) System.out.println("\n현재 TOP 데이터 (PEEK): " + node.getData());
stack.pop(); // 40 제거
node = stack.peek(); // 30
if (node != null) System.out.println("POP 후 TOP 데이터 (PEEK): " + node.getData());
System.out.println("스택이 비어있는가? " + stack.isEmpty()); // false (10, 20, 30 남아있음)
}
}
/*
/... 스택 생성 .../
현재 TOP 데이터 (PEEK): 40
인덱스 0의 노드 (40)를 제거했습니다. // 연결 리스트 메시지
40를 스택에서 POP 했습니다.
인덱스 0의 노드: 30
스택의 TOP 데이터: 30
POP 후 TOP 데이터 (PEEK): 30
스택이 비어있는가? false
*/
Stack isEmpty
public class StackMain {
public static void main(String[] args) {
Stack stack = new Stack();
stack.pop(); // 30 제거
stack.pop(); // 20 제거
stack.pop(); // 10 제거
System.out.println("스택이 비어있는가? " + stack.isEmpty()); // true (모두 제거됨)
Node resultNode = stack.pop(); // 빈 스택에서 pop 시도
System.out.println("빈 스택에서 POP 시도 결과: " + resultNode); // null
}
}
/*
30를 스택에서 POP 했습니다.
20를 스택에서 POP 했습니다.
10를 스택에서 POP 했습니다.
스택이 비어있는가? true
스택이 비어있어 POP 할 데이터가 없습니다. (null 반환)
*/