Deque를 java로 구현해보자.

MJ_Vly·2022년 5월 24일
0

자료구조

목록 보기
2/4

Deque

사진출처 : https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/

Deque란

- 양방향으로 데이터의 삽입 및 삭제가 가능하다.

- front 삽입 : addFirst(), offerFirst()

- rear 삽입 : addLast(), add(), offerLast(), offer();

- front 삭제 : remove(), removeFirst(), poll(), pollFirst()

- rear 삭제 : removeLast(), pollLast()

- front 데이터 가져오기 : getFirst(), peek(), peekFirst()

- rear 데이터 가져오기 : getLast(), peekLast()

* poll의 경우 삭제 후 리턴

* get, peek는 상단의 값을 리턴하는데 get은 덱이 비었으면 예외 발생, peek는 null 반환

이외에도 removeFirstOccurrence(Object o) 등의 메서드들이 존재한다.
removeFirstOccurrence(Object o) 같은 경우 Object o 와 동일한 첫 엘리멘트를 제거한다.

이 중 addFirst(), addLast(), removeFirst(), removeLast(), pollFirst(), pollLast(), peekFirst(), peekLast(), size()를 구현하였으며, 추가로 empty(), full(), printDequr() 등의 메서드도 구현해보았다.

인터페이스 작성

public interface Dequeimpl {
	boolean firstEmpty();
	boolean lastEmpty();
	boolean firstFull();
	boolean lastFull();
	char pollFirst();
	char pollLast();
	char peekFirst();
	char peekLast();
	int size();
	void addFirst(char item);
	void addLast(char item);
	char removeFirst();
	char removeLast();
}

class 작성

//addFirst -> 앞에 추가
//addLast -> 뒤에 추가
//pollFirst 	-> 앞에 값을 리턴하고 해당 값을 지움
//pollLast		-> 뒤에 값을 리턴하고 해당 값을 지움
//removeFirst 	-> 리턴 없이 앞에 값을 지움
//removeLast 	-> 리턴 없이 뒤에 값을 지움
//peekFirst 	-> 앞에 값 리턴
//peekLast 		-> 뒤에 값 리턴
//size			-> 데크의 사이즈를 출력
//printDeque	-> 데크 프린트

public class Deque implements Dequeimpl{
	
	private int dequeSize;
	private int rear;
	private int front;
	private int rearEmpty;
	private int frontEmpty;
	private char[] ArrDeque;
	
	public Deque(int dequeSize) {
		this.dequeSize = dequeSize;
		ArrDeque = new char[this.dequeSize];
		rear = this.dequeSize/2 -1;
		front = this.dequeSize/2 +1;
	}

	@Override
	public boolean firstEmpty() {
		// TODO Auto-generated method stub
		return (front == frontEmpty);
	}

	@Override
	public boolean lastEmpty() {
		// TODO Auto-generated method stub
		return (rear == rearEmpty);
	}

	@Override
	public boolean firstFull() {
		// TODO Auto-generated method stub
		return (front == 0);
	}

	@Override
	public boolean lastFull() {
		// TODO Auto-generated method stub
		return (rear == this.dequeSize-1);
		
	}

	@Override
	public char pollFirst() {
		// TODO Auto-generated method stub
		if(firstEmpty()) {
			System.out.println("first Empty");
			return 0;
		}else {
			System.out.println("poll_first: "+ArrDeque[front]);
			return ArrDeque[front++];
		}
		
	}

	@Override
	public char pollLast() {
		// TODO Auto-generated method stub
		if(lastEmpty()) {
			System.out.println("last Empty");
			return 0;
		}else {
			System.out.println("poll_last: "+ArrDeque[rear]);
			return ArrDeque[rear--];
		}
	}

	@Override
	public char peekFirst() {
		// TODO Auto-generated method stub
		if(firstEmpty()) {
			System.out.println("first Empty");
			return 0;
		}else {
			System.out.println("peek_first: "+ArrDeque[front]);
			return ArrDeque[front];
		}
	}

	@Override
	public char peekLast() {
		// TODO Auto-generated method stub
		if(lastEmpty()) {
			System.out.println("last Empty");
			return 0;
		}else {
			System.out.println("peek_last: "+ArrDeque[rear]);
			return ArrDeque[rear];
		}
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return ((rear-front)+1==-1) ? 0 : (rear-front)+1;
	}

	@Override
	public void addFirst(char item) {
		// TODO Auto-generated method stub
		if(firstFull()) {
			System.out.println("first Full");
		}else {
			//first가 첫 데이터인 경우
			if(rear == (this.dequeSize/2)-1 && front == (this.dequeSize/2)+1 ) {
				rear++;
				rearEmpty = rear;
				frontEmpty = this.dequeSize/2 +1;
				System.out.println("첫데이터는 first");
			}
			ArrDeque[--front] = item;
			System.out.println("first add: "+item);
		}
		
	}

	@Override
	public void addLast(char item) {
		// TODO Auto-generated method stub
		if(lastFull()) {
			System.out.println("last Full");
		}else {
			//last가 첫 데이터인 경우 
			if(rear == (this.dequeSize/2)-1 && front == (this.dequeSize/2)+1 ) {
				front--;
				frontEmpty = front;
				rearEmpty = this.dequeSize/2 -1;
				System.out.println("첫데이터는 last");
			}
			ArrDeque[++rear] = item;
			System.out.println("last add: "+item);
		}
	}

	@Override
	public char removeFirst() {
		// TODO Auto-generated method stub
		if(firstEmpty()) {
			if(lastEmpty()) {
				//front, rear 초기화
				reset();
			}else {
				System.out.println("first Empty");
			}
			return 0;
		}else {
			System.out.println("first remove: "+ArrDeque[front]);
			return ArrDeque[front++];
		}
	}

	@Override
	public char removeLast() {
		// TODO Auto-generated method stub
		if(lastEmpty()) {
			if(firstEmpty()) {
				//front, rear 초기화
				reset();
			}else {
				System.out.println("last Empty");
			}
			return 0;
		}else {
			System.out.println("last remove: "+ ArrDeque[rear]);
			return ArrDeque[rear--];
		}
		
	}
	
	public void printDeque() {
		for(int i=front; i<=rear; i++) {
			System.out.print(ArrDeque[i]+" ");
		}
		System.out.println();
	}
	
	public void reset() {
		rear = this.dequeSize/2 -1;
		front = this.dequeSize/2 +1;
	}
	
	public static void main(String[] args) {
		int dequeSize = 5;
		Deque arrDeque = new Deque(dequeSize);
		
		arrDeque.addLast('R');
		arrDeque.addFirst('A');
		arrDeque.printDeque();
		arrDeque.addLast('B');
		arrDeque.printDeque();
		arrDeque.addFirst('C');
		arrDeque.addFirst('B');
		arrDeque.printDeque();
		arrDeque.addFirst('D');
		arrDeque.addLast('E');
		arrDeque.addLast('T');
		arrDeque.printDeque();
		arrDeque.peekFirst();
		arrDeque.peekLast();
		arrDeque.removeFirst();
		arrDeque.removeLast();
		arrDeque.peekFirst();
		arrDeque.peekLast();
		arrDeque.printDeque();
		
	}
	
}
profile
조금씩 쌓아가는

0개의 댓글