1. Stack
import java.util.Stack
Stack<(type)> (name) = new Stack<>();
여기서 (type)은 reference type으로 스택 안에 들어갈 원소의 타입
import java.util.Stack;
public class Main {
public static void main(String[] args){
Stack<Integer> s = new Stack<>();
}
}
2. stack 핵심 메소드
2-1) push(E)
맨 위에 데이터 E를 추가
2-2) size()
stack에 들어있는 데이터 수를 반환
2-3) isEmpty()
stack이 비어있다면 true, 아니라면 false를 반환
2-4) peek()
stack의 가장 위에 있는 데이터를 반환
2-5) pop()
stack의 가장 위에 있는 데이터를 반환하며 동시에 그 데이터를 stack에서 제거한다.
import java.util.Stack;
public class Main {
public static void main(String[] args){
//정수를 관리할 stack을 선언(빈 스택)
Stack<Integer> s = new Stack<>();
s.push(2);
s.push(5);
s.push(9);
//가장 나중에 들어온 원소 출력(9)
System.out.println(s.peek());
//가장 나중에 들어온 원소 제거
s.pop();
//원소의 개수 출력
System.out.println(s.size());
while(!s.isEmpty()){
//가장 나중에 들어간 원소부터 순서대로 출력
System.out.println(s.pop());
}
}
}
3. 연습문제1
- push A: 정수 A를 스택에 넣는 연산입니다. 새로 들어온 정수는 상단부터 차례대로 스택에 쌓입니다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력합니다.
- size: 스택에 들어있는 정수의 개수를 출력합니다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력합니다.
- top: 스택의 가장 위에 있는 정수를 출력합니다.
import java.util.Stack;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Stack<Integer> stack = new Stack<>();
for(int i = 0; i< n; i++){
String q = sc.next();
if(q.equals("push")){
int A = sc.nextInt();
stack.push(A);
} else if(q.equals("pop")){
System.out.println(stack.pop());
} else if(q.equals("size")){
System.out.println(stack.size());
} else if(q.equals("empty")){
if(stack.isEmpty() == true){
System.out.println(1);
} else {
System.out.println(0);
}
} else {
System.out.println(stack.peek());
}
}
}
}
4. 큐
import java.util.Queue;
import java.util.LinkedList;
Queue<(type)> name = new LinkedList<>();의 형태 선언
type은 reference type이고 큐에 들어갈 원소의 타입
import java.util.Queue;
import java.util.LinkedList;
public class Main{
public static void main(String[] args){
Queue<Integer> q = new LinkedList<>();
}
}
5. 큐 핵심 메소드
5-1) add(E)
맨 뒤에 데이터 E를 추가
5-2) size()
현재 큐에 들어있는 데이터의 수를 반환
5-3) isEmpty()
현재 큐가 비어있다면 true, 아니라면 false를 반환
5-4) peek()
큐의 맨 앞에 있는 데이터를 반환
5-5) poll()
큐의 맨 앞에 있는 데이터를 반환하고 동시에 그 데이터를 큐에서 뺀다.
peek는 제거하지 않은데 poll은 제거함
import java.util.Queue;
import java.util.LinkedList;
public class Main {
public static void main(String[] args){
//정수를 관리할 queue를 선언합니다(빈 큐)
Queue<Integer> q = new LinkedList<>();
q.add(3);
q.add(5);
q.add(9);
//가장 앞에 있는 원소 3을 출력
System.out.println(q.peek());
//가장 앞에 있는 3을 제거
q.poll();
//원소의 개수 2개 출력
System.out.println(q.size());
//가장 앞에 있는 원소부터 순서대로 5,9 출력
while(!q.isEmpty()){
System.out.println(q.poll());
}
}
}
6. 연습문제2
- push A: 정수 A를 큐에 넣는 연산입니다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력합니다.
- size: 큐에 들어있는 정수의 개수를 출력합니다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력합니다.
- front : 큐의 가장 앞에 있는 정수를 출력합니다.
import java.util.Queue;
import java.util.Scanner;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < n; i++){
String q = sc.next();
if(q.equals("push")){
int A = sc.nextInt();
queue.add(A);
} else if(q.equals("pop")){
System.out.println(queue.poll());
} else if(q.equals("size")){
System.out.println(queue.size());
} else if(q.equals("empty")){
if(queue.isEmpty() == true){
System.out.println(1);
} else {
System.out.println(0);
}
} else {
System.out.println(queue.peek());
}
}
}
}
7. Deque
자바에서 Deque를 사용하기 위해..
import java.util.Deque;
import java.util.ArrayDeque;
Deque<(type)> (name) = new ArrayDeque<>(); 형태의 선언이 필요하다.
import java.util.Deque;
import java.util.ArrayDeque;
public class Main{
public static void main(String[] args){
Deque<Integer> dq = new ArrayDeque<>();
}
}
8. deque 핵심 메소드
8-1) addFirst(E)
맨 앞에 데이터 E를 추가한다
8-2) addLast(E)
맨 뒤에 데이터 E를 추가한다
8-3) pollFirst()
맨 앞에 있는 데이터를 반환하고 deque에서 제거한다
8-4) pollLast()
맨 뒤에 있는 데이터를 반환하고 deque에서 제거한다.
8-5) size()
현재 deque에 들어있는 데이터의 수를 반환한다
8-6) isEmpty()
현재 deque가 비어있다면 true, 아니라면 false를 반환한다
8-7) peekFirst()
deque의 맨 앞에 있는 데이터를 반환
8-8) peekLast()
deque의 맨 뒤에 있는 데이터를 반환
import java.util.Deque;
import java.util.ArrayDeque;
public class Main {
public static void main(String[] args){
//정수를 관리할 deque를 선언
Deque<Integer> dq = new ArrayDeque<>();
//맨 앞에 3,5를 순서대로 추가
//[5,3]으로 들어있음
dq.addFirst(3);
dq.addFirst(5);
//맨 앞에 적혀있는 숫자 5가 출력
System.out.println(dq.peekFirst());
//맨 뒤에 9를 추가
//[5,3,9]
dq.addLast(9);
//맨 뒤에 적혀있는 숫자인 9가 출력
System.out.println(dq.peekLast());
//맨 앞 숫자(5)를 제거한다.
//[3,9]
dq.pollFirst();
//맨 앞에 적힌 숫자 3을 출력
System.out.println(dq.peekFirst());
//원소의 개수 2를 출력
System.out.println(dq.size());
}
}
9. 연습문제3
- push_front A: 정수 A를 덱의 앞에 넣습니다.
- push_back A: 정수 A를 덱의 뒤에 넣습니다.
- pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력합니다.
- pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력합니다.
- size: 덱에 들어있는 정수의 개수를 출력합니다.
- empty: 덱이 비어있으면 1을, 아니면 0을 출력합니다.
- front: 덱의 가장 앞에 있는 정수를 출력합니다.
- back: 덱의 가장 뒤에 있는 정수를 출력합니다.
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Deque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < n; i++){
String q = sc.next();
if(q.equals("push_front")){
int A = sc.nextInt();
deque.addFirst(A);
} else if(q.equals("push_back")){
int A = sc.nextInt();
deque.addLast(A);
} else if(q.equals("pop_front")){
System.out.println(deque.pollFirst());
} else if(q.equals("pop_back")){
System.out.println(deque.pollLast());
} else if(q.equals("size")){
System.out.println(deque.size());
} else if(q.equals("empty")){
if(deque.isEmpty() == true){
System.out.println(1);
} else {
System.out.println(0);
}
} else if(q.equals("front")){
System.out.println(deque.peekFirst());
} else {
System.out.println(deque.peekLast());
}
}
}
}
10. 연습문제4
1부터 N까지의 정수가 오름차순으로 정렬되어있습니다. 이 수열을 정수가 하나만 남을때까지 다음과 같은 동작을 반복하는 프로그램을 작성해봅시다.
- 맨 앞의 정수를 제거합니다.
- 그 후 남은 수열의 맨 앞의 정수를 맨 뒤로 이동시킵니다.
시키는대로 구현하면 된다
1부터 N까지를 모두 deque에 넣고, 앞의 정수를 pollFirst()로 제거한 다음, 다시 앞의 정수를 pollFirst()로 빼서,
이를 k에 저장해서, k를 다시 맨 뒤로 넣는, addLast()를 수행
dq.size() != 1이 아닌 동안 계속 반복하도록 while문을 이용해 반복 수행
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Deque<Integer> dq = new ArrayDeque<>();
for(int i = 1; i < n+1; i++){
dq.addLast(i);
}
while(dq.size() != 1){
dq.pollFirst();
int k = dq.pollFirst();
dq.addLast(k);
}
System.out.println(dq.peekFirst());
}
}728x90
'알고리즘 > Java 기초' 카테고리의 다른 글
| 자바 자료구조5 -우선순위 큐 사용법- (0) | 2023.03.04 |
|---|---|
| 자바 자료구조4 -HashMap과 HashSet- (0) | 2023.03.04 |
| 자바 초보부터 B형까지9 -class 생성하기 필수- (0) | 2023.03.01 |
| 자바 초보부터 B형까지8 -2차원 배열 필수- (0) | 2023.03.01 |
| 자바 초보부터 B형까지7 -변수의 범위, 지역변수, 전역변수 설정방법- (0) | 2023.03.01 |