March
31st,
2021
Stack이란?
FILO(First In Last Out)을 적용한 자료구조. 언제나 목록의 끝에서 데이터를 추가/삭제한다. 쉽게 말해 한쪽이 막힌 통이라고 생각하면 된다.
자바에서는 Vector클래스를 상속하였으며, 이는 곧 동기화가 가능하다는 말이다!
주요 메소드
- push : 스택에 데이터를 추가한다.
- pop : 스택의 가장 마지막 데이터를 삭제한다.
- peek : 가장 마지막 데이터를 반환한다.
- search : 가장 마지막 index로부터 얼마나 떨어져있는지 offset을 반환한다.
- empty : 해당 스택이 비었는지 판단, true/false를 반환한다.
주요 사용처
- 브라우저 뒤로가기
- 실행 취소
- 역순 문자열 만들기
- 수식의 괄호 검사
- 후위표기법 계산
- DFS(깊이우선탐색)
스택 구현 코드
1) LinkedList로 스택 구현
TBD
2) 배열로 구현
인터페이스 :
package datastructure.stack;
public interface StaackInterface<T> {
/**
* 스택의 맨 위에 요소를 추가합니다.
*
* @param item 스택에 추가할 요소
* @return 스택에 추가된 요소
*/
T push(T item);
/**
* 스택의 맨 위에 있는 요소를 제거하고 제거 된 요소를 반환합니다.
*
* @return 제거 된 요소
*/
T pop();
/**
* 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다.
*
* @return 스택의 맨 위에 있는 요소
*/
T peek();
/**
* 스택의 상반 부터 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
* 중복되는 원소가 있을경우 가장 위에 있는 요소의 위치가 반환됩니다.
*
* @param value 스택에서 위치를 찾을 요소
* @return 스택의 상단부터 처음으로 요소와 일치하는 위치를 반환.
* 만약 일치하는 요소가 없을 경우 -1 을 반환
*/
/*
* ________
* | a |
* idx 3 |______| search("w")
* | e | --> 상단(idx 3)으로 부터 3번 째에 위치
* idx 2 |______| == return 되는 값 : 3
* | w |
* idx 1 |______|
* | k |
* idx 0 |______|
*
*/
int search(Object value);
/**
* 스택의 요소 개수를 반환합니다.
*
* @return 스택에 있는 요소 개수를 반환
*/
int size();
/**
* 스택에 있는 모든 요소를 삭제합니다.
*/
void clear();
/**
* 스택에 요소가 비어있는지를 반환합니다.
*
* @return 스택에 요소가 없을 경우 {@code true}, 그 외의 경우 {@code false}를 반환
*/
boolean empty();
}
package datastructure.stack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.EmptyStackException;
import java.util.Stack;
public class MyStack<T> implements StaackInterface<T> {
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 용적 크기
private static final Object[] EMPTY_ARRAY = {}; // 빈 배열
private Object[] array; // 요소를 담을 배열
private int size; // 요소 개수
public MyStack() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
public MyStack(int capacity){
this.array = new Object[capacity];
this.size = capacity;
}
private void resize(){
if(array.length == 0){
this.array = new Object[DEFAULT_CAPACITY];
this.size = DEFAULT_CAPACITY;
return;
}
if(size == array.length){
int newCapacity = array.length * 2;
array = Arrays.copyOf(array, newCapacity);
return;
}
if(size < array.length / 2){
int newCapacity = array.length / 2;
array = Arrays.copyOf(array,newCapacity);
return;
}
}
public int getSize() {
return size;
}
@Override
public T push(T data){
if(size == array.length){
resize();
}
array[size] = data;
size++;
return data;
}
@Override
public T pop(){
if(size == 0){
throw new EmptyStackException();
}
T data =(T) array[size-1];
size--;
resize();
return data;
}
@Override
public T peek(){
if(size == 0){
throw new EmptyStackException();
}
T data = (T) array[size-1];
return data;
}
@Override
public int search(Object value) {
int i=0;
for( Object obj : array){
if(obj.equals(value))
return size - i;
i++;
}
return -1;
}
@Override
public int size() {
return this.size;
}
@Override
public void clear() {
array = EMPTY_ARRAY;
size = 0;
resize();
}
@Override
public boolean empty() {
return size == 0;
}
}
3) ArrayList로 구현
package datastructure.stack;
import java.util.ArrayList;
import java.util.EmptyStackException;
public class MyStackwithArrList<T> extends ArrayList<T> implements StaackInterface<T>{
public MyStackwithArrList() {
super();
}
public MyStackwithArrList(int capacity) {
super(capacity);
}
@Override
public T push(T item) {
add(size()-1,item);
return item;
}
@Override
public T pop() {
int length = size();
T data = remove(length-1);
return data;
}
@Override
public T peek() {
int length = size();
if(length == 0) throw new EmptyStackException();
return get(length-1);
}
@Override
public int search(Object value) {
int lastIndex = lastIndexOf(value);
if(lastIndex >= 0) return size() - lastIndex -1;
return -1;
}
@Override
public void clear() {
clear();
}
@Override
public boolean empty() {
return size() == 0;
}
}
