스택이란?
스택(stack)은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력순서는
후입선출(LIFO : Last In First Out)입니다. 즉 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.
스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 합니다. 스택에 데이터를 푸시하고 팝하는 과정은 테이블 위에 접시를 겹겹이 쌓는 것처럼 데이터를 넣고 꺼내는 작업을 위쪽부터 수행합니다. 이렇게 푸시와 팝이 이루어지는 쪽을 꼭대기(top)이라 하고, 그 반대쪽은 스택의 가장 아랫부분을 바닥(bottom)이라고 합니다.
※푸시와 팝의 예
스택 만들기
스택을 구현하는 프로그램을 만들어 보겠습니다 .기본 구조를 익히기 위해 스택을 생성할 때 용량(스택에 쌓을 수 있는 최대 데이터 수)을 결정하는 고정 길이 스택을 만들겠습니다. 여기서 스택에 저장하는 값은 int형 입니다.
※정수형 스택과 예외 생성
IntStack.java
//int형 고정길이 스택
public class IntStack {
private int[] stk; //스택용 배열
private int capacity; // 스택 용량
private int ptr; //스택 포인터
//실행 시 예외: 스택이 비어 있음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException{}
}
//실행 시 예외: 스택이 가득 참
public class OverFlowIntStackException extends RuntimeException {
public OverFlowIntStackException{}
}
//생성자
public IntStack(int maxLen) {
ptr = 0;
capacity = maxLen;
try {
stk = new int[capacity];
} catch (OutOfMemoryError e) {
e.printStackTrace();
capacity = 0;
}
}
}클래스 IntStack에서 실행할 때 예외는 EmptyIntStackException과 OverflowStackException의 두가지입니다. 이 예외는 push, popm peek 메서드에서 사용됩니다.
<스택용 배열 stk>
푸시된 데이터를 저장하는 스택용 배열입니다. 인덱스 0인 요소가 스택의 바닥입니다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]입니다
<스택 용량 capacity>
스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타내는 int형 필드입니다.
<스택 포인터 ptr>
스택에 쌓여 있는 데이터 수를 나타내는 필드입니다. 이 값을 스택 포인터(stack point)라고 합니다.
물론 스택이 비어 있으면 prt값은 0이 되고, 가득 차 있으면 capacity값과 같습니다.
<생성자 IntStack>
생성자는 스택용 배열 본체를 생성하는 등 준비 작업을 합니다. 생성할 때 스택은 비어 있으므로(데이터가 하나도 쌓여 있지 않은 상태) 스택 포인터 prt값을 0으로 합니다. 그리고 매개 변수 maxLen으로 전달받은 값을 스택 용량을 나타내는 capacity에 대입하고 요솟수가 capacity인 배열 본체를 생성합니다. 따라서 스택용 배열 본체의 개별 요소에 접근하는 인덱스는 바닥부터
stk[0], stk[1] … stk[capacity - 1]
이 됩니다
※푸시(push)와 팝(pop) , 피크(peek) 메서드 생성
IntStack.java
//스택에 x를 푸시
public int push(int x) throws OverFlowIntStackException {
if (ptr >= capacity)
throw new OverFlowIntStackException();
return stk[ptr++] = x;
}
//스택에서 데이터를 팝(꼭대기에서 데이터를 꺼냄)
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
//스택에서 데이터를 피크(꼭대기에 있는 데이터를 들여다봄)
public int peek() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}<푸시 메서드 push>
스택에 데이터를 푸시하는 메서드입니다. 스택이 가득 차서 푸시할 수 없는 경우 예외 Over flowIntStackException을 내보냅니다.
전달 받은 데이터 x를 배열 요소 stk[ptr]에 저장하고 스택 포인터를 1 증가시킵니다. 메서드의 반환값은 푸시한 값입니다.
<팝 메서드 pop>
스택의 꼭대기에 있는 데이터를 팝(제거)하고 그 값을 반환하는 메서드입니다. 스택이 비어있어 팝을 할 수 없는 경우 예외 EmptyIntStackException을 내보냅니다.
푸시와 마찬가지로 실질적으로 1행만으로 된 메서드입니다.
먼저 스택 포인터 ptr값 1 감소시키고 그때 stk[ptr]에 저장되어 있는 값을 반환합니다.
<피크 메서드 peek>
스택의 꼭대기에 있는 데이터를 들여다보는 메서드입니다. 스택이 비어 있으면 예외 EmptyIntStackException을 내보냅니다.
스택이 비어 있지 않으면 꼭대기에 있는 요소 stk[ptr-1]의 값을 반환합니다. 이때 데이터를 넣거나 뺴지 않으므로 스택 포인터는 변화시키지 않습니다.
메서드 push, pop, peek 에서는 스택이 가득 찼는지 또는 비어 있는지를 메서드 첫머리에서 판단합니다.
<스택의 모든 요소를 삭제하는 메서드 clear>
IntStack.java
//스택의 모든 요소를 삭제하는 메서드 clear
//스택을 비움
public void clear() {
ptr = 0;
}스택에서 푸시하고 팝하는 모든 작업은 스택 포인터를 바탕으로 이루어집니다. 따라서 스택의 배열 요솟값을 변경할 필요가 없습니다. 모든 요소를 삭제하는 작업은 스택 포인터 ptr값을 0으로 하면 끝납니다.
<검색 메서드 indexOf>
IntStack.java
//스택의 모든 요소를 삭제하는 메서드 clear
//스택을 비움
public void clear() {
ptr = 0;
}스택 본체의 배열 stk에 x와 값은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드입니다.
스택에서 검색을 꼭대기 위쪽부터 바닥으로 선형 검색을 수행합니다.
stk[capacity -1] … stk[1], stk[0] 순으로 탐색합니다.
<용량을 확인하는 메서드 getCapacity>
IntStack.java
//스택의 용량을 반환
public int getCapacity() {
return capacity;
}스택의 용량을 반환하는 메서드입니다. capacity값을 그대로 반환합니다.
<데이터 개수를 확인하는 메서드 size>
IntStack.java
//스택에 쌓여있는 데이터의 개수 반환
public int size() {
return ptr;
}<스택이 비어 있는지 검사하는 메서드 isEmpty>
IntStack.java
//스택이 비어있는지 판단
public boolean isEmpty() {
return ptr <= 0;
}<스택이 가득 차있는지 검사하는 메서드 isFull>
IntStack.java
//스택이 가득 찼는지 판단
public boolean isFull() {
return ptr >= capacity;
}<스택의 모든 데이터를 바닥 → 꼭대기 순서로 출력>
IntStack.java
//스택의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
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.java 전체 코드
public class IntStack {
private int[] stk; //스택용 배열
private int capacity; // 스택 용량
private int ptr; //스택 포인터
//생성자
public IntStack(int maxLen) {
ptr = 0;
capacity = maxLen;
try {
stk = new int[capacity];
} catch (OutOfMemoryError e) {
e.printStackTrace();
capacity = 0;
}
}
//실행 시 예외: 스택이 비어 있음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException {
}
}
//실행 시 예외: 스택이 가득 참
public class OverFlowIntStackException extends RuntimeException {
public OverFlowIntStackException {
}
}
//스택에 x를 푸시
public int push(int x) throws OverFlowIntStackException {
if (ptr >= capacity)
throw new OverFlowIntStackException();
return stk[ptr++] = x;
}
//스택에서 데이터를 팝(꼭대기에서 데이터를 꺼냄)
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
//스택에서 데이터를 피크(꼭대기에 있는 데이터를 들여다봄)
public int peek() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}
//스택의 모든 요소를 삭제하는 메서드 clear
//스택을 비움
public void clear() {
ptr = 0;
}
//스택에서 x를 찾아 인덱스(없으면 -1)를 반환
public int inedxOf(int x) {
for (int i = ptr - 1; i >= 0; i--) {
if (stk[i] == x) {
return i;
}
}
return - 1;
}
//스택의 용량을 반환
public int getCapacity() {
return capacity;
}
//스택에 쌓여있는 데이터의 개수 반환
public int size() {
return ptr;
}
//스택이 비어있는지 판단
public boolean isEmpty() {
return ptr <= 0;
}
//스택이 가득 찼는지 판단
public boolean isFull() {
return ptr >= capacity;
}
//스택의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
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();
}
}
}
스택 활용하기
StackMain.java
import java.util.Scanner;
public class StackMain {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
IntStack stack = new IntStack(64); //최대 64개를 푸시할 수 있는 스택 생성
while (true) {
System.out.println(); //메뉴 구분을 위한 빈행 추가
System.out.printf("현재 데이터 개수: %d / %d\n", stack.size(),stack.getCapacity());
System.out.print("(1) 푸시 (2) 팝 (3) 피크 (4) 덤프 (0) 종료" );
int menu = sc.nextInt();
if(menu == 0)break;
int x;
switch (menu) {
case 1:
System.out.print("데이터: ");
x = sc.nextInt();
try {
stack.push(x);
System.out.printf("데이터 값 <%d> 푸시 완료\n",x);
} catch (IntStack.OverFlowIntStackException e) {
e.printStackTrace();
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2:
try {
x = stack.pop();
System.out.printf("팝으로 나온 데이터 : %d", x);
} catch (IntStack.EmptyIntStackException e) {
e.printStackTrace();
System.out.println("스택이 비어있습니다");
}
break;
case 3:
try {
x = stack.peek();
System.out.printf("피크로 나온 데이터 : %d", x);
} catch (IntStack.EmptyIntStackException e) {
e.printStackTrace();
System.out.println("스택이 비어있습니다");
}
break;
case 4:
stack.dump();
break;
}
}
}
}
결과
-
실행시
-
푸시
데이터 5,7,3 입력
-
팝
-
피크
- 덤프
- 종료
