[java] Stack 구현

자료구조/알고리즘 책을 펴면 가장 먼저 나오는 녀석 되시겠다.

그만큼 기본 중의 기본!

똑똑한 아저씨 아줌마들이 많은 언어들의 (자바, c++, 파이썬 기타등등!)

라이브러리(STL) 에 친절하게 이미 만들어두어서, 가져다 쓰기만 하면 되므로

직접 구현할 일은 절대 거의 없지만 

당신이 기업/대회 코딩 테스트를 준비한다면, 즉석에서 만들 수 있을 정도는 되어야 한다. 

----------------------------------------------------------------------

기

[개념]

스택은 First In Last Out (줄여서 FILO, 후입선출) 

먼저 들어온 데이터가 가장 나중에 빠져나오는 자료구조이다.

쓰레기통을 생각하면 된다. 스택은 쓰레기통의 코드화 그 자체라고 할 수 있다.

그렇다. 스택 == 쓰레기통.

스택 개념 끝! (정말이다. 쉽다!)

-----------------------------------------------------------------------

승

[구현]

스택을 구현하기 위해서는 아래의 (변수/배열) 3개가 반드시 필요하다.

1. int top;   // 쓰레기통 뚜껑에 해당하는 부분

3. int size;  // 쓰레기통의 크기를 지정하는 부분

2. Object[] stackSize;   // 쓰레기통 배열(몸체), Object 타입이므로 숫자, 문자 기타등등 다 들어갈 수 있다.

데이터가 들어오고 나가는 부분이 top 에서 일어나므로, 출입하는 데이터를 제어하기 위한 top 변수는 반드시 필요하다!

size 변수는 스택이 비어있는지, 가득찼는지 등을 파악하기 위해 필요하다!

stackSIze 배열은 정해진 size대로, 또 데이터가 담길 방들을 마련하는데 사용되므로 필요하다!

변수 세개도 만들어주고, Stack class 를 new 키워드를 사용해 호출할 수 있도록 생성자도 만들어준다.

그러면 아래와 같이 코드를 작성했을 때 Stack 배열이 만들어진다.

 

배열 10크기만큼의 Stack 생성 성공.

이제 '스택'을 만든것이다 !

⭑ size 변수 없이도 스택 호출생성할 수 있는데. 왜 반드시 필요하다고 하심?

A. 아래 부분에서 만들 각종 메소드를 처리하기 위해서 필요합니다.

    "아무런 기능도 없는" 스택을 만들거라면 사실 size 변수는 필요하지 않습니다.

    하지만 그렇다면 stack 자료구조를 만드는 이유도 없겠죠.  그래서 반드시 필요합니다.

------------------------------------------------

전

쓰레기통은 만들었고... 

그럼 이제 해야할 일은 무엇?

스택에 데이터를 넣는 행위(메소드)를 만들어야 한다.

1. 데이터를 넣는 행위(push)

2. 데이터를 빼는 행위(pop)

3. 가장 최근에 넣은 (가장 위에 있는) 데이터 확인하기(peek)

4. 스택이 비어있는지 검사(empty)

5. 스택이 가득찼는지 검사(full)

그 외에 자신이 생각하는 여러가지 기능을 만들면 된다.

아래 코드는 위에서 말한 다섯 가지 기능을 하는 메소드들이다.

        public boolean full() {   // 스택이 가득찼는가?
		return (size == top+1);
	}
	
	public void push(int data) { //스택에 데이터 넣기 
		// if (스택이 가득 찬 것이 true이면 에러 발생)
		if(full()) throw new ArrayIndexOutOfBoundsException();
		stackSize[++top] = data;
	}
	
	public boolean empty() { //스택이 비어있는지 보기 
		return (top == -1);
	}

	public Object peek() { // 스택에 가장 최근에 넣은 데이터 확인 
		return stackSize[top];
	}
	
	public Object pop() { //스택에서 가장 최근에 넣은 데이터 빼기 
		// if (스택이 비어있는 것이 true이면 에러 발생)
		if (empty()) throw new ArrayIndexOutOfBoundsException();
		return stackSize[--top+1];
	}

결




이게 끝이다. (ㄹㅇ루다가)

첨에 스택을 공부할때는 개념 파악은 쉬웠는데,

코드로 옮기려고 하니 막막하더라.

그래서 걍 통째로 외워버렸고 틈틈히 잊어버렸다 싶을때쯤

하니 어느샌가 아니? 왜 이걸 몰랐지 싶다.

당신도 그렇게 될 수 있다. 왜냐하면 빠가인 나도 했거든.. 화이팅이다.

아래는 코드 전체.

class Stack {
        private int top;
	private int size;
	private Object[] stackSize;
        
        public Stack(int size) { // 스택 생성자. 
		this.top = -1;
		this.size = size;
		this.stackSize = new Object[size];
	}
	
	public boolean full() {   // 스택이 가득찼는가?
		return (size == top+1);
	}
	
	public void push(int data) { //스택에 데이터 넣기 
		// if (스택이 가득 찬 것이 true이면 에러 발생)
		if(full()) throw new ArrayIndexOutOfBoundsException();
		stackSize[++top] = data;
	}
	
	public boolean empty() { //스택이 비어있는지 보기 
		return (top == -1);
	}

	public Object peek() { // 스택에 가장 최근에 넣은 데이터 확인 
		return stackSize[top];
	}
	
	public Object pop() { //스택에서 가장 최근에 넣은 데이터 빼기 
		// if (스택이 비어있는 것이 true이면 에러 발생)
		if (empty()) throw new ArrayIndexOutOfBoundsException();
		return stackSize[--top+1];
	}