※ 순차 자료구조 방식의 단점
- 사용 크기가 제한되어 있다.(큐의 크기를 마음대로 변경할 수 없다)
- 원소가 없어도 항상 처음 크기를 유지해야 된다(메모리 낭비가 생긴다)
이러한 문제를 해결하기 위해 연결 자료구조 방식을 이용하여 크기에 제한없는 연결 큐를 구현해 보자.
※ 연결 큐
- 연결 큐의 초기 상태(공백 큐)에서 front와 rear는 null이다.
- front는 첫번째 노드를 가르키고(Linked List에서의 head) rear는 마지막 노드를 가르킨다(Linked List에서의 tail)
※ 연결 큐 구현 소스
Interface
public interface Queue {
boolean isEmpty();
void enQueue(String item);
String deQueue();
void delete();
String peek();
}
Node
public class Node {
private String data;
protected Node link;
public Node(String data){
this.data = data;
this.link = null;
}
public String getData() {
return data;
}
}
LinkedQueue
public class LinkedQueue implements Queue {
private Node front;
private Node rear;
public LinkedQueue() {
this.front =null;
this.rear = null;
}
@Override
public boolean isEmpty() {
if(front ==null){
return true;
}else{
return false;
}
}
@Override
public void enQueue(String item) {
Node newNode = new Node(item);
if(front ==null){
rear = newNode;
front = newNode;
}else{
rear.link = newNode;
rear = newNode;
}
}
@Override
public String deQueue() {
if(front==null){
System.out.println("Queue is empty");
return null;
}else{
String qValue = front.getData();
front = front.link;
if(front ==null){
rear =null;
}
return qValue;
}
}
@Override
public void delete() {
if(front==null){
System.out.println("Queue is empty");
}else{
front = front.link;
if(front ==null){
rear = null;
}
}
}
@Override
public String peek() {
return front.getData();
}
public void printQueue(){
if(front ==null){
System.out.println("Queue is empty");
}else{
Node temp = front;
while(temp.link != null){
System.out.print("value : " + temp.getData() + " ");
temp= temp.link;
}
System.out.println("value : " + temp.getData());
}
}
}
Main
public class Main {
public static void main(String[] args) {
String deleteItem;
LinkedQueue lq = new LinkedQueue();
lq.enQueue("A");
lq.printQueue();
lq.enQueue("B");
lq.printQueue();
deleteItem = lq.deQueue();
System.out.println(deleteItem);
lq.printQueue();
lq.enQueue("C");
lq.printQueue();
deleteItem = lq.deQueue();
System.out.println(deleteItem);
deleteItem = lq.deQueue();
System.out.println(deleteItem);
deleteItem = lq.deQueue();
System.out.println(deleteItem);
}
}
※ 덱(Deque, Double-ended Queue)
큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐, 스택의 성질과 큐의 성질을 모두가지고 있다.
※ 덱(Deque, Double-ended Queue) 구현 소스
Node
public class Node {
private String data;
protected Node r_link;
protected Node l_link;
public Node(String data){
this.data=data;
this.r_link = null;
this.l_link = null;
}
public String getData(){
return data;
}
}
DeQueue
public class DeQueue {
private Node front;
private Node rear;
public DeQueue() {
this.front = null;
this.rear = null;
}
public boolean isEmpty(){
return (front == null && rear == null);
}
public void insertFront(String data){
Node newNode = new Node(data);
if(isEmpty()){
front = newNode;
rear = newNode;
}else{
newNode.r_link = front;
front.l_link = newNode;
front = newNode;
}
}
public void insertRear(String data){
Node newNode = new Node(data);
if(isEmpty()){
front = newNode;
rear = newNode;
}else{
newNode.l_link= rear;
rear.r_link =newNode;
rear = newNode;
}
}
public String deleteFront(){
if(isEmpty()){
System.out.println("DeQueue is empty");
return null;
}else{
String DqValue = front.getData();
if(front.r_link==null){
front = null;
rear = null;
}else{
front = front.r_link;
front.l_link=null;
}
return DqValue;
}
}
public String deleteRear(){
if(isEmpty()){
System.out.println("DeQueue is empty");
return null;
}else{
String DeQueue = rear.getData();
if(rear.l_link ==null){
rear = null;
front = null;
}else{
rear = rear.l_link;
rear.r_link= null;
}
return DeQueue;
}
}
public String peekFront(){
if(isEmpty()){
System.out.println("DeQueue is empty");
return null;
}else{
return front.getData();
}
}
public String peekRear(){
if(isEmpty()){
System.out.println("DeQueue is empty");
return null;
}else{
return rear.getData();
}
}
public void removeFront(){
if(isEmpty()){
System.out.println("DeQueue is empty");
}else{
if(front.r_link == null){
front =null;
rear =null;
}else{
front = front.r_link;
front.l_link =null;
}
}
}
public void removeRear(){
if(isEmpty()){
System.out.println("DeQueue is empty");
}else{
if(rear.l_link ==null){
front=null;
rear=null;
}else{
rear = rear.l_link;
rear.r_link =null;
}
}
}
public void printDeQueue(){
Node temp = front;
while(temp.r_link !=null){
System.out.print("value : " + temp.getData() +" ");
temp = temp.r_link;
}
System.out.println("value : " + temp.getData() +" ");
}
}
Main
public class Main {
public static void main(String[] args) {
String delItem;
DeQueue dq = new DeQueue();
dq.insertFront("A");
dq.printDeQueue();
dq.insertFront("B");
dq.printDeQueue();
dq.insertRear("C");
dq.printDeQueue();
delItem = dq.deleteFront();
System.out.println(delItem);
dq.printDeQueue();
delItem = dq.deleteRear();
System.out.println(delItem);
dq.printDeQueue();
dq.insertRear("D");
dq.printDeQueue();
dq.insertFront("E");
dq.printDeQueue();
dq.insertFront("F");
dq.printDeQueue();
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 05-1 트리 (0) | 2016.11.25 |
|---|---|
| 04-4 큐의 응용 (0) | 2016.11.25 |
| 04-2 큐의 구현(순차 자료구조를 이용한 큐) (0) | 2016.11.25 |
| 04-1 큐(Queue) (0) | 2016.11.25 |
| 03-4 스택의 응용 (0) | 2016.11.25 |
