[자료구조] Stack과 Queue-1

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

스택

한 쪽 끝에서만 item을 삭제하거나 새로운 item을 저장하는 자료구조

후입선출(LIFO) 원칙하에 삽입과 삭제 수행

push : 새 item을 저장하는 연산
pop : top item을 삭제하는 연산

배열로 구현한 ArrayStack 클래스

ArrayStack 클래스

public class ArrayStack<E> {
 private E s[];
 private int top;
 public ArrayStack(){
     s = (E[]) new Object[1];
     top = -1;
 }
 public int size() { return top+1; }
 public boolean isEmpty() { return (top == -1); }
 ...
}

이외 메소드

peek (stack의 top항목 내용 리턴)

public E peek() {
 if(isEmpty()){
   throw new EmptyStackException();
 }
 return s[top];
}

push (새 item을 저장하는 연산)

public void push(E newItem) {
  if(size() == s.length) {
      resize(2*s.length);
  }
  s[++top] = newItem;
}

pop (top item을 삭제하는 연산)

public E pop() {
  if(isEmpty()){
      throw new EmptyStackException();
  }
  E item = s[top];
  s[top--] = null;
  if(size()>0 && size()==s.length/4) {
      resize(s.length/2);
  }
  return item;
}

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/YXty0up-RH0

IM

스택

배열로 구현한 ArrayStack 클래스