[Java] 자료 구조 - Stack, Queue

JUNBEOM PARK·2022년 2월 23일

🧨 Java

목록 보기

29/33

🤔 Stack ?

자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'이다.
상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조이다.
Stack의 가장 큰 특징은 나중에 들어간 것이 먼저나오는 (Last In First Out)의 형태이다.

Stack의 특징

먼저 들어간 자료가 나중에 나오는 LIFO(Last In First Out) 구조
시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
그래프의 깊이 우선 탐색(DFS)에서 사용
재귀적(Recursion) 함수를 호출 할 때 사용

Stack 선언

Stack<Integer> stack = new Stack<>(); //int형 스택 선언

Java에서 stack을 선언 하려면 java.util.Stack을 import 한 뒤,
Stack<element> stack = new Stack<>();과 같은 형식으로 선언 한다.

Stack 값 추가

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

Stack에 값을 추가하고 싶다면 push() 메소드를 활용하면 된다.

위 와 같이 데이터가 쌓이게 된다.

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의 전체 값 제거 (초기화)

Stack에서 값을 제거 하고 싶다면 pop() 메소드를 사용 하면 된다.

위 와 같이 데이터가 제거 된다.
Stack의 값을 모두 제거 하고 싶으면 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의 가장 상단의 값 출력

Stack의 가장 위에 잇는 값을 출력하고 싶으면 peak() 메소드를 사용 하면 된다.

위 와 같이 가장 마지막에 들어간 값이 출력 된다.

Stack의 기타 메소드

stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

Stack의 크기를 구하는 size() 메소드
Stack이 비어있는지 확인 하는 empty() 메소드
Stack의 값을 검색하는 contains() 메소드 등이 있다.

😃 Queue ?

Queue는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미 한다.
이처럼 줄을 지어 순서대로 처리 되는 것이 Queue라는 자료 구조 이다.
Queue는 데이터를 일시적으로 쌓아두기 위한 자료 구조로 Stack 과는 다르게
FIFO(First In First Out)의 형태를 가진다.
FIFO형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다.

Queue의 특징

먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 구조
큐는 한 쪽 끝은 프론트(front)로 정하여 삭제 연산만 수행
다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행
그래프의 넓이 우선 탐색(BFS)에서 사용

Queue 선언


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

Java에서 Queue는 LinkedList를 활용하여 생성 해야 한다.

그렇기에 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() 또는 offer()라는 메소드를 활용하면 된다.
add() 메소드의 경우 만약 삽입에 성공하면 true를 반환한다.

위 와 같이 데이터가 쌓이게 된다.

Queue 값 삭제


queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

Queue에서 값을 제거하고 싶다면 poll() 이나 remove() 메소드를 사용 하면 된다.
poll() 메소드는 큐가 비어 있으면 null을 반환한다.

pop() 메소드를 사용하면 위 그림과 같이 제거 된다.
clear() 메소드를 사용하면 모든 요소가 제거 된다.

Queue 에서 가장 먼저 들어간 값 출력

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.peek();       // queue의 첫번째 값 참조