JAVA/HIGH JAVA
[JAVA] Stack, Queue, (홈페이지 뒤로가기 구현), 정렬(Sort)
아잠만_
2024. 4. 22. 12:48
- Stack ==> 후입선출(LIFO)의 자료구조 (최근에 저장된 자료 변경)
- Queue ==> 선입선출(FIFO)의 자료구조 (처음에 저장된 자료 변경)
- Stack과 Queue는 LinkedList를 이용하여 사용할 수 있다.
Stack
- 자료입력
- push(입력값) - 자료출력
- pop()
최근 저장된 자료를 꺼내온 후 꺼내온 자료를 Stack에서 삭제한다
- peek()
최근 저장된 자료를 삭제없이 자료를 꺼내온다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class StackQueueTest {
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
// LinkedList<String> stack2 = new LinkedList<String>();
stack.push("홍길동");
stack.push("일지매");
stack.push("변학도");
stack.push("강감찬");
System.out.println("현재 stack 값 : "+stack); // 현재 stack 값 : [홍길동, 일지매, 변학도, 강감찬]
// 최근에 넣은 값을 꺼내오며 stack에서 삭제
String data = stack.pop();
System.out.println("꺼내온 값 : "+data); // 꺼내온 값 : 강감찬
// 최근에 넣은 값을 꺼내오며 stack에서 삭제
System.out.println("꺼내온 값 : "+stack.pop()); // 꺼내온 값 : 변학도
System.out.println("현재 stack 값 : "+stack); // 현재 stack 값 : [홍길동, 일지매]
stack.push("성춘향");
System.out.println("추가 후 현재 stack 값 : "+stack); // 추가 후 현재 stack 값 : [홍길동, 일지매, 성춘향]
System.out.println("꺼내온 값 : "+stack.pop()); // 꺼내온 값 : 성춘향
System.out.println("현재 stack 값 : "+stack); // 현재 stack 값 : [홍길동, 일지매]
System.out.println("삭제없이 꺼내온 값 : "+stack.peek()); // 삭제없이 꺼내온 값 : 일지매
System.out.println("현재 stack 값 : "+stack); // 현재 stack 값 : [홍길동, 일지매]
System.out.println();
}
}Queue
- 자료입력
- offer(입력값) - 자료출력
- pull()
처음에 저장된 자료를 꺼내오고 꺼내온 자료를 Queue에서 삭제한다
- peek()
처음에 저장된 자료를 꺼내와 삭제없이 자료를 꺼내온다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class StackQueueTest {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.offer("홍길동");
queue.offer("일지매");
queue.offer("변학도");
queue.offer("강감찬");
System.out.println("현재의 queue값 : "+queue); // 현재의 queue값 : [홍길동, 일지매, 변학도, 강감찬]
String temp = queue.poll();
System.out.println("꺼내온 값 : "+temp); // 꺼내온 값 : 홍길동
System.out.println("현재의 queue값 : "+queue); // 현재의 queue값 : [일지매, 변학도, 강감찬]
System.out.println("꺼내온 값 : "+queue.poll()); // 꺼내온 값 : 일지매
System.out.println("현재의 queue값 : "+queue); // 현재의 queue값 : [변학도, 강감찬]
queue.offer("성춘향");
System.out.println("추가 후 현재의 queue값 : "+queue); // 추가 후 현재의 queue값 : [변학도, 강감찬, 성춘향]
System.out.println("꺼내온 값 : "+queue.poll()); // 꺼내온 값 : 변학도
System.out.println("현재의 queue값 : "+queue); // 현재의 queue값 : [강감찬, 성춘향]
System.out.println("삭제없이 꺼내온 값 : "+queue.peek()); // 삭제없이 꺼내온 값 : 강감찬
System.out.println("현재의 queue값 : "+queue); // 현재의 queue값 : [강감찬, 성춘향]
}
}Stack을 이용하여 웹 브라우저의 앞으로 가기, 뒤로가기 기능을 구현하기 Stack이용
import java.util.Stack;
public class StackTest {
public static void main(String[] args) {
Browser b = new Browser();
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => []
// 현재 =>
// forward => []
// -----------------------
b.goURL("1.네이버");
// 1.네이버 사이트에 접속합니다...
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => []
// 현재 => 1.네이버
// forward => []
// -----------------------
b.goURL("2.야후");
// 2.야후 사이트에 접속합니다...
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => [1.네이버]
// 현재 => 2.야후
// forward => []
// -----------------------
b.goURL("3. 구글");
// 3. 구글 사이트에 접속합니다...
b.goURL("4. 다음");
// 4. 다음 사이트에 접속합니다...
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => [1.네이버, 2.야후, 3. 구글]
// 현재 => 4. 다음
// forward => []
// -----------------------
System.out.println("뒤로 가기 후...");
b.goBack();
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => [1.네이버, 2.야후]
// 현재 => 3. 구글
// forward => [4. 다음]
// -----------------------
b.goBack();
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => [1.네이버]
// 현재 => 2.야후
// forward => [4. 다음, 3. 구글]
// -----------------------
b.goForward();
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => [1.네이버, 2.야후]
// 현재 => 3. 구글
// forward => [4. 다음]
// -----------------------
System.out.println("새로운 사이트 접속 후..");
b.goURL("5. 네이트");
// 5. 네이트 사이트에 접속합니다...
b.history();
// ----------------------
// 방 문 기 록
// -----------------------
// back => [1.네이버, 2.야후, 3. 구글]
// 현재 => 5. 네이트
// forward => [4. 다음] // clear할 경우 내용 삭제
// -----------------------
// 원래 사이트는 forward내용이 삭제가 됨
// 그러므로 goURL에 forward.clear()추가
}
}
// 웹브라우저의 앞으로가기, 뒤로가기 기능을 구현하는 예제(Stack이용)
class Browser{
private Stack<String> back;
private Stack<String> forward;
private String currentURL;
public Browser() {
back = new Stack<String>();
forward = new Stack<String>();
currentURL="";
}
// 사이트를 방문하는 메서드 ==> 매개변수에는 방문할 URL이 저장되어 있다.
public void goURL(String url) {
System.out.println(url+" 사이트에 접속합니다...");
if(currentURL!=null && !"".equals(currentURL)) { // 현재페이지가 있으면
back.push(currentURL); // 현재 페이지를 back스택에 추가한다
}
currentURL = url; // 현재 페이지를 변경한다.
forward.clear(); // forward스택의 내용을 모두 지운다.
}
// 뒤로 가기 처리
// isEmpty() ==> 컬렉션에 데이터가 없이 비어 있으면 true, 그렇지 않으면 false
public void goBack() {
if(!back.isEmpty()) { // back스택에 데이터가 있으면...
forward.push(currentURL); // 현재 페이지를 forward에 추가
currentURL = back.pop(); // back스택에서 꺼내온 주소를 현재 페이지로 함.
}
}
// 앞으로 가기 처리
public void goForward() {
if(!forward.isEmpty()) {
back.push(currentURL); // 현재 페이지를 back에 추가
currentURL=forward.pop(); // forward스택에서 꺼내온 주소를 현재페이지로 함.
}
}
// 방문 기록 확인용 메서드
public void history() {
System.out.println("----------------------");
System.out.println(" 방 문 기 록");
System.out.println("-----------------------");
System.out.println("back => "+back);
System.out.println("현재 => "+currentURL);
System.out.println("forward => "+forward);
System.out.println("-----------------------");
System.out.println();
}
}정렬(Sort)
- 정렬과 관련된 interface는 Comparable, Comparator 이렇게 두 가지가 있다.
- Comparable
- Collection에 추가되는 데이터 자체에 정렬 기준을 넣고 싶을 때 구현하는 인터페이스이다.
- compareTo()메서드를 재정의 - Comparator
- 외부에 별도로 정렬 기준을 구현하고 싶을 때 (외부정렬기준) 구현하는 인터페이스 이다.
- compare()메서드를 재정의
> 반환값 : 0 == > 두 값이 같다 (순서를 바꾸지 않음)
> 반환값 : 양수 ==> 앞, 뒤 순서를 바꾼다
> 반환값 : 음수 ==> 앞, 뒤 순서를 바꾸지않음
ex) 오름차순 일 경우 ==> 앞의 값이 뒤의 값보다 [ 크면 양수, 같으면 0, 작으면 음수 ] 반환하도록 구현 - String 클래스, Wrapper클래스, Date클래스, File클래스에는 내부정렬 기준이 이미 구현되어있다.
(구현된 내부 정렬 기준을 모두 오름차순으로 처리되도록 구현되어있다.)
만약 다른 기준으로 정렬하고 싶을 땐 Comparator로 외부정렬 기준을 세워 정렬해야한다.
import java.util.ArrayList;
import java.util.Collections;
public class ListSortTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("일지매");
list.add("홍길동");
list.add("성춘향");
list.add("변학도");
list.add("이순신");
System.out.println("정렬 전 : "+list); // 정렬 전 : [일지매, 홍길동, 성춘향, 변학도, 이순신]
// 정렬은 Collections.sort()메서드를 이용하여 정렬한다.
Collections.sort(list); // Comparable 오름차순
System.out.println("정렬 후 : "+list); // 정렬 후 : [변학도, 성춘향, 이순신, 일지매, 홍길동]
}
}외부 정렬 클래스 작성
String타입을 내림차순으로 정렬할 때,
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class ListSortTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("일지매");
list.add("홍길동");
list.add("성춘향");
list.add("변학도");
list.add("이순신");
System.out.println("정렬 전 : "+list); // 정렬 전 : [일지매, 홍길동, 성춘향, 변학도, 이순신]
Collections.shuffle(list); // 자료 섞기 (실행할 때마다 다름)
System.out.println("자료 섞기 후 : "+list); // 자료 섞기 후 : [성춘향, 이순신, 홍길동, 일지매, 변학도]
// 외부 정렬 기준을 적용해서 정렬하기
Collections.sort(list, new Desc()); // 외부정렬 클래스를 불러옴
System.out.println("정렬 후 : "+list); // 정렬 후 : [홍길동, 일지매, 이순신, 성춘향, 변학도]
}
}
// 정렬 방식을 정해주는 클래스를 만든다. (외부 정렬 기준 클래스라고 한다.)
// ==> Comparator인터페이스를 구현해서 작성한다.
class Desc implements Comparator<String>{ // Comparator 인터페이스를 구현
// compare() 메서드를 이용하여 정렬하고자 하는 기준을 정해준다.
// compare() 메서드의 반환값
// 반환값 0 ==> 두 값이 같다.
// 반환값이 양수 ==> 앞, 뒤의 순서를 바꾼다.
// 반환값이 음수 ==> 앞, 뒤 순서를 바꾸지 않음.
// 예) 오름차순일 경우 ==> 앞의 값이 뒤의 값보다 크면 양수, 같으면 0, 작으면 음수를 반환하도록 구현
@Override
public int compare(String str1, String str2) { // 순서를 바꿀지 말지 정해주는 메서드
// 내림차순으로 구현하려고 한다.
// String은 Comparable로 기본 내부정렬 기준이 구현되어있음.
// 이미 만들어진 정렬기준을 활용하여 재 정렬
if( str1.compareTo(str2) > 0) { // 양수이면
return -1; // 음수이면 어떤 값을 반환해도 상관없음
// 내림차순 형태이므로 순서를 바꾸지 않음
} else if( str1.compareTo(str2) < 0 ) { // 음수이면
return 1;
// 내림차순 형태이므로 순서를 바꿈
} else {
return 0;
}
}
}클래스 생성자에 포함된 값 하나를 기준으로 정렬화 시키기
package kr.or.ddit.basic;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class ListSortTest02 {
public static void main(String[] args) {
ArrayList<Member> memList=new ArrayList<Member>();
memList.add(new Member(1,"홍길동", "010-1111-1111"));
memList.add(new Member(5,"이순신", "010-2222-1111"));
memList.add(new Member(9,"성춘향", "010-3333-1111"));
memList.add(new Member(3,"강감찬", "010-4444-1111"));
memList.add(new Member(6,"일지매", "010-5555-1111"));
memList.add(new Member(2,"변학도", "010-6666-1111"));
System.out.println("정렬전...");
for(Member mem : memList) {
System.out.println(mem); // 추가한 순서대로 출력
}
System.out.println("-----------------------------------------------------");
Collections.sort(memList); // 내부정렬기준이 있을 때는 Comparable를 사용
// Member에 내부정렬기준
System.out.println("정렬후...");
for(Member mem : memList) {
System.out.println(mem);
}
System.out.println("-----------------------------------------------------");
Collections.sort(memList, new SortNumDesc()); // 외부정렬기준 Comparator
System.out.println("정렬후...");
for(Member mem : memList) {
System.out.println(mem);
}
System.out.println("-----------------------------------------------------");
}
}
// Member 클래스의 회원 이름을 기준으로 오름차순 정렬되도록 내부정렬기준을 추가하기
// ==>Comparable인터페이스
// 회원관리용 클래스
class Member implements Comparable<Member>{
private int num;
private String name;
private String tel;
// 생성자 생성
public Member(int num, String name, String tel) {
super();
this.num = num;
this.name = name;
this.tel = tel;
}
// Getter, Setter 생성
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getTel() {
return tel;
}
public void setTel(String tel) {
this.tel = tel;
}
// toString 생성
@Override
public String toString() {
return "Member [num=" + num + ", name=" + name + ", tel=" + tel + "]";
}
@Override
public int compareTo(Member mem) { // 외부에서 들어오는(매개변수) 데이터와 자기자신과 비교
// 오름차순으로 구현
/*
* if(this.getName().compareTo(mem.getName())>0) { return 1;
* } else if(this.getName().compareTo(mem.getName())<0) { return -1;
* } else { return 0;
* }
*/
return this.getName().compareTo(mem.getName());
// 내림차순
// return this.getName().compareTo(mem.getName())*-1;
}
}
// Member클래스의 번호(num)의 내림차순으로 정렬하는 외부 정렬 기준 클래스 > Comparator
// (클래스 명 : SortNumDesc )
class SortNumDesc implements Comparator<Member>{
@Override
public int compare(Member mem1, Member mem2) {
// if(mem1.getNum()>mem2.getNum()) {
// return -1;
// } else if(mem1.getNum()<mem2.getNum()) {
// return 1;
// } else {
// return 0;
// }
// Wrapper 클래스 (Integer)를 이용한 처리방법
return new Integer(mem1.getNum()).compareTo(mem2.getNum())*-1;
// return Integer.compare(mem1.getNum(), mem2.getNum())*-1;
}
}package kr.or.ddit.basic;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* 문제) 학번, 이름, 국어점수, 영어점수, 수학점수, 총점, 등수를 멤버로 갖는 Student클래스를 만든다. Student클래스의
* 생성자에서는 학번, 이름, 국어점수, 영어점수, 수학점수만 매개변수로 받아서 초기화 처리를 한다 (이때 총점의 세과목 점수를 이용해서
* 초기화 한다.)
*
* 이 Student객체는 List에 저장하여 관리한다
*
* List에 저장된 데이터들을 학번의 오름차순으로 정렬할 수 있는 내부정렬기준을 구현하고, 총점의 역순(내림차순)으로 정렬하는데 총점이
* 같으면 이름의 오름차순으로 정렬되는 외부 정렬 기준 클래스를 작성하여 정렬된 결과를 출력하시오 (외부 정렬 기준 클래스명 :
* SortByTotal )
*
* 등수는 List에 전체 데이터가 추가된 후에 구한다.
*
*
*/
public class StudentTest {
public void createRanking(List<Student> list) { // static main에서 불러오기 위해선 인스턴스상태이므로 불가능
for (int i = 0; i < list.size(); i++) {
list.get(i).setRank(1);
for (int j = 0; j < list.size(); j++) {
if (list.get(i).getSum() < list.get(j).getSum()) {
int rank = list.get(i).getRank() + 1;
list.get(i).setRank(rank);
}
}
}
}
public static void main(String[] args) {
StudentTest test = new StudentTest();
List<Student> list = new ArrayList<Student>();
list.add(new Student(1, "가나라", 80, 70, 90));
list.add(new Student(2, "홍길동", 50, 80, 95));
list.add(new Student(3, "일지매", 100, 60, 90));
list.add(new Student(4, "황진이", 85, 80, 85));
list.add(new Student(5, "홍길순", 90, 75, 90));
test.createRanking(list); // static을 붙여주던지 객체를 불러와야함
Collections.shuffle(list);
for (Student st : list) {
System.out.println("섞은 후 :" + st);
}
System.out.println();
Collections.sort(list);
System.out.println("학번 정렬");
for (Student st : list) {
System.out.println("정렬 후 :" + st);
}
System.out.println();
System.out.println("총점 / 이름 정렬");
Collections.sort(list, new SortByTotal());
for (Student st : list) {
System.out.println("정렬 후 :" + st);
}
}
}
class Student implements Comparable<Student> {
private int no;
private String name;
private int kor;
private int eng;
private int math;
private int sum;
private int rank;
public Student(int no, String name, int kor, int eng, int math) {
super();
this.no = no;
this.name = name;
this.kor = kor;
this.eng = eng;
this.math = math;
this.sum = kor + eng + math;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getKor() {
return kor;
}
public void setKor(int kor) {
this.kor = kor;
}
public int getEng() {
return eng;
}
public void setEng(int eng) {
this.eng = eng;
}
public int getMath() {
return math;
}
public void setMath(int math) {
this.math = math;
}
public int getSum() {
return sum;
}
public void setSum(int sum) {
this.sum = sum;
}
public int getRank() {
return rank;
}
public void setRank(int rank) {
this.rank = rank;
}
@Override
public String toString() {
return "Student [no=" + no + ", name=" + name + ", kor=" + kor + ", eng=" + eng + ", math=" + math + ", sum="
+ sum + ", rank=" + rank + "]";
}
@Override
public int compareTo(Student stu) {
return new Integer(this.getNo()).compareTo(stu.getNo());
}
}
class SortByTotal implements Comparator<Student> {
@Override
public int compare(Student stu1, Student stu2) {
// if (stu1.getSum() > stu2.getSum()) {
// return -1;
// } else if (stu1.getSum() < stu2.getSum()) {
// return 1;
// } else if (stu1.getName().compareTo(stu2.getName()) > 0) {
// return 1;
// } else if (stu1.getName().compareTo(stu2.getName()) < 0) {
// return -1;
// } else {
// return 0;
// }
if(stu1.getSum()==stu2.getSum()) {
return stu1.getName().compareTo(stu2.getName());
} else {
return Integer.compare(stu1.getSum(), stu2.getSum())*-1;
}
}
}