Stack이란?
•
같은 타입의 자료를 순차적으로 저장하는 직선형 자료 구조
먼저 들어간 자료가 나중에 나오는 LIFO(Last In First Out) 구조Stack의 사용
•
음료수 진열대 (먼저 들어간 음료수가 나중에 나옴)
•
인터넷 브라우저 창 (뒤로 가기, 앞으로 가기 등)
Stack의 구현
•
isEmpty
◦
스택이 empty 상태인지 확인한다
•
push(삽입)
◦
스택의 최상위에 새로운 자료를 삽입한다
•
pop(추출)
◦
가장 최상위에 위치한 자료를 추출한 후에 스택에서 제거한다
•
peek
◦
가장 최상위에 위치한 자료를 추출한다
◦
pop 메소드와는 달리 스택에서 제거하지는 않는다.
•
clear
◦
스택에 존재하는 모든 자료들을 삭제한다
예시
import java.util.Scanner;
class Stack {
private int top;
private int stackSize;
private char stackArr[]; // char이 아닌 int object 다 가능
// 스택을 생성하는 생성자
public Stack(int stackSize) {
top = -1; // 스택 포인터 초기화
this.stackSize = stackSize; // 스택 사이즈 설정
stackArr = new char[this.stackSize]; // 스택 배열 생성
}
// 스택이 비어 있는지 확인
// 스택 포인터가 -1인 경우 데이터가 없는 상태이므로 true
// 그렇지 않은 경우 false를 리턴
public boolean isEmpty() {
return (top == -1); // top은 배열의 개수가 아닌 인덱스를 의미
}
// 스택이 가득 차 있는지 확인
// 스택 포인터가 스택의 마지막 인덱스와 동일한 경우 true
// 그렇지 않은 경우 false를 리턴
public boolean isFull() {
return (top == this.stackSize -1); // 배열이기 때문에 -1
}
// 스택에 데이터 추가
public void push(char item) {
if(isFull()) {
System.out.println("스택에 꽉 차 있습니다");
} else {
// 다음 스택 포인터가 가리키는 인덱스에 데이터 추가
stackArr[++top] = item; // 넣은 다음 증가시켜야 하기 때문에 ++top
System.out.println("입력된 문자 " + item);
}
}
// 스택의 최상위에서 데이터 추출 후 삭제
public char pop() {
if(isEmpty()){
System.out.println("스택이 비어 있습니다");
return 0; // 비어 있으면 종료
} else {
System.out.println("삭제된 문자 " + stackArr[top]);
// top : 최상위에 있는 인덱스를 가리킴
// char ch = stackArr[top];
// top--;
// return ch;
// 한줄로 나타내면 아래와 같음
return stackArr[top--];
// 리턴 먼저 시켜주고 줄여야 하기 때문에 top--
}
}
// 스택의 최상위 데이터 추출
public char peek() {
if(isEmpty()) {
System.out.println("스택이 비어 있습니다");
return 0;
} else {
System.out.println("엿보려는 문자 " + stackArr[top]);
return stackArr[top];
}
}
// 스택 초기화
public void clear() {
if(isEmpty()) {
System.out.println("스택은 비어 있습니다");
} else {
top = -1; // 스택 포인터 초기화
stackArr = new char[this.stackSize]; // 새로운 스택 배열 생성
System.out.println("스택이 초기화 되었습니다");
}
}
// 스택에 저장된 모든 데이터 출력
public void printStack() {
if(isEmpty()) {
System.out.println("스택이 비어 있습니다");
} else {
for (int i = 0; i <= top; i++) {
System.out.print(stackArr[i] + " ");
}
System.out.println();
}
}
}
public class StackTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("스택 사이즈 입력 ");
int stackSize = sc.nextInt();
Stack stack = new Stack(stackSize);
stack.push('A');
stack.printStack();
stack.push('B');
stack.printStack();
stack.push('C');
stack.printStack();
stack.pop();
stack.printStack();
stack.pop();
stack.printStack();
stack.peek();
stack.printStack();
stack.clear();
stack.printStack();
sc.close();
}
}
Java
복사
결과
