8/24 - 자료구조

package 스택;

public class LinkListStackMain {

	public static void main(String[] args) {
		
		LinkedListStack lls = new LinkedListStack();
		
		lls.push(3);
		lls.push(4);
		lls.push(6);
		
		System.out.println(lls.pop());
		System.out.println(lls.peek());
		System.out.println(lls.isEmpty());
	}

}

1.스택
- 배열 (연속된 공간에 저장 - 인덱스)
(크기 지정, 지정된 크기 이상으로 커질수가 없음)

package 스택;

//배열활용 스택만들기
public class ArrayStack {
	//필드(private), 메서드(생성자,get(가지고오기), set(수정하기))
	
	//필드 : 배열, 스택 용량(최대 요소 개수), 포인터(top)
	private int[] stk; // 스택용 배열
	private int capacity; // 스택 용량
	private int ptr; // 스택 포인터(top) - 다음 요소 들어올 수 있는 인덱스 
	
	//예외(Runtime(실행) 시 오류 발생)
	//런타임 오류 -> 코드에는 문제가 없음 -> 예외처리 필수
	//1. try~catch
	//2. throws
	//int num = "sdf";
	//컴파일오류 -> 컴파일 자체가 안됨(코드에 문제)
	//스택이 비어있음 -> pop() -> 예외처리
	
	//Nested ClaSS(class 안에 class 작성)
	public class EmptyStackException extends RuntimeException{
		public EmptyStackException() {
			System.out.println("스택이 비어있습니다!");
		}
	}
	
	//스택이 가득차있음 -> push() ->예외처리
	public class OverflowStackException extends RuntimeException{
		public OverflowStackException() {
			System.out.println("스택이 가득 차있습니다!");
		}
	}
	
	//생성자(Stack생성)
	public ArrayStack(int max) {//ArrayStack 생성시 사용자가 크기 지정할 수 있도록
		stk = new int[max]; //사용자가 지정한 크기만큼 연속된 공간 할당
		capacity = max; // 최대허용용량 = 사용자가 지정한 크기 
		ptr = 0; // 최초로 들어오는 요소는 0번 인덱스 
	}
	
	//요소삽입(push(int n)) 삽입된 요소 반환(리턴)
	public int push(int n) {
		if(ptr>=capacity) {
			//(isFull()) 같은 으미
			throw new OverflowStackException();
		}else {
			stk[ptr] = n; //스택에 요소 넣기!
			ptr++; // 포인터 1증가
			return stk[ptr-1]; // 포인터 1증가 되었기 때문에 -1 해줘야 함! 
		}		
	}
	//요소 삭제(pop()) , 삭제된 요소 반환(린턴)
	public int pop() {
		if(ptr<=0) {
			throw new EmptyStackException();
		}else {
			//포인터 1감소(top 위치가 1감소)
			ptr--;
			return stk[ptr];
		}
	}
	//꼭대기 요소 확인
	public int peek() {
		//스택이 비어있으면 예외처리
			if(ptr<=0) {
				//ptr<= == isEmpty 같은의미다
				throw new EmptyStackException();
			}else {
				//비어있지 않으면 top(꼭대기요소) 리턴
				return stk[ptr-1];
			}
		}
	
	//스택이 비어있는지
	//비어있으면 true 비어있지 않으면 false
	public boolean isEmpty() {
		return ptr<=0;
		}
	
	//스택이 가득차있는지
	//가득차있는지 true 차있지 않으면 false
	public boolean isFull() {
		return ptr>=capacity;
	}
	
	}

package 스택;

public class ArrayStackMain {

	public static void main(String[] args) {
		
		// 스택생성
		ArrayStack as = new ArrayStack(5);
		
		as.push(3);
		as.push(2);
		as.push(4);
		as.push(5);
		as.push(6);

		System.out.println(as.pop());
		System.out.println(as.peek());
		System.out.println(as.isEmpty());
		System.out.println(as.isFull());
	}

}

노드

package 스택;

public class Node {
	//데이터
	private int data;
	// 다음 노드의 주소
	private Node nextNode;
	
	public Node(int n) {
		data = n;
		nextNode = null; //다음 노드 주소는 아직모름
	}
	
	//노드의 데이터를 가지고 오기
	public int getData() {
		return data;
	}
	
	//해당 노드와 연결되어있는 노드(주소, 참조값) 가지고 오기
	public Node getNextNode() {
		return nextNode;
	}
	
	//현재 생성된 노드가 이전에 top노드의 주소값을 가지고 있도록 (연결)
	public void linkNode(Node top) { //top : 현재 탑노드의 주소(참조값)
		nextNode = top;		
	}

}

2. 링크드리스트
(연속된 공간에 저장 x -> 주소값)

package 스택;

public class LinkedListStack {
	private Node top; //현재 top 노드의 주소값
	
	public LinkedListStack() {
		top = null;
	}
	//스택이 비어있을 경우 예외처리
	public class EmptyStackException extends RuntimeException{
		public EmptyStackException() {
			System.out.println("스택이 비어있습니다!");
		}
	}
	
	//요소 삽입, 삽입된 요소의 데이터 반환
	public int push(int n) {
		Node newNode = new Node(n); // 노드 생성 데이터부분 초기화
		newNode.linkNode(top); // 현재 top인 노드의 주소값을 새로 생성된
		                       // 노드의 주소부에 저장(연결)
		top = newNode; // 새로 생성된 노드가 top이 되도록 수정
		
		return newNode.getData();
	}
	
	//요소 삭제, 삭제된 요소의 데이터 반환 
	//스택이 비어있으면 예외처리
	public int pop() {
		if(top==null) {
			throw new EmptyStackException();
		}else {
			int data = top.getData();
			
			//top 위치 바꾸기
			//top필드가 현재top의 이전에 있는 노드의 주소값
			top = top.getNextNode();
			//top이 가지고 있는 주소데이터(top과 연결된 노드의 주소) -> top 할당
			//-> top 위치 바뀜
			return data; //top 바뀌기 전에 top 노드의 데이터
		}
	}
	//꼭대기 노드 데이터 가지고오기
	public int peek() {
		return top.getData();
	}
	//스택이 비어있는지
	//비어있으면 true 비어있지 않으면 false
	public boolean isEmpty() {
		return top == null;
	}

}

 

<과제>

큐로 배열만들기

package 큐;

public class ArrayQueue {
	private int[] que; //큐용 배열
	private int capacity; //큐의 용량(최대 요소 개수)
	private int frontPtr; //front(맨 앞 요소 가리키는 포인터)
	private int rearPtr; //rear(맨 뒤 요소 가리키는 포인터)
	private int num; //큐 현재 데이터 개수
	
	// 큐가 비어있을 때 -> 값을 삭제 하지 못함
		public class EmptyQueueException extends RuntimeException{ 
			public EmptyQueueException() {
				System.out.println("큐가 비어있습니다");
			}
		}
		// 큐가 가득차있을 때 -> 값을 더이상 삽입 하지 못합
		public class OverflowQueueException extends RuntimeException{
			public OverflowQueueException() {
				System.out.println("큐가 가득 차있습니다");
			}
		}
		
		///생성자
		public ArrayQueue(int max) {// max - 배열의 크기
			que = new int[max]; 
			capacity = max; 
			frontPtr = 0; 
			rearPtr = 0; 
			num = 0; 
		}
		
		//요소 삽입
		public int enque(int n) { //n 큐에 넣을 요소(정수)
			if(num>=capacity) {
				//==isFull로 쓸수 있다
				throw new OverflowQueueException();
			}else {
				que[rearPtr] = n; //배열에 요소 삽입
				rearPtr++; //다음 요소가 들어올 인덱스 번호 지정
				num++; // 현재 요소 개수 1증가
				if(rearPtr==capacity) {//rearPtr 가 배열에 인덱스 범위를 벗어나게 되면
					rearPtr =0;        //무조건 0법 인덱스를 가리키게 함
				}
				return n;
			}
		}

//요소 삭제
public int deque() {
	if(num<=0) {//큐에 데이터가 없을때(비어있음)
		//==isEmpty로 쓸수 있다
		throw new EmptyQueueException();
	}else {
		int n = que[frontPtr]; //삭제될 데이터의 값 저장
		frontPtr++; //front 포인터 1증가(1번 인덱스 삭제 -> front가 2번 인덱스)
		num--; //현재 요소개수 1감소
		
		if(frontPtr==capacity) { //frontPtr가 배열의 인덱스 범위를 벗어나면
			frontPtr =0;//frontPtr를0으로 바꿔줌
		}
		return n; //삭제 된 데이터 리턴
	}
}

	//맨 앞 데이터 리턴
	public int peek() {
		if(num<=0){
			//==isEmpty로 쓸수 있다
			throw new EmptyQueueException();
		}else {
			return que[frontPtr];
		}
	}
	
	//큐가 비어있는지
	public boolean isEmpty() {
		return num<=0;
	}
	
	//큐가 가득차있는지
	public boolean isFull() {
		return num>=capacity;
	}

}

package 큐;

public class ArrayQueueMain {

	public static void main(String[] args) {
		
		ArrayQueue aq = new ArrayQueue(5);
		
		aq.enque(1);
		aq.enque(2);
		aq.enque(3);
		aq.enque(4);
		aq.enque(5);
		
		System.out.println(aq.deque());
		System.out.println(aq.deque());
		System.out.println(aq.deque());
		
		System.out.println(aq.peek());
	}

}

- 링크드 리스트 배열만들기

package 큐;

public class Node {
	private int data; // 실제 데이터 저장
	private Node nextNode; // 연결된 노드(다음에 추가될 노드의 주소)
	//int i;
	//Node(변수타입) nextNode(변수명);
	
	//생성자 (Node라는 변수타입을 만드는 작업)
	public Node(int data) {
		this.data = data;
		this.nextNode = null; //노드만 생성했을 경우네는 큐에 연결된 상태가 아님!
	}
	
	//this 노드가 rear 일때 새로운 노드가 연결이 될때 그 노드의 주소값을 저장
	public void linkNode(Node next) {
		this.nextNode = next;
	}
	//i=2;
	//nextNode (변수 명) = 값(주소 값);
	//주소값 ex) I@ajsdisj123124
	
	
	//this 노드의 데이터 가지고 오기
	public int getData() {
		return data;
	}
	
	//this 노드에 저장된 next노드의 주소값 가지고오기
	public Node getNextNode() {
		return nextNode;
	}
	
	
}

package 큐;

public class LinkedListQueue {
	private Node front; //front 노드 주소
	private Node rear; //rear 노드 줏
	private int num; //큐 요소 개수
	
	//생성자
	public LinkedListQueue() {
		front = null;
		rear = null;
		num = 0;
	}
	
	// 큐가 비어있을 경우 예외처리
	public class EmptyQueueException extends RuntimeException{
		public EmptyQueueException() {
			System.out.println("큐가 비어있습니다");
		}
	}
	
	//요소 삽입
	public int enque(int n) {
		//데이터를 저장하고 있는 노드 생성
		Node newNode = new Node(n); //enque 호출시 작성한 값으로 데이터부 초기화
		
		//노드가 없을 때 (큐가 비어있을 때)
		//head=null, rear = null
		//노드 1개 삽입 -> 1개 삭제(head 삭제)
		//첫번째 노드 삽입 -> head =
		
		//큐가 비어있을 경우 -> 노드 - front 
		if(isEmpty()) {
		   //==isEmpty
			front = newNode;

		}else { //큐의 마지막 노드가 다음 노드(새노드) 주소값을 가지게
			rear.linkNode(newNode); //새로운 노드의 주소값이 rear 노드의 주소부에 저장(연결)
		}
		rear = newNode; //새로운 노드가 rear가 되도록 변경
		num++; //요소개수 1증가
		
		return newNode.getData();
	}
	
	//요소 삭제
	public int deque() {
		if(isEmpty()) { //큐가 비어있을 경우
		   //==isEmpty	
			throw new EmptyQueueException();
		}else {
			int n = front.getData(); //현재 삭제될 노드의 데이터 저장
			Node nextNode = front.getNextNode(); //다음에 front가 될 노드의 주소 (참조값)을 저장
			
			front = nextNode; //front 노드가 바뀜
			num--; //큐 요소 개수 1감소
			
			return n;
		}
	}
	
	//맨 앞 요소 리턴
	public int peek() {
		return front.getData();
	}
	
	//큐가 비어있는지
	public boolean isEmpty() {
		return num<=0;
	}

}

package 큐;

public class LinkedListQueueMain {

	public static void main(String[] args) {
		
		LinkedListQueue llq = new LinkedListQueue();
		
		llq.enque(1);
		llq.enque(2);
		llq.enque(3);
		llq.enque(4);
		llq.enque(5);
		llq.enque(6);
		
		System.out.println(llq.deque());
		System.out.println(llq.deque());
		System.out.println(llq.deque());
		
		System.out.println(llq.peek());

	}

}

<오후수업>

상속이란?

상속: 뒤를 잇다, 이어받다, 물려받다

ex) 네 발 자전거를 만들고 싶다.

 

[ 마우스 만들기]

package Ex01;

public class Mouse {
	
	// Mouse만이 가질수 있는 기능 설계하기
	public void leftClick() {
		System.out.println("좌클릭~~");
	}
	
	public void rightClick() {
		System.out.println("우클릭~~");
	}

}

package Ex01;

public class MouseMain {

	public static void main(String[] args) {
		
		// Mouse 설계도를 통하여 mouse 객체 생성하기
		Mouse mouse = new Mouse();
		
		mouse.leftClick();
		mouse.rightClick();
		
		System.out.println();
		
		//WheelMouse 객체 생성
		WheelMouse wm = new WheelMouse();
		
		wm.leftClick();
		wm.rightClick();
		wm.wheel();
		
		System.out.println();
		
		//smartMouse 객체 생성
		SmartMouse sm = new SmartMouse();
		sm.leftClick();
		sm.rightClick();
		sm.wheel();
		sm.smart();
	}

}

package Ex01;

public class SmartMouse extends WheelMouse{
	
	//좌 클릭	
	//우 클릭
	//휠 기능	
	// +) SmartMouse만이 가질수 있는 기능
	// 피로를 감소시키는 기능 ->smart()
	
	public void smart() {
		System.out.println("피로가 감소되는 기능~~");
	}
	
	// 물려받기 하였으나 나만의 기능으로 사용할 수 있는 기능 만들기
	// -> 재정의 의미! (메소드 오버라이딩)
	// -> 상속의 받는 관계에서 메소드에 대하여 재정의를 하는것! 
	public void leftClick() {
		System.out.println("더블 좌클릭~~");
	}
	
	public void rightClick() {
		System.out.println("더블 우클릭~~");
	}

	
	

}

package Ex01;

public class WheelMouse extends Mouse {
	
	//공통되는 기능은 이미 만들어져있는 클래스로 부터 물려받기!
	// 상속의 키워드! extends
	
//	//왼쪽 클릭 기능
//	public void leftClick() {
//		System.out.println("좌 클릭~~");
//	}
//	//오른쪽 클릭 기능
//	public void rightClick() {
//		System.out.println("우 클릭~~");
//	}
	
	//휠 사용 기능
	public void wheel() {
		System.out.println("휠 사용하기~~~");
	}
	

}

 

java의 상속 : 기존 클래스의 변수(데이터)와 메소드(로직, 코드)를 물려받아 새로운 클래스를 구성하는 것.

 

기존 클래스: 부모 클래스, 수퍼 클래스

                                        ↑    재사용+추가기능

새로운 클래스: 자식 클래스 , 서브 클래스

 

 

상속의 필요성

상속을 사용해서 얻는 장점

- 기존 클래스의 변수와 코드를 재사용 ->코드의 중복 감소, 클래스 간결화

- 먼저 작성된 검증된 프로그램을 재사용 -> 신뢰성 있는 프로그램 손쉽게 개발

- 클래스간 계층적 분류 및 관리 -> 유지보수 용이

 

상속 문법의 이해

class 마우스

클릭하기 메소드

우클릭하기 메소드

↑

 

자바 상속의 특징1. 다중상속을 지원하지 않는다.

 

다중상속: 하나의 수퍼 클래스만 가질 수 있음

 

자바 상속의 특징2. 상속의 횟수에 제한을 두지 않는다.

 

자바 상속의 특징3. object라고 하는 최상위 클래스에서 만나게 된다 / 모든 클래스는 java.lang.object를 상속받는다.

 

[상속 확인하기]

class 프린터 -> 부모/슈퍼 클래스

 

캐스팅(Casting)

 

 

추상화: 클래스간의 공통점을 찾아내서 공통의 조상을 만드는 작업, 상속 계층도를 따라 올라갈수록 클래스의 추상화는 더욱 심화된다., 뼈대만 남는다,

 

구체화: 상속을 통해 클래스를 구현, 확장하는 작업

 

- 추상 메소드 

   - 선언되어 있으나 구현되어 있지 않은 메소드

   - 추상 메소드 선언 abstract 키워드로 선언 

   - ex)public abstract int getValue();

 

-  추상 메소드는 서브 클래스에서 오버라이딩하여 구현

 

[추상 클래스]

  - 추상 메소드를 하나라도 가진 클래스

     - 클래스 앞에 반드시 abstract라고 선언해야 함

  - 추상 메소드가 하나도 없지만 클래스 앞에 abstract로 선언한 경우

 

[추상 클래스 특성]

- 추상 클래스의 객체는 생성할 수 없다.

- 추상 클래스 필요성

   - 상속관계에서 서브클래스가 반드시 구현 해야 함을 알릴 때 (강제성)

   - 설계와 구현 분리

     * 슈퍼 클래스에서는 개념적 특징 정의

     * 서브 클래스에서 구체적 행위 구현

package Ex02;

public abstract class Charac {
	
	//일반 클래스 -> 설계가 완성되어 있는 완성 설계도
	// 추상화 -> 완성되지 않은 뼈대만 제공하는 기능
	
	//추상 메소드는 완성되지 않은 기능의 메소드 이므로 
	// 완성 되지 않은 설계도에 포함되어야 한다! -> 클래스도 추상화가 되어야 한다
	
	
	// 기본 캐릭터로 간단한 기능을 가질 수 있도록 설계
	// run(): 앞으로 전진
	public void run() {
		System.out.println("앞으로 전진");
	}
	
	//추상화 작업을 위한 키워드! -> abstract
	
	
	//jump(): 위로 점프
	public abstract void jump(); 
		//System.out.println("위로 점프");

	
	//attack() : 주먹 휘두르기
	public abstract void attack(); 
		//System.out.println("주먹 휘두르기");
	

	

}

package Ex02;

public class Warrior extends Charac{
	
	// 추상 클래스를 상속받는 클래스는
	// 해당 추상 메소드에 대하여 구체적인 구현이 이뤄져야 한다!(강제성)
	
	//기본 캐릭터를 물려받은 전사 캘릭터
	// 공격시 : 칼 휘두르기
	// 점프시 : 이단 점프하기
	
	public void attack() {
		System.out.println("칼 휘두르기!!");
	}
	
	public void jump() {
		System.out.println("이단 점프하기");
	}
	
	
}

package Ex02;

public class Wizard extends Charac{

	//기본 캐릭터의 기능을 물려받은 마법사 캐릭터
	// 공격시 "마술봉 휘두르기~~"
	// 점프시 "포털 이동!!"
	
	public void attack() {
		System.out.println("마술봉 휘두르기~~");
	}
	public void jump() {
		System.out.println("포털 이동!!");
	}
	
}

package Ex02;

public class CharcMain {

	public static void main(String[] args) {
		
		//추상적으로 만들어진 클래스는 
		//미완성되어 있는 클래스로 명확하게 객체 생성을 할 수 없다!
		//-> 추상 클래스는 new 키워드를 사용할 수 없다!
		
		//Charac ch = new Charac();
		
//		ch.jump();
//		ch.attack();
//		ch.run();
		
		System.out.println();
		
		Wizard ch2 = new Wizard();
		ch2.attack();
		ch2.jump();
		ch2.run();

		System.out.println();
		
		
		Warrior ch3 = new Warrior();
		ch3.run();
		ch2.attack();
		ch2.jump();

	}

}

package Ex03;

public class RegularEmployee {
	
	private String empno;
	private String name;
	private int pay;
	private int bonus;
	
	public RegularEmployee(String empno, String name, int pay, int bonus) {
		
		this.empno = empno;
		this.name = name;
		this.pay = pay;
		this.bonus = bonus;
	}
	
	public int getMondeyPay() {
		return (pay+bonus)/12;
	}
	
	public String print() {
		return empno + " : "+name+" : "+pay;
	}
		
	}

package Ex03;

public class RegularEmployeeMain {

	public static void main(String[] args) {
	 //객체를 생성하는 키워드 -> new
	 // new -> 키워드 사용과 동시에 생성자 메소드를 호출할 수 있는 기능!
	 RegularEmployee regular=new RegularEmployee("SMHRD001","홍길동",4000,400);
	 System.out.println(regular.print());
	 System.out.println(regular.getMondeyPay()+"만원");

	 TempEmployee temp = new TempEmployee("SMHRD002","채수민",3000,300);
	 System.out.println(temp.print());
	 System.out.println(temp.getMondeyPay()+"만원");


	}

}

package Ex03;

public class TempEmployee {
	
	String empno;
	String name;
	int pay;
	public TempEmployee(String empno, String name, int pay) {
		//super(); -> 상속의 의미에서 부모가 되는 클래스를 지칭하는 키워드
		this.empno = empno;
		this.name = name;
		this.pay = pay;
	}
	
	
	public String getEmpno() {
		return empno;
	}
	public void setEmpno(String empno) {
		this.empno = empno;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getPay() {
		return pay;
	}
	public void setPay(int pay) {
		this.pay = pay;
	}
	
	

}