자료구조 최종정리 : 연결리스트 덱

덱(디큐라고도함)은 두개의 끝을 가지는 큐라는 뜻

양쪽 끝에서 자료의 삽입과 반환이 모두 가능한 선형 자료구조

기존 큐에서는 새로운 자료의 추가는 큐의 제일 뒤 리어에서만 가능하고 자료의 반환은 제일 앞 프런트에서만 가능했다면

덱에서는 끝이 두 개이므로 각각의 끝에서 자료의 추가와 반환이 모두 가능하다.

덱의 이러한 특성 때문에 큐와 스택의 기능을 합친 자료구조로도 설명이 된다.

 

연산		덱	스택	큐
앞 프런트	추가	inserFront	없음	없음
	반환	deleteFront	없음	dequeue
뒤 리어	추가	insertRear	push	enqueue
	반환	deleteRear	pop	없음

* a-steal 스케줄링 알고리즘이 덱의 기능을 요구한다는데..

 

여기서는 헤더노드가 아닌 헤더포인터로 구현하겠음

(둘 차이는 일반변수와 포인터의 차이랄까..처음 변수는 공변수가 되고..포인터는 null이 되서..처음이나 끝이나 중간 대입시 헤더노드는 일정한데..

헤더포인터는 처음대입시...중간..끝..모두 틀리다는데..자세한건 책 p185참고)

 

어쩃든..소스는 아래 주석을 잘 분석해보자..

#include<iostream>
#include<conio.h>
#include<string>
#include<vector>

using namespace std;

class DequeNode
{
public:
 char data;
 DequeNode *pRLink;
 DequeNode *pLLink;
};

class LinkedDeque
{
public:
 int m_currentElementCount;
 //여기서는 헤더 포인터로 구현
 //헤더 노드를 이용하게 되면..dequenode headerNode이런식이 되겠지..
 //뭐 pfrontnode prearnode이렇게 하는게 맞는듯..
 DequeNode *pFrontNode;
 DequeNode *pRearNode;

public:
 LinkedDeque()
 {
  m_currentElementCount=0;
  pFrontNode=NULL;
  pRearNode=NULL;
 }
 ~LinkedDeque()
 {
 }

 bool isLinkedDequeEmpty()
 {
  bool ret=false;
  if(m_currentElementCount==0)
  {
   ret=true;
  }
  return ret;
 }
 //노드를 front에 추가하는 함수
 //현재 덱의 상태가 공백인지에 따라 처리과정에 차이가 발생
 //1. 공백상태라면 제일 앞쪽 프런트 노드와 제일 뒤쪽 리어 노드가 모두 새로추가된 노드를 가리킴
 //2. 1개 이상 노드가 있다면 뒤쪽 리어노드만 변경시킴
 bool insertFrontLD(DequeNode element)
 {
  bool ret=false;
  DequeNode *pNode=NULL;
  pNode=new DequeNode;
  if(pNode!=NULL)
  {
   *pNode=element;
   pNode->pLLink=NULL;
   pNode->pRLink=NULL;
   
   //1. 공백상태인 경우
   if(isLinkedDequeEmpty())
   {
    pFrontNode=pNode;
    pRearNode=pNode;
   }

   //2. 1개 이상 노드가 있을경우
   else
   {
    pFrontNode->pLLink=pNode;
    pNode->pRLink=pFrontNode;
    pFrontNode=pNode;
   }
   m_currentElementCount++;
   ret=true;
  }
  return ret;
 }
 
 //위의 insertfront와 같다. 이건 insertrear
 bool insertRearLD(DequeNode element)
 {
  bool ret=false;
  DequeNode *pNode=NULL;

  pNode=new DequeNode;
  if(pNode!=NULL)
  {
   *pNode=element;
   pNode->pLLink=NULL;
   pNode->pRLink=NULL;

   if(isLinkedDequeEmpty())
   {
    pFrontNode=pNode;
    pRearNode=pNode;
   }
   else
   {
    pRearNode->pRLink=pNode;
    pNode->pLLink=pRearNode;
    pRearNode=pNode;
   }
   m_currentElementCount++;
   ret=true;
  }
  return ret;
 }
 
 //덱의 앞 노드 반환 deleteFront
 //1. 2개 이상의 노드가 있을시와 2. 노드가 1개인 덱에서의 있을시 2가지가 있다.(노드 제거 후 공백상태인지..)
 //2. 의 경우에서 제일 앞쪽 노드를 반환하기 때문에 pfrontnode에는 문제가 없으나
 //뒤쪽 리어 노드를 가리키는 pRearNode에 별도처리가 필요하다.
 DequeNode* deleteFrontLD()
 {
  DequeNode *pReturn=NULL;
  if(!isLinkedDequeEmpty())
  {
   pReturn=pFrontNode;
   pFrontNode=pFrontNode->pRLink;
   pReturn->pRLink=NULL; //제거된 자료에서 더이상 다른 노드로 접근을 해서는 안되기 때문에..
   
   m_currentElementCount--;
   //2. 덱에 남은 마지막 노드를 제거하는 경우
   if(isLinkedDequeEmpty())
   {
    pRearNode=NULL;
   }
   //1. 일반적인 경우
   else
   {
    pFrontNode->pLLink=NULL;
   }
  }
  return pReturn;
 }

 //덱의 뒤 노드 반환 deleteRear
 //앞 노드 반환과 비슷하다. 이건 반대로 앞쪽에 문제가 있겠지?(
 DequeNode* deleteRearLD()
 {
  DequeNode *pReturn=NULL;
  if(!isLinkedDequeEmpty())
  {
   pReturn=pRearNode;
   pRearNode=pRearNode->pLLink;
   pReturn->pLLink=NULL;
   m_currentElementCount--;
   if(isLinkedDequeEmpty())
   {
    pFrontNode=NULL;
   }
   else
   {
    pRearNode->pRLink=NULL;
   }
  }
  return pReturn;
 }
};