[알고리즘] Stack 개념 + java.util.Stack

 

 

 

 스택 (Stack) 

개념

스택이란?
: Last In First Out 의 특징을 가지고 있는 선형적 자료구조

마치 접시를 쌓아둔 듯한 자료구조입니다.

제일 밑에 있는 접시를 빼면 위의 있는 접시들이 흔들려 깨질 수가 있습니다.

따라서, 접시를 빼낼 때는 위부터 꺼내야합니다.

이와 같은 데이터 저장 구조를 가진 것을 바로 스택 이라고 합니다.

 

특징

스택은 후입선출(LIFO: Last In First Out) 의 특징을 가지고 있으며, 프로그래밍 언어에서 메서드 콜을 할 때 사용되어 집니다.

이를 Functional Call 이라고 합니다.

메서드를 호출할 때 스택을 사용하여 너무 많은 메서드가 쌓이다보면 스택 오버 플로우(overflow) 가 발생합니다.

스택은 배열이나 연결리스트를 이용하여 구현될 수 있습니다.

 

 

 

 Java Stack API - Stack 클래스 사용 

java 스택 api 를 사용하는 방법을 알아보도록 하겠습니다.

다음과 같은 메서드가 존재합니다.

empty: 스택이 비었는지 아닌지
peek: 스택의 top 확인
pop: 스택에서 top 요소 빼기
push: 스택에 넣기
search: 해당 요소가 스택에서 몇 번째에 있는지 반환

Vector 클래스를 extends 하고 있기 때문에 add, clear 와 같은 메서드를 사용할 수 있습니다.

 

push

package day220804.practice;


import java.util.Stack;


public class StackTest {
	static Stack<Integer> stack = new Stack<>();


	public static void main(String[] args) throws Exception {
		// 삽입
		stack.push(2);
		stack.push(1);
		stack.push(3);

		System.out.println(stack);
	}
}

2, 1, 3 의 순으로 stack 에 집어넣었습니다.

삽입 연산을 할 때는 push() 메서드를 사용할 수 있습니다.

 

pop

package day220804.practice;


import java.util.Stack;


public class StackTest {
	static Stack<Integer> stack = new Stack<>();


	public static void main(String[] args) throws Exception {
		// 삽입
		stack.push(2);
		stack.push(1);
		stack.push(3);

		System.out.println("삽입 후: " + stack);

		// 삭제
		stack.pop();

		System.out.println("삭제 후: " + stack);
	}
}

pop() 메서드를 사용하면 삭제 연산을 할 수 있습니다.

삭제 연산이 수행되면 제일 위에 있는 것이 삭제가 됩니다.

 

peek

package day220804.practice;


import java.util.Stack;


public class StackTest {
	static Stack<Integer> stack = new Stack<>();


	public static void main(String[] args) throws Exception {
		// 삽입
		stack.push(2);
		stack.push(1);
		stack.push(3);

		System.out.println("삽입 후: " + stack);

		// top 요소 확인
		System.out.println("top 요소 확인: " + stack.peek());
	}
}

peek() 메서드를 사용하면 제일 위에 있는 top 요소가 무엇인지 확인할 수 있습니다.

top 요소를 리턴합니다.

 

empty

package day220804.practice;


import java.util.Stack;


public class StackTest {
	static Stack<Integer> stack = new Stack<>();


	public static void main(String[] args) throws Exception {
		// 삽입
		stack.push(2);
		stack.push(1);
		stack.push(3);

		System.out.println("삽입 후: " + stack);

		// 스택 비었는지 확인
		System.out.println("비었는지 확인: " + stack.empty());
		System.out.println("비었는지 확인: " + stack.isEmpty());

		// 모두 삭제 
		stack.clear();

		// 모두 삭제 후 스택 비었는지 확인
		System.out.println("비었는지 확인: " + stack.empty());
		System.out.println("비었는지 확인: " + stack.isEmpty());

	}
}

empty() 메서드를 이용해서 스택이 비었는지 아닌지 불린 값으로 리턴하여 확인할 수 있습니다.

true 면 빈 것이고, false 라면 빈 것이 아닙니다.

vector 의 isEmpty() 메서드를 이용할 수도 있습니다.

clear() 메서드를 이용하면 스택을 모두 비울 수 있습니다.

 

search

package day220804.practice;


import java.util.Stack;


public class StackTest {
	static Stack<Integer> stack = new Stack<>();


	public static void main(String[] args) throws Exception {
		// 삽입
		stack.push(2);
		stack.push(1);
		stack.push(3);

		System.out.println("삽입 후: " + stack);

		// 요소 찾기
		System.out.println("1의 위치: " + stack.search(1));
		System.out.println("2의 위치: " + stack.search(2));
		System.out.println("3의 위치: " + stack.search(3));
	}
}

 

 

 

 Java Stack API - Deque 클래스 사용 

java api document 를 가보면 더 나은 LIFO 스택 연산을 하고 싶다면 아래와 같이 Deque 클래스를 사용하라고 합니다.

Deque<Integer> stack = new ArrayDeque<>();

Deque 클래스를 이용하게 되면 덱 연산까지 사용할 수 있습니다.

Deque 은 마치 두 개의 Queue 를 붙여놓은 것 같은 형태로 양쪽에서 요소를 넣고 뺄 수 있습니다.

하지만 조심해야할 점이 있습니다.

바로 Deque 클래스에서 add() 는 addLast() 이기 때문에 stack 에서 사용할 때는 push() 를 사용해야 합니다.

remove() 와 pop() 도 마찬가지 입니다.

 

 

 

 

 

 

 

 

# java stack # 알고리즘 자바

---