[JAVA] 스택(Stack)과 큐(Queue)

[JAVA] 매서드

---

스택 ( Stack )

• 스택은 사전에 "쌓다", "쌓이다" 라는 뜻을 가진 용어로, 말 그대로 계속 쌓아올린 듯한 모양을 가진 자료구조이다.
• 스택은 가장 나중에 들어온 데이터가 가장 먼저 빠져나가는 후입선출(LIFO : Last In First Out) 구조

---

스택의 특징

• 후입선출 (LIFO : Last In First Out) 구조 : 먼저 들어온 데이터가 나중에 빠져나가는 구조
• 단방향 입출력 구조 : 데이터의 들어오는 방향과 나가는 방향이 같다.
• 데이터를 하나씩만 넣고 뺀다.
• 깊이 우선 탐색(DFS)에 이용된다
• 재귀 함수의 동작 흐름과 같은 구조를 가진다.

---

스택 코드 작성 순서

• PUSH
  1. 배열의 크기를 +1 하여 증가시킨다.
  2. 배열의 요소를 1번에 옮겨 담는다. 
  3. 마지막에 추가 
  4. 원본 배열을 새로운 배열로 변경

static void push(int data) {

	int[] temp = new int[arr.length+1];
		
	for(int i=0; i<arr.length; i++) {
			
		temp[i] = arr[i];		
	}
		
	temp[temp.length-1] = data;
		
	arr = temp;
	temp = null;	
}

• POP
  1. 삭제할 값부터 백업
  2. 원본 배열의 크기 -1 인 배열을 생성
  3. 값을 옮겨담는다.
  4. 사본 배열을 원본 배열로 변경
  5. 1번을 리턴

static int pop() {
	if(arr.length>0) {
		
        int del = arr[arr.length-1];	
		int[] temp = new int[arr.length-1];
			
		for(int i=0; i<temp.length; i++) {
			temp[i] = arr[i];
		}
		arr = temp;
		temp = null;
			
		return del;
	}
	return 0;
}

---

스택 전체 소스코드

import java.util.Arrays;

public class m05 {

	public static void main(String[] args) {
		
		push(10);
		push(20);
		push(30);
		
		System.out.println(Arrays.toString(arr));	
		System.out.println(pop());
		System.out.println(Arrays.toString(arr));
		
	}
	
	//end main
	static int[] arr = {1,2,3,4,5};
	
	// 추가
	static void push(int data) {
		
		int[] temp = new int[arr.length+1];
		
		for(int i=0; i<arr.length; i++) {
			
			temp[i] = arr[i];		
		}
		
		temp[temp.length-1] = data;
		
		arr = temp;
		temp = null;	
	}
	
	// 제거
	static int pop() {

		if(arr.length>0) {
			int del = arr[arr.length-1];
			
			int[] temp = new int[arr.length-1];
			
			for(int i=0; i<temp.length; i++) {
				temp[i] = arr[i];
			}
			arr = temp;
			temp = null;
			
			return del;
		}
		return 0;
	}
}

---

큐 ( Queue )

• Queue의 사전적 의미는 '무엇을 기다리는 사람', '차량 등의 줄 혹은 줄을 서서 기다리는 것'을 의미한다.
• 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트
• 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다.
•  

---

큐의 특징

• 데이터의 순서가 중요한 작업에 적합하다.
• 큐의 크기가 고정되어 있으면 데이터가 가득 차면 더 이상 삽입이 불가능하다.
• 큐의 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행
• 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행
• 그래프의 넓이 우선 탐색(BFS)에 사용
• 컴퓨터 버퍼에서 주로 사용

---

큐의 동작 원리

• PUSH ( = 스택과 push 과정 동일 )
  1. 배열의 크기를 +1 하여 증가시킨다.
  2. 배열의 요소를 1번에 옮겨 담는다. 
  3. 마지막에 추가 
  4. 원본 배열을 새로운 배열로 변경

static void push(int data) {
		
	int[] temp = new int[arr.length+1];
		
	for(int i=0; i<arr.length; i++) {
			
		temp[i] = arr[i];		
	}
		
	temp[temp.length-1] = data;
	arr = temp;
	temp = null;
}

• POP 
  1. 삭제할 요소를 백업한다.
  2. 복사 배열을 하나 생성한다.
  3. 원본의 첫 번째 배열부터 마지막 배열까지 담는다.
  4. 원본 배열을 새로운 배열로 변경

static int pop() {
		
    int del = arr[0];
		
	int[] temp = new int[arr.length-1];
		
	for(int i=0; i<temp.length; i++) {
		temp[i] = arr[i+1];
	}
        
	arr = temp;
	temp = null;
		
	return del;
}

• 전체 소스코드

import java.util.Arrays;

public class Queue {

	public static void main(String[] args) {

		push(10);
		push(20);
		push(30);
		push(40);
		push(50);
		System.out.println(Arrays.toString(arr));
		
		System.out.println(pop());
		System.out.println(Arrays.toString(arr));
	}
	
	static int[] arr = {};
	
	static void push(int data) {

		int[] temp = new int[arr.length+1];
		
		for(int i=0; i<arr.length; i++) {
			
			temp[i] = arr[i];		
		}
		
		temp[temp.length-1] = data;
		

		arr = temp;
		temp = null;
	}
	
	//삭제
	static int pop() {

		int del = arr[0];
		
		int[] temp = new int[arr.length-1];
		
		for(int i=0; i<temp.length; i++) {
			temp[i] = arr[i+1];
		}
		
		arr = temp;
		temp = null;
		
		return del;
	}

}