💡 책처럼 쌓이는 자료구조가 스택
스택(STACK)이라는 단어에는 ‘쌓다’라는 뜻이 있습니다. 그 의미대로 데이터를 쌓아서 관리하는 방식이 스택입니다.
무언가 조사할 때, 책상 위에 참고 자료로 사용한 책을 쌓아 놓았던 경험이 있을 것입니다.
1. 책장에서 책 한 권을 꺼내 읽고, 그 책을 책상 옆에 놓아 둔다.
2. 그리고 다른 책을 꺼내 읽고, 그 책을 방금 놓은 책 위에 쌓는다.
3. 또 다른 책을 꺼내 읽고, 다 읽은 책 위에 쌓는다.이 과정을 반복한다면 결과적으로 책상 위에는 한 무더기의 책이 쌓여 버릴 것입니다.
이렇게 많은 책이 쌓여있는 상태에서 중간에 있는 책을 꺼내려고 한다면?
쌓아 놓은 책이 무너져 버릴 수도 있습니다.
따라서 가운데에 있는 책을 꺼내려면, 가장 위에 쌓인 책부터 한 권 한 권 차례대로 빼내야 할 것입니다. 이 작업을 원하는 책이 맨 위에 놓일 때까지 반복합니다.
스택이란 이와 같이 ‘책상에 책을 쌓듯’ 데이터를 관리하는 방법입니다.
스택의 데이터 관리법은 두 가지로 이루어집니다.
- 데이터를 넣는(쌓는) 작업을 푸시(PUSH)
- 데이터를 꺼내는 작업을 팝(POP)
이렇게 스택처럼 마지막에 입력된 데이터가 먼저 출력되는 특징을 갖는 데이터 관리 방식을 LIFO(Last In, First Out) 또는 FILO(First In, Last Out)라고 부릅니다.
스택 구현(JAVA)
Char 자료형을 받는 스택을 코드로 작성해보겠습니다.
charStack.java
메소드 설명
pop()
가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다
push(item)
스택의 최 상위에 새로운 자료를 삽입한다
isEmpty()
스택이 empty 상태인지 확인한다. 비어 있으면 true를 반환한다
clear()
스택에 존재하는 모든 자료들을 삭제한다
peek()
가장 최 상위에 위치한 자료를 추출한다
pop 메소드와는 달리 스택에서 제거하지는 않는다.
dump()
스택 안에 있는 모든 데이터를 표시한다
코드
package project;
interface Stack {
public boolean isEmpty();
public boolean isFull();
public void push(char item);
public char pop();
public char peek();
public void clear();
}
public class charStack implements Stack {
private int max; // 스택 용량
private int ptr; // 스택 포인터
private char[] stk; // 스택 본체
public charStack(int capacity) {
ptr = 0; // 포인터
max = capacity; // 스택 크기
try {
stk = new char[max]; // 스택 본체용 배열을 생성
} catch (OutOfMemoryError e) {
max = 0;
}
}
// 실행 시 예외 : 스택이 비어 있음
public class EmptycharStackException extends RuntimeException {
public EmptycharStackException() {
}
}
// 실행 시 예외 : 스택이 가득 참
public class OverflowcharStackException extends RuntimeException {
public OverflowcharStackException() {
}
}
@Override
public boolean isEmpty() {
return ptr <= 0;
}
@Override
public boolean isFull() {
return ptr >= max;
}
@Override
public void push(char item) {
if (ptr >= max) {
throw new OverflowcharStackException();
}
stk[ptr++] = item;
}
@Override
public char pop() {
if (ptr <= 0) { // 스택이 비어 있음
throw new EmptycharStackException();
}
return stk[--ptr];
}
@Override
public char peek() {
if (ptr <= 0)
throw new EmptycharStackException();
return stk[ptr - 1];
}
@Override
public void clear() { // 스택을 비움
ptr = 0;
}
// interface 외의 메소드
public int size() { // 스택에 쌓여 있는 데이터 수를 반환
return ptr;
}
public int capacity() { // 스택의 용량을 반환
return max;
}
public void dump() { // 스택 안에 있는 모든 데이터를 표시하는 메소드
if (ptr <= 0)
System.out.println("스택이 비어있습니다.");
else {
for (int i = 0; i < ptr; i++) {
System.out.print(stk[i] + " ");
}
System.out.println();
}
}
}StackTest.java
package project;
import java.util.Scanner;
public class StackTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
charStack s = new charStack(64); // 64 크기의 char스택 생성
while(true) {
System.out.println("현재 데이터 수 : " + s.size() + "/" + s.capacity());
System.out.println("(1) 푸시 (2) 팝 (3)피크 (4) 덤프 (0) 종료 : ");
int menu = sc.nextInt();;
if(menu == 0 ) break; // 종료
char x;
switch(menu) {
case 1: // push
System.out.println("data : ");
x = sc.next().charAt(0);
try {
s.push(x);
} catch (charStack.OverflowcharStackException e) {
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2: // pop
try {
x = s.pop();
System.out.println("팝한 데이터는 "+ x + "입니다.");
} catch (charStack.EmptycharStackException e ) {
System.out.println("스택이 비어 있습니다.");
}
break;
case 3: // peek
try {
x = s.peek();
System.out.println("피크한 데이터는 "+ x + "입니다.");
}catch(charStack.EmptycharStackException e) {
System.out.println("스택이 비어 있습니다.");
}
break;
case 4: // dump
s.dump();
break;
}
}
}
}회고
- 자료구조를 이해하는 것과 구현하는 것은 다르다는 것을 느꼈다.
- 정확히 이해해야 원하는 기능을 만들어 낼 수 있다는 것이 피부로 와닿았다.
기록중