Stack에 대해서
Stack이란?
Stack<E> st = new Stack<E>();
후입선출(LIFO:Last In First Out)의 자료구조이다. 즉 가장 나중에 저장된(push)데이터가 가장 먼저 인출(pop)된다. 접근이 목록의 끝(Top 또는 Top Pointer)에서만 일어나기 때문에 Pushdown List 라고도 한다
Stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다.
다음은 스택이 실제로 쓰이는 예이다.
- 운영체제(OS: Operating System) 프로그램에서 사용되는 함수들을 스택 자료형에 저장하여 사용한다.
- 컴파일러(Compiler) 수학 기호들을 기계어로 변환시 사용한다. (연산자 우선 순위 표현을 위한 괄호 검사)
- 자바 가상 머신(JVM: Java Virtual Machine) JVM 내에서 메서드가 실행, 종료될 때 스택 프레임을 이용하여 관리한다.
Stack의 구현
스택의 구현 방법은 배열을 이용하는 것과 연결 리스트를 사용하는 것 두가지가 있다.
1. 배열을 활용해 Stack 구현해보기.
public class ArrayStack implements Stack {
private Object[] stackArray;
private int index; // 현재 인덱스 확인
public static void main(String args[]) {
ArrayStack as = new ArrayStack(10);
as.push("hihi");
as.push(1);
as.push('A');
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
as.push('A');
System.out.println(as.pop());
}
public ArrayStack(int size) {
this.stackArray = new Object[size];
this.index = 0;
}
@Override
public void push(Object data) {
if (index >= stackArray.length) {
throw new IndexOutOfBoundsException("full");
} else {
stackArray[index++] = data;
}
}
@Override
public Object peek() {
if (isEmpty()) {
throw new IndexOutOfBoundsException();
} else {
return stackArray[index - 1];
}
}
@Override
public Object pop() {
if (isEmpty()) {
throw new IndexOutOfBoundsException();
} else {
Object obj = peek();
stackArray[index] = null;
return obj;
}
}
@Override
public boolean isEmpty() {
return (index <= 0);
}
}
배열을 활용할 경우 구현이 쉽고, 원하는 데이터의 접근 속도가 빠르다. 그러나 데이터 삽입과 삭제에 있어 비효율적이다.
2. 링크드리스트를 활용한 Stack 구현해보기.
public class LinkedStack implements Stack {
private Stack topNode;
public static void main(String args[]) {
LinkedStack ls = new LinkedStack();
ls.push("1");
ls.push(1);
ls.push("hiih");
System.out.println(ls.pop());
System.out.println(ls.pop());
System.out.println(ls.pop());
}
public LinkedStack() {
this.topNode = null;
}
@Override
public void push(Object data) {
// 새로운 노드 생성
OdolNode newNode = new OdolNode(data);
// 새로운 노드의 다음노드를 삽입 이전의 top을 참조하도록
newNode.setNextNode(topNode);
// 삽입 이후의 탑은 새로운 노드
topNode = newNode;
}
@Override
public Object pop() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("empty");
} else {
// 탑노드의 데이터
Object data = peek();
// 새로운 탑노드는 현재 탑노드의 nextNode
topNode = topNode.getNextNode();
// 데이터 반환
return data;
}
}
@Override
public Object peek() {
if (isEmpty()) {
throw new IndexOutOfBoundsException();
} else {
return topNode.getData(); // 데이터만 반환
}
}
@Override
public boolean isEmpty() {
return (topNode == null);
}
}
class OdolNode { // 스택에 활용할 노드 클래스
private Object data; // 데이터를 저장
private OdolNode nextNode; // 이전의 노드를 저장하기 위한 노드
public OdolNode(Object data) {
this.data = data;
this.nextNode = null;
}
public Object getData() {
return data;
}
public void setNextNode(OdolNode node) {
nextNode = node;
}
public OdolNode getNextNode() {
return nextNode;
}
}
링크드 리스트를 활용할 경우 데이터의 최대 개수가 한정되어 있지 않고, 데이터 삽입 삭제가 용이하다. 연결리스트 구조는 배열과 다르게 데이터가 순차적으로 나열되어 있지 않다.
Stack Method
Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메소드를 5개만 상속받아 사용한다.
출처
https://freestrokes.tistory.com/82 https://odol87.tistory.com/6