[JAVA] Stack, Queue, (홈페이지 뒤로가기 구현), 정렬(Sort)

• 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;
	}
	
	}

}