Groo
스택에 대해서 본문
안녕하세요, 오늘은 새로운 자료구조인 스택에 대해서 알아보려고 합니다.
스택의 기본 개념과 내용을 알아본 후 스택을 활용한 간단한 프로그램 또한 구현을 해볼 것입니다.
🤷♂️ 스택은 무엇인가요?
Stack이라는 단어의 뜻은 채우다는 의미입니다. 단어의 뜻과 같이 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조입니다. 스택은 다른 자료구조들과 달리 데이터의 입력과 출력 순서가 후입 선출이라는 것이 중요합니다. 후입 선출의 의미는 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 것을 의미합니다. 그럼 아래의 표를 통해 스택에 대한 간단한 개념 정리를 해보도록 하겠습니다.
| 구성 모습 | 바닥 (Bottom) / 꼭대기 (Top) |
| 개념 및 의미 | 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 |
| 데이터 입력 방식 | 푸시 (Push) |
| 데이터 출력 방식 | 팝 (Pop) |
| 데이터 입력과 출력 순서 | 후입선출 (LIFO, Last In First Out) |
🎯 스택의 구조는 어떻게 되나요?
그럼 위의 표에 적혀있는 스택의 구성 모습과 데이터 입력, 출력 방식은 실제로 어떻게 이루어지는 것일까요? 이 스택의 구조는 정말 쉽게 되어있습니다. 그럼 아래의 접시 예시와 함께 실제로 데이터가 일시적으로 입력되고 출력되는 모습을 보도록 하겠습니다.
위의 그림은 실제로 스텍에 데이터가 푸시되고 팝 되는 모습을 접시를 쌓는 모습에 비유하여 구성한 그림입니다. 푸시와 팝 즉 데이터의 입력과 출력이 모두 꼭대기 Top에서 이루어지는 모습을 볼 수 있습니다. 그럼 이번에는 더욱 구체적으로 살펴보겠습니다.
실제 스택을 활용해서 프로그램을 구현할 때 또한 위의 그림과 같은 원리로 작동을 합니다. 따라서 프로그램 구현을 하기 전 위의 구조를 이해하는 것이 중요합니다. 스택의 푸시, 팝, Top, Bottom 등이 어떻게 작동을 하고 사용이 되는지 꼭 이해하기 바랍니다.
🏹 스택 필수 요소는 무엇인가요?
이번에는 위에서 배운 내용을 바탕으로 실제로 스택을 구현해보도록 하겠습니다. 스택을 올바르게 구현을 하기 위해서는 필요한 변수, 매서드 등 다양한 것이 필요합니다. 그럼 지금부터 스택 구현에 필요한 내용들을 천천히 살펴보도록 하겠습니다. 아래를 보시죠!
📕 스택 멤버 변수
스택을 구현하기 위해서는 프로그램에서 사용할 수 있는 멤버 변수가 필요합니다. 아래와 같이 스택의 크기 즉 용량을 저장하는 max 변수와 스택의 현재 저장되어있는 데이터의 크기를 저장하는 ptr 변수 및 스택의 본체 즉 데이터들을 저장할 배열 변수 stk 또한 필요합니다. 변수의 이름들은 개발자의 성향에 맞게 지어도 상관은 없으나 변수의 이름에 각각 고유의 의미를 지니어야 합니다.
class IntStack{
int max;
int ptr;
int[] stk;
}📘 스택 매서드
스택을 구현할 때 가장 중요한 것이 바로 푸시(Push), 팝(Pop) 데이터를 입력하고 출력하는 역할을 하는 매서드입니다. 푸시(Push) 매머드와 같은 경우는 스택에 저장할 데이터를 매개변수로 전달받아 현재 배열에서 가장 꼭대기에 있는 곳에 데이터를 추가합니다.
그 후 ptr의 값을 1 증가시켜 데이터가 입력되었다는 것을 알립니다. 만약 ptr의 값이 max의 값과 같다면 현재 스택은 빈 공간 없이 모두 데이터가 존재한다는 것이며 더 이상 데이터를 입력하지 못하도록 예외처리를 진행합니다. 아래의 코드를 보시겠습니다.
public int push(int x) throws OverflowIntStackException{
if(ptr == max) throw new OverflowIntStackException();
return stk[ptr++] = x;
}반면에 팝(Pop) 메서드는 푸시(Push) 매서드와 달리 스택의 데이터를 출력하는 매서드입니다. 팝(Pop) 매서드가 호출이 되었다면 현재 스택 배열에서 꼭대기 즉 최상위 데이터를 반환합니다. 그 후 ptr의 값을 -1 감소시켜 데이터가 출력됬다는 것을 알립니다.
그러나 만약 ptr의 값이 0이거나 0보다 값이 작다면 스택에 현재 데이터가 아무것도 존재하지 않는다는 의미이기 때문에 빈 공간에서 데이터를 출력하려다가 NPE 오류를 발생시키지 않게 하기 위해 예외 처리를 따로 설정을 해두면 됩니다. 아래의 코드를 보시죠!
public int pop() throws EmptyIntStackException{
if(ptr <= 0) throw new EmptyIntStackException();
return stk[--ptr];
}대표적인 매서드 푸시(Push), 팝(Pop)을 포함하여 스택에 관련된 다양한 매서드들이 존재합니다. 예를 들면 최상위 데이터 반환, 배열 데이터 검색, 초기화, 용량 확인, 데이터 수 확인, 스택 확인 등 다양한 매서드들이 존재하지만 모두 소개를 하는 것은 불가능하다고 생각하였습니다. 그래서 아래의 코드에 주석 처리를 하여 어떤 매서드가 어떤 기능을 한다고 정리를 하였습니다. 참고 부탁드립니다.
public class IntStack {
public int max; // stk 배열의 용량
public int ptr; // stk 배열의 스택 포인터
public int[] stk; // 스택 배열의 본체
// 실행 시 예외 : 스택이 비어 있음
public class EmptyIntStackException extends RuntimeException{
public EmptyIntStackException(){}
}
// 실행 시 에외 : 스택이 가득 참
public class OverflowIntStackException extends RuntimeException{
public OverflowIntStackException(){}
}
public IntStack(int capacity){
ptr = 0;
max = capacity;
try{ stk = new int[max]; }
catch (OutOfMemoryError e){ max = 0; }
}
// 스택 데이터 추가
public int push(int x) throws OverflowIntStackException{
if(ptr == max) throw new OverflowIntStackException();
return stk[ptr++] = x;
}
// 스택 데이터 제거
public int pop() throws EmptyIntStackException{
if(ptr <= 0) throw new EmptyIntStackException();
return stk[--ptr];
}
// 스택 최상위 데이터 전달
public int peak() throws EmptyIntStackException{
if(ptr <= 0) throw new EmptyIntStackException();
return stk[ptr - 1];
}
// 스택 검색 데이터 인덱스 전달
public int indexOf(int x){
for(int i = ptr - 1; i >= 0; i--){
if(stk[i] == x) return stk[i];
}
return -1;
}
// 스택 데이터 초기화
public void clear(){
ptr = 0;
}
// 스택 용량 전달
public int capacity(){
return max;
}
// 스택 데이터 용량 전달
public int size(){
return ptr;
}
// 스택 빈 공간 전달
public boolean isEmpty(){
return ptr <= 0;
}
// 스택 가득 찬 공간 전달
public boolean isFull(){
return ptr == 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();
}
}
}📸 스택 구현해보기!
이제 스택을 구현하기 위해 변수, 매서드 등을 알아보았다면 스택을 활용한 간단한 프로그램을 제작해보도록 하겠습니다. 위의 IntStack 클래스를 사용하여 프로그램을 만들 것이며 프로그램의 테스트를 위해 IntStackTester 클래스를 제작할 것입니다. IntStackTester 클래스에서는 사용자에게 기능에 대한 UI를 제공하고 사용자로부터 어떤 기능을 수행할 것인지 입력받습니다.
public class IntStackTester {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
IntStack intStack = new IntStack(64);
int input = 1;
while(input != 0){
System.out.println("현재 데이터 수 : " + intStack.size() + "/" + intStack.capacity());
System.out.print("(0) 종료 (1) 푸시 (2) 팝 (3) 피크 (4) 덤프 : "); input = scanner.nextInt();
switch (input){
case 0: break;
case 1:{
System.out.print("데이터 : "); int data_input = scanner.nextInt();
try{ intStack.push(data_input); }
catch (IntStack.OverflowIntStackException ex){
System.out.println("스택이 가득 찼습니다.");
} break;
}
case 2: {
try{System.out.println("팝한 데이터는 " + intStack.pop() + "입니다.");}
catch (IntStack.EmptyIntStackException ex){
System.out.println("스택이 비어 있습니다.");
} break;
}
case 3: {
try{System.out.println("피크한 데이터는 " + intStack.peak() + "입니다.");}
catch (IntStack.EmptyIntStackException ex){
System.out.println("스택이 비어 있습니다.");
} break;
}
case 4: intStack.dump(); break;
}
System.out.println();
}
}
}👍 글을 마치며
오늘은 스택에 대해서 알아보는 시간을 가졌습니다. 스택을 활용하여 간단한 프로그램도 구현을 해보았습니다. 스택은 앞으로 프로그램을 개발할 때 정말 중요하며 그 공간에 데이터가 어떻게 입력이 되고 출력이 되는지 구조를 알고 있어야 코드의 구현을 조금 더 효율적으로 할 수 있습니다. 다음번에는 스택과 비슷한 개념을 가지고 있는 큐에 대해 알아보는 시간을 가지도록 하겠습니다.
참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편
'프로그래밍 기초 > Data structure & Algorithm' 카테고리의 다른 글
| 재귀에 대해서 (0) | 2020.03.05 |
|---|---|
| 큐에 대해서 (2) | 2020.02.13 |
| 이진 검색과 시간 복잡도에 대해서 (0) | 2020.02.12 |
| 선형 검색과 보초법에 대해서 (0) | 2020.02.11 |
| 자료구조와 알고리즘에 대해서 (0) | 2020.02.10 |
