[자료구조] 스택(Stack)과 Java로 구현

스택(Stack)

LIFO(Last In First Out) 특성을 가진 자료구조

메모리에 들어오는 데이터 위치가 메모리 말단(Top Pointer)이고

쓰기 위해 내보내는 데이터 역시 메모리 말단을 거친다

 

스택의 추상자료형(Abstract Data Type; ADT)

- 입력연산 : 푸시(Push)

- 출력연산 : 팝(Pop)

- 조회연산 : 피크(Peek)

※ 조회연산은 탑 포인터가 가리키는 데이터를 조회만 할 뿐 탑의 순번(인덱스)은 변화시키지 않는다

 

스택의 Push, Pop 과정

1. Push

- 먼저 Top Pointer의 값을 증가 시킨 후, 증가시킨 Top의 위치에 데이터를 넣는다

2. Pop

- 먼저 데이터를 꺼낼 Top의 위치를 다른 변수(인덱스)에 별도로 저장한 후, Top의 위치를 감소시킨다

- 저장해 놓은 인덱스 위치의 값을 Pop 한다

 

Java로 구현 (ArrayList 이용)

import java.util.ArrayList;

public class stackRealization {
	public static void main(String[] args){
		Stack<Integer> stack = new Stack<Integer>();	//Integer 타입으로 생성
		
		int size = 0;
		
		System.out.println("----push----");
		for(int i=0; i<5; i++) {
			int num=i;
			stack.push(num);
			System.out.println(num);
		}
		
		System.out.println("----peek----");
		System.out.println(stack.peek());
		
		System.out.println("----search----");
		System.out.println(stack.search(3));
		
		size = stack.size();	//나머지 pop하기 위해 사이즈 구함
		System.out.println("----pop----");
		for(int i=0; i<size; i++) {
			System.out.println(stack.pop());
		}
		
		System.out.println("----isEmpty----");	//Empty면 끝
		if(stack.empty())
			System.out.println("clear!");
	}
}


class Stack<E> {
	ArrayList<E> stack = new ArrayList<E>();
	private int top = -1;
	
	void push(E element) {
		stack.add(++top, element);
	}
	
	E pop() {
		int idx = top;
		top--;
		return stack.remove(idx);
	}
	
	E peek() {
		return stack.get(top);
	}
	
	boolean empty() {
		if(stack.size()==0)
			return true;
		return false;
	}
	
	int search(E element) {
		if(stack.contains(element))		//해당 요소가 있는지 확인
			return top-stack.indexOf(element)+1;	//리턴해야 하는 인덱스는 top부터 1번임
		return -1;		//없으면 -1 리턴
	}
	
	int size() {
		return stack.size();
	}
}

- 배열의 크기를 조절할 수 있는 ArrayList를 이용하여 구현

- 제네릭 컬렉션 클래스로 만들었고 Integer 형태로 구현하여 실행하였음

 

참고로 그림은 내가 직접 PPT를 이용하여 그려보았다!!

※ 글의 내용은 명품 Java Programming 책과 나무위키를 참고하여 작성하였습니다