Stack / Queue

Stack

 

⭐️Stack의 특징

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 
3. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
4. 그래프의 깊이 우선 탐색(DFS)에서 사용
5. 재귀적(Recursion) 함수를 호출 할 때 사용

 

⭐️ Stack의 사용법

import java.util.Stack; //import
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
Stack<String> stack = new Stack<>(); //char형 스택 선언

 

⭐️ Stack값 추가

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가

 

Stack에 값을 추가하고 싶다면 push(value)라는 메소드를 활용하면 됩니다. 

 

⭐️ Stack값 삭제

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.pop();       // stack에 값 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

 

스택에서 값을 제거하고싶다면 pop()이라는 메서드를 사용하면 됩니다. pop을 하면 가장 위쪽에 있는 원소의 값이 제거됩니다. 스택의 값을 모두 제거하고싶다면 clear()라는 메서드를 사용하면 됩니다.

 

⭐️Stack의 가장 상단의 값 출력

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.peek();     // stack의 가장 상단의 값 출력

 

스택의 가장 위에 있는 값을 출력하고 싶다면 peek()라는 함수를 사용하면 됩니다. 아래 그림과 같이 가장 마지막에 들어간 값이 출력됩니다.

 

⭐️Stack의 기타 메서드

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

 

그 밖에도 stack에는 크기를 구하는 size()메서드와 stack이 비어있는지 확인하는 empty() 메서드(비어있다면 true, 그렇지 않다면 false를 return) stack의 값을 search하는 contains(int value)함수가 있습니다.

---

Queue

⭐️ Queue의 특징

1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 
2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함
3. 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함  

4. 그래프의 넓이 우선 탐색(BFS)에서 사용
5. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴

 

⭐️ Queue의 사용법

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

 

자바에서 Queue는 LinkedList를 활용하여 생성해야 합니다. 그렇기에 Queue와 LinkedList가 다 import되어 있어야 사용이 가능합니다. Queue<Element> queue = new LinkedList<>()와 같이 선언해주면 됩니다.

 

⭐️ Queue 값 추가

Queue<Integer> stack = new LinkedList<>(); //int형 queue 선언
queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가

 

자바에서 queue에 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 됩니다.

add(value) 메소드의 경우 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킵니다. queue에 값을 계속해서 추가해나간다면 아래 그림과 같은 형태로 데이터가 쌓이게 됩니다.

offer(value)의 경우 add(value)와 해당 큐 맨 뒤에 값 삽입 / 값 추가 성공 시 true반환 이라는 점은 동일하지만 큐에 여유 공간이 없어 삽입에 실패하면 false를 반환한다는 점이 차이점이다.

⭐️ Queue 값 삭제

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.poll();       // queue에 첫번째 값(맨 앞)을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값(맨 앞) 제거
queue.clear();      // queue 초기화

 

queue에서 값을 제거하고싶다면 poll()이나 remove()라는 메서드를 사용하면 됩니다.

poll()함수는 큐가 비어있으면 null을 반환합니다.

remove()을 하면 가장 앞쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다. queue의 모든 요소를 제거하려면 clear()메서드를 사용합니다.

⭐️ Queue 맨 앞의 값 확인

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가

queue.peek();       // queue의 첫번째 값 참조
queue.element();        // queue의 첫번째 값 참조

 

큐의 맨 앞에 있는 값(첫 번째로 저장된 값)을 알고 싶다면 peek( ) 이나 element( )를 사용하면 됩니다.

큐가 비어 있어 확인이 불가할 경우, peek( )의 경우 null을 반환하고, element( )의 경우 NoSuchElementException이 발생합니다.

 

🧐

Queue에서 데이터를 추가, 삭제, 검색할 때 제공되는 메서드들의 차이는 문제 상황에서

에러를 발생시키느냐(add, remove, element) 아니면

null 혹은 false를 반환(offer, poll, peek) 하는가입니다.

 

 

 

참고

https://coding-factory.tistory.com/601

https://coding-factory.tistory.com/602