stack 스택

stack의 특징

스택에 저장된 자료는 선형 구조를 갖는다.
선형구조란 자료 간의 관계가 1대 1의 관계를 갖는다.
⭐후입선출(LIFO: Last-In-First-Out): 마지막에 삽입한 자료를 가장 먼저 꺼낸다.

stack의 구현

배열을 이용하여 스택을 표현할 수 있다.
스택에서 마지막에 삽입된 원소의 위치를 top이라 부른다.
가장 마지막 원소의 위치를 가리키고 있기 때문에 top을 변수로 선언한다면 초기화는 -1로 한다. 처음 상태는 어떠한 값도 들어있지 않기 때문이다.
top이 -1을 가리키고 있다면, '스택이 비어있다'로 해석한다.

연산

push: 저장소에 자료를 저장한다. <삽입>
pop: 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다. <삭제>
isEmpty: 스택이 공백인지 아닌지 확인하는 연산
peek: 스택의 top에 있는 item(원소)을 반환하는 연산

pop은 실제로 값을 꺼내서 쓰고 날려버리는 느낌이라면, peek은 마지막 item(원소)을 확인(훔쳐만 보는 것)만 하는 것. 단, 둘 다 top이 가리키고 있는 원소를 반환하는 것은 동일하다.

stack의 구현2

push()

top++
arr[top] = 값 저장

arr[++top] = 값

pop()

일단 타겟 값을 지우고(빼내서 사용하고)
top--

💡사실 타겟 값을 일일이 지울 필요는 없다. top--이 되고 이후에 새로운 값을 넣게 되면 덮어씌워져 버리므로 논리적으로 삭제된 것이기 때문이다.

arr[top--]

peek()

맨 위 원소를 확인한다. 값을 삭제하진 않는다.

size()

---

import java.util.Arrays;

public class Stack {

	static int[] stack = new int[3];
	static int top = -1;
	
	public static void main(String[] args) {

		push(3);
		push(5);
		
		// 실험1. pop(), 그리고 push()하기
		pop();
		pop();
		System.out.println(Arrays.toString(stack));
		push(1);
        push(7);
		System.out.println(Arrays.toString(stack));
		
		// 실험2. top에 있는 원소를 삭제와 동시에 사용도 하고자 한다면 변수에 저장해둔다.
		int a = pop();
		System.out.println(a);
		System.out.println(top);
		
		// 실험3. peek()
		push(7);
		int b = peek();
		System.out.println(b);
		
		//실험4. 다시 넣고 출력
		push(8);
		System.out.println(Arrays.toString(stack));
		
        //실험5. 가득 찬 상태에서 push
		push(17);
		push(9);
		System.out.println(Arrays.toString(stack));
		
		//실험6. 공백이면 pop XX
		pop();
		pop();
		pop();
		int c = pop();
		System.out.println(c);
		System.out.println(Arrays.toString(stack));
		
	} //main

	//저장
	static void push(int value) {
		if(!(isFull())) {
			stack[++top] = value;
		}
	}
	
	//삭제
	static int pop() {
		// case1. top의 원소를 지우고 싶다면
		if (!(isEmpty())) {
			int value = stack[top];
			stack[top]=0;
			top--;
			return value;
		}
		return -1020202;
		
		// case2. 논리적 삭제되므로 일일이 지우지 않는다면
		// 마지막 원소를 반환하면서 top을 1 줄여주어야 하므로
		// return arr[top--];
	}
	
	//peek
	static int peek() {
		return stack[top];
	}
    
    //가득 찼는지 확인
	//배열형태(정적)로 만들었기 때문에
	static boolean isFull() {
		return top == stack.length-1 ;
	}
	
	//공백 상태인지 확인
	static boolean isEmpty() {
		return top == -1;
	}
	
} // end class