본문 바로가기

java

Deque(Double-ended Queue)

데큐는 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서 스택의 설질과 큐의  성질 모두 가지고 있는 자료조




 - 덱의 insertFront() 연산과 deleteFront()연산은 front를 스택에 top으로 생각했을 때 스택의 push()연산과, pop()연산과 같다.

 - 덱의 insertRear() 연산과deleteRear()연산은 rear를 스택에 top으로 각했을때 스택의 push()연산과, pop()연산과 같다.

 - 덱의 insertRear()연산과 deleteFront()연산은 일반 큐의 enQueue()연산, deQueue()연산과 같다.


연산 수행에 대한 덱의 상태




public class DQNode {
char data;
DQNode rlink;
DQNode llink;
}
public class DQueue {
DQNode front;
DQNode rear;

public DQueue() {
front = null;
rear = null;
}

public boolean isEmpty() {
return (front == null);
}

public void insertFront(char item) {
DQNode newNode = new DQNode();
newNode.data = item;

if (isEmpty()) {
front = newNode;
rear = newNode;
newNode.rlink = null;
newNode.llink = null;
} else {
front.llink = newNode;
newNode.rlink = front;
newNode.llink = null;
front = newNode;
}
System.out.println("Front Inster Item " + item);
}

public void insertRear(char item) {
DQNode newNode = new DQNode();
newNode.data = item;

if (isEmpty()) {
front = newNode;
rear = newNode;
newNode.rlink = null;
newNode.llink = null;
} else {
rear.rlink = newNode;
newNode.rlink = null;
newNode.llink = rear;
rear = newNode;
}

System.out.println("Rear Insert Item" + item);
}

public char deleteFornt() {
if (isEmpty()) {
System.out.println("Front Removing Fail!! DQueue is empty!!" );
return 0;
}

char data = front.data;

if (front.rlink == null) {
front = null;
rear = null;
} else {
front = front.rlink;
front.llink = null;
}

return data;
}

public char deleteRear() {
if (isEmpty()) {
System.out.println("Rear Removing Fail!! DQueue is empty!!" );
return 0;
}

char data = rear.data;

if (rear.llink == null) {
rear = null;
front = null;
} else {
rear = rear.llink;
rear.rlink = null;
}

return data;
}



public void removeFornt() {
if (isEmpty()) {
System.out.println("Front Removing Fail!! DQueue is empty!!" );
return;
}

if (front.rlink == null) {
front = null;
rear = null;
} else {
front = front.rlink;
front.llink = null;
}

}

public void removeRear() {
if (isEmpty()) {
System.out.println("Rear Removing Fail!! DQueue is empty!!" );
return;
}

if (rear.llink == null) {
rear = null;
front = null;
} else {
rear = rear.llink;
rear.rlink = null;
}
}


public char peekFront() {
if (isEmpty()) {
System.out.println("Front Peeking Fail!! DQueue is empty!!" );
return 0;
}

return front.data;
}

public char peekRear() {
if (isEmpty()) {
System.out.println("Rear Peeking Fail!! DQueue is empty!!" );
return 0;
}

return front.data;
}

public void printDQueue() {
if (isEmpty()) {
System.out.println("DQueu is Empty.");
} else {
DQNode temp = front;
System.out.print("DQUEUE>>");

while (temp != null) {
System.out.printf("%C", temp.data);
temp = temp.rlink;
}

System.out.println();
System.out.println();
}
}

public static void main(String[] args) {
char deleteItem;
DQueue deque = new DQueue();
deque.insertFront('A');
deque.printDQueue();

deque.insertFront('B');
deque.printDQueue();

deque.insertRear('C');
deque.printDQueue();

deleteItem = deque.deleteFornt();
System.out.println("Front delete Item" + deleteItem);
deque.printDQueue();

deleteItem = deque.deleteRear();
System.out.println("Rear delete Item" + deleteItem);
deque.printDQueue();

deque.insertRear('D');
deque.printDQueue();

deque.insertFront('E');
deque.printDQueue();

deque.insertFront('F');
deque.printDQueue();

deque.insertFront('G');
deque.printDQueue();

}
}


'java' 카테고리의 다른 글

Map  (0) 2017.11.15
이진 탐색 트리  (0) 2017.11.15
연결큐  (0) 2017.11.15
원형 큐  (0) 2017.11.15
Queue는 무엇인가?  (0) 2017.11.15