1. 스택(Stack)
- 후입 선출(LIFO; Last-In, First-Out) 구조의 자료구조
: 가장 나중에 저장된 데이터부터 가장 먼저 꺼내는 방식의 자료구조- 일반적으로 배열 기반 컬렉션 클래스로 구현
: 데이터 추가는 항상 순차적으로 수행되고, 삭제 또한 맨 마지막부터 역순으로 진행하므로
추가/삭제 시 추가 작업이 불필요하기 때문- 다음과 같은 경우에 활용
: 수식 계산, 수식 괄호 검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로 기능 등
2. 스택 구현
- 전체 구현 코드는 여기에서 확인 가능
스택의 주요 기능 정의
Stack 인터페이스
package datastructure.stack;
public interface Stack<E> {
boolean isEmpty();
void push(E e); // 스택에 새로운 데이터를 추가, 늦게 저장될수록 맨 위에 저장
E pop(); // 스택의 맨 위에 저장된 데이터를 삭제
E peek(); // 가장 최근에 저장된 데이터를 반환
void clear(); // 스택에 저장된 모든 데이터를 제거
int getSize(); // 스택에 저장된 데이터의 개수 반환
void dump(); // 스택에 저장된 모든 데이터를 출력
}
배열을 사용한 스택 구현
ArrayBaseStack 클래스
import java.util.Arrays;
public class ArrayBaseStack<E> implements Stack<E> {
private static final int DEFAULT_CAPACITY = 10; // 용량의 초기값
private final int max; // 스택의 최대 용량
private final Object[] stack; // 스택의 본체가 되는 배열
private int top; // 스택의 꼭대기에 해당하는 인덱스 번호
// 지정한 용량을 갖는 스택을 생성
public ArrayBaseStack() {
this(DEFAULT_CAPACITY); // 별도의 용량을 지정하지 않으면 초기값으로 설정
}
public ArrayBaseStack(int max) {
this.max = max; // 스택에 허용된 용량 초기화
this.stack = new Object[max]; // 지정한 용량을 갖고 스택의 본체가 되는 배열 생성
this.top = 0; // 스택의 꼭대기가 되는 인덱스 번호 초기화
}
// 빈 스택인지 확인
@Override
public boolean isEmpty() {
return top <= 0;
}
// 가득 찬 스택인지 확인(배열 기반 스택에서만 이용 가능한 기능)
public boolean isFull() {
return top >= max;
}
@Override
public void push(E e) {
// 1-1. 스택이 가득 찬 경우 그대로 종료
if (isFull()) {
System.out.println("Stack is full");
}
// 1-2. 스택의 꼭대기에 새로운 데이터를 추가
// 2. 꼭대기가 되는 인덱스 번호는 1 증가
stack[top++] = e;
}
@Override
public E pop() {
// 1-1. 스택이 비어 있는 경우 그대로 종료
if (isEmpty()) {
return null;
}
// 구현한 스택을 사용할 실행 코드에서는 실행 도중 스택 내 데이터의 형변환을 수행하지 않음
// 1-2. 스택에 꼭대기가 되는 인덱스 번호를 1 감소시켜 스택의 범위 축소
@SuppressWarnings("unchecked")
E data = (E) stack[--top];
// 2. 삭제된 데이터를 반환
return data;
}
@Override
public E peek() {
// 1-1. 스택이 비어 있는 경우 그대로 종료
if (isEmpty()) {
return null;
}
// 1-2. 스택에 데이터가 존재하면 스택의 꼭대기에 저장된 값을 반환
@SuppressWarnings("unchecked")
E data = (E) stack[top - 1];
return data;
}
// 스택을 비움
@Override
public void clear() {
Arrays.fill(stack, null);
top = 0;
}
// 스택의 용량을 반환(배열 기반 스택에서만 이용 가능한 기능)
public int getCapacity() {
return max;
}
// 스택에 축적된 데이터의 개수를 반환
@Override
public int getSize() {
return top;
}
// 스택에 저장된 모든 데이터를 바닥~꼭대기 순으로 출력
@Override
public void dump() {
if (isEmpty()) {
System.out.println("Stack is empty!!");
return;
}
for (int i = 0; i < top; i++) {
System.out.print(stack[i] + " ");
}
System.out.println();
}
}실행용 샘플 코드 및 실제 실행 결과
public class ArrayBaseStackMain {
public static void main(String[] args) {
ArrayBaseStack<Integer> stack = new ArrayBaseStack<>();
// 스택에 1~5까지의 정수를 순서대로 저장
for (int i = 1; i <= 10; i++) {
stack.push(i);
}
// 현재 스택에 저장된 데이터 개수, 저장된 데이터(꼭대기 → 바닥 순) 출력
System.out.printf("Stack capacity: %d, Stack size: %d\n", stack.getCapacity(), stack.getSize());
stack.dump();
if (stack.isFull()) {
System.out.println("Stack is full!!");
}
System.out.println();
// 스택에 저장된 1개씩 꺼냈을 때, 꺼낸 데이터와 그 때의 스택의 크기 출력
while (!stack.isEmpty()) {
System.out.printf("Popped: %d, Stack size: %d\n", stack.peek(), stack.getSize());
stack.pop();
}
System.out.println();
// 현재 스택이 빈 스택인지 출력
System.out.printf("Stack capacity: %d, Stack size: %d\n", stack.getCapacity(), stack.getSize());
stack.dump();
}
}
연결 리스트를 사용한 스택 구현
ListBaseStack 클래스
package datastructure.stack;
import datastructure.util.Node1;
public class ListBaseStack<E> implements Stack<E> {
private Node1<E> top; // 스택의 꼭대기 노드를 가리키는 변수
private int size; // 스택에 저장된 노드의 개수
// 스택 초기화
public ListBaseStack() {
top = null;
size = 0;
}
// 빈 스택인지 확인
@Override
public boolean isEmpty() {
return top == null;
}
@Override
public void push(E e) {
// 1. 주어진 데이터를 저장할 새로운 노드 생성
Node1<E> newNode = new Node1<>(e, top);
// 2. 새로운 데이터는 기존의 꼭대기 위에 추가
newNode.setNext(top);
// 3. 꼭대기 노드를 새로 추가된 노드로 갱신
top = newNode;
// 4. 스택에 저장된 노드의 개수 1 증가
size++;
}
@Override
public E pop() {
// 1-1. 빈 스택일 경우 그대로 종료
if (isEmpty()) {
return null;
}
// 1-2. 삭제할 데이터는 별도로 저장
E removedData = top.getData();
// 2. 스택의 꼭대기 노드를 바로 밑의 노드로 갱신하여 기존의 꼭대기 노드 삭제
top = top.getNext();
size--;
return removedData;
}
// 현재 스택의 꼭대기에 저장된 데이터를 반환
@Override
public E peek() {
return top.getData();
}
// 스택에 저장된 모든 데이터 삭제
@Override
public void clear() {
while (!isEmpty()) {
pop();
}
top = null;
}
// 스택에 저장된 노드의 개수를 반환
@Override
public int getSize() {
return size;
}
// 스택에 저장된 모든 데이터를 꼭대기에서 바닥 순으로 출력
@Override
public void dump() {
if (isEmpty()) {
System.out.println("Stack is empty!!");
return;
}
Node1<E> current = top;
while (current != null) {
System.out.println(current.getData());
current = current.getNext();
}
}
}실행용 샘플 코드 및 실제 실행 결과
package datastructure.stack;
public class ListBaseStackMain {
public static void main(String[] args) {
Stack<Integer> stack = new ListBaseStack<>();
// 스택에 1~5까지의 정수를 순서대로 저장
for (int i = 1; i <= 5; i++) {
stack.push(i);
}
// 현재 스택에 저장된 데이터 개수, 저장된 데이터(꼭대기 → 바닥 순) 출력
System.out.printf("Stack size: %d\n", stack.getSize());
stack.dump();
System.out.println();
// 스택에 저장된 1개씩 꺼냈을 때, 꺼낸 데이터와 그 때의 스택의 크기 출력
while (!stack.isEmpty()) {
System.out.printf("popped: %d, stack size: %d\n", stack.peek(), stack.getSize());
stack.pop();
}
System.out.println();
// 현재 스택이 빈 스택인지 출력
System.out.println("Stack size: " + stack.getSize());
stack.dump();
}
}
3. Java에서의 스택
- Java 언어에서 스택 자료구조는
java.util.Stack,java.util.ArrayDeque,java.util.LinkedList등의 클래스에서 구현됨- Java에서는 스택 자료구조 사용 시
java.util.Stack클래스보다는java.util.ArrayDeque등의 덱 자료구조의 기능을 사용할 것을 권장
:java.util.Stack의 조상 클래스인java.util.Vector자체의 성능 문제도 존재하지만, 덱 자료구조 자체는 스택/큐의 기능을 모두 사용 가능하여 활용성이 높기 때문
(java.util.ArrayDeque등의 덱 자료구조 관련 기능은 따로 정리)
스택 자료구조 사용 예시
/* 1. java.util.Stack 클래스 사용*/
Stack<Integer> stackExample1 = new Stack<>();
/* 2. 덱 자료구조의 기능을 스택처럼 활용 */
Deque<Integer> stackExample2 = new ArrayDeque<>();
Deque<Integer> stackExample3 = new LinkedList<>();Reference
- Do-it! 자료구조와 함께 배우는 알고리즘 입문(Bohyoh Shibata 지음, 강민 옮김)
- 윤성우의 열혈 자료구조(윤성우 지음)
- 자바의 정석 3판(남궁성 지음)
