Stack & Queue

Stack

Stack 특징

Stack의 특징은 LIFO(Last In First Out)
마지막으로 저장된 데이터가 처음으로 나가는 구조.

Stack 주요 동작

push : Stack에 데이터를 저장한다.
pop : Stack에 있는 Last 데이터를 반환하며, Stack에서 제거한다.
peek : Stack에 있는 Last 데이터를 반환하지만, Stack에서 제거하지 않는다. 즉, Last 데이터를 확인한다.

Stack 사용 사례

stack memory : 함수의 호출과 관계되는 지역변수와 매개변수가 저장된다. 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.

stack frame : stack memory에 저장되는 함수의 호출 정보를 말한다.

Queue

Queue의 특징은 FIFO(First In First Out)
처음으로 Queue에 저장된 데이터가 처음으로 나가는 구조로써 순서를 보장한다.

Queue 주요 동작

enqueue : queue 구조에 데이터를 저장한다.
dequque : queue 구조에 있는 First 데이터를 반환하며, Queue에서 제거한다.
peek : Queue에 있는 First 데이터를 반환하지만, Queue에서 제거하지 않는다. 즉, First 데이터를 확인한다.

기술 문서 Queue

기술 문서에서 Queue는 항상 FIFO를 의미하지 않는다.
CPU의 코어가 1개일때 process1, process2, process3을 실행해야 하는 상황일 경우 process1을 처리중일때 process2와3은 ready queue로써 대기중인 상태이다.
ready queue가 일반적인 queue로 구현되어있는 경우에는 순서대로 프로세스가 실행되지만, ready queue가 우선순위 큐로 구현되어있으면, 우선순위에 따라 프로세스가 CPU에 의해 실행된다.

priority queue(우선순위 큐)

Stack & Queue Error

StackOverflowError

StackOverflowError는 스택 메모리 공간을 다 사용했을 경우 발생한다.
에러 대부분이 재귀함수(recursive function)에서 탈출을 하지 못해 발생한다. 즉, 계속해서 참조가 일어나기 때문이다.

// 재귀함수의 대표적인 피보나치 수열
public int fibo(int n){
	if(n<=1) return n;
    if(n>1) return (fibo(n-1)+fibo(n-2));
}

해결방법 : 탈출조건 (break point)을 작성하지 않거나, 잘못 작성한경우 발생하기 때문에 탈출조건을 제대로 작성해야한다.

OutOfMemoryError

OutOfMemoryError는 JAVA에서 Heap 메모리를 다 썼을때 발생한다.

• Heap메모리 : 사용자에 의한 동적할당 메모리 영역으로써, JAVA에서 객체가 거주하는 메모리영역이다.

주요 원인은 Queue에 데이터가 계속 쌓이면 발생한다.
해결방법 : Queue의 사이즈, 크기를 고정한다.

Queue크기를 고정 한 후 Queue에 데이터가 다 찼을 경우
1.예외(exception)던지기 : Queue에 데이터를 추가할 경우 예외를 발생
2.특별한 값 반환 : Queue에 데이터를 추가할 경우 null 또는 false반환
3.성공할 때까지 영원히 스레드 블락 : Queue에 공간이 생길 때까지 블락(대기)상태에 놓인다.
4.제한된 시간만 블락되고 그래도 안되면 포기 : 블락상태에서 제한 시간동안 Queue에 공간이 생기지 않을 경우 포기한다.

LinkedBlockingQueue

LinkedBlockingQueue는 Java Class로써 Queue의 OutOfMemoryError 발생시 다양한 방법으로 Error를 처리한다.
.add(e) : 예외 발생
.offer(e) : 특별한 값 리턴
.put(e) : 블락상태로 대기
.offer(e,time,unit) : 블락 타임아웃 시간을 설정하여 블락상태로 대기

public class Main {
	public static void main(String[] args) {
		Queue<String> que = new LinkedBlockingQueue<>();
		que.offer("첫번째");
		que.offer("두번째");
		que.offer("세번째");
		
		System.out.println(que.poll());
		System.out.println(que.poll());
		System.out.println(que.poll());
	}
}
// 출력결과 : 
// 첫번째
// 두번째
// 세번째

출처 : 쉬운코드 유튜브
출처 : dev.to