자료구조) (큐+스택) 이중연결리스트를 이용한 덱프로그램

예제 7-4 이중 연결 리스트를 이용한 덱 프로그램

#include <stdio.h>

#include <malloc.h>

typedef char element;

typedef struct DQNode{

element data;

struct DQNode *llink; //다음 노드를 가르킬 포인터

struct DQNode *rlink;

} DQNode; // 자료형 정의

typedef struct{ //연결큐 데이터 타입

DQNode *front, *rear;

} DQueType; // 자료형 정의

DQueType *createDQue()//공백 이중연결 덱을 생성

{

DQueType *DQ;

DQ = (DQueType *)malloc(sizeof(DQueType));//메모리 할당

DQ->front=NULL;

DQ->rear=NULL;

return DQ;

}

int isEmpty(DQueType *DQ) //덱이 공백인지 아닌지 검사

{

if (DQ->front == NULL) {

printf("\n Linked Queue is empty! \n");

return 1; //front 널이면 종료

}

else return 0;

}

void insertFront(DQueType *DQ, element item)//연결덱에 첫번째 원소를 삽입

{

DQNode *newNode=(DQNode *)malloc(sizeof(DQNode));

newNode->data = item;

if(DQ->front == NULL) {// front가 널이면 r,llink를 널로 잡아준다

DQ->front = newNode;

DQ->rear = newNode;

newNode->rlink = NULL;

newNode->llink = NULL;

}

else {

DQ->front->llink = newNode;

newNode->rlink = DQ->front;

newNode->llink = NULL;

DQ->front = newNode;

}

}

void insertRear(DQueType *DQ, element item) //연결덱에 마지막 원소를 삽입

{

DQNode *newNode=(DQNode *)malloc(sizeof(DQNode));

newNode->data = item;

if(DQ->front == NULL) {

DQ->front = newNode;

DQ->rear = newNode;

newNode->rlink = NULL;

newNode->llink = NULL;

}

else {

DQ->rear->rlink = newNode;

newNode->rlink = NULL;

newNode->llink = DQ->rear;

DQ->rear = newNode;

}

}

element deleteFront(DQueType *DQ) //연결덱에서 첫번째 원소를 삭제

{

DQNode *old = DQ->front;

element item;

if (isEmpty(DQ)) return 0;

else {

item = old->data;

if(DQ->front->rlink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->front = DQ->front->rlink;

DQ->front->llink = NULL;

}

free(old);

return item;

}

}

element deleteRear(DQueType *DQ) //연결덱에서 마지막 원소를 삭제

{

DQNode *old = DQ->rear;

element item;

if (isEmpty(DQ)) return 0;

else {

item = old->data;

if(DQ->rear->llink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->rear = DQ->rear->llink;

DQ->rear->rlink = NULL;

}

free(old);

return item;

}

}

void removeFront(DQueType *DQ) //연결덱에서 첫번째 원소를 삭제

{

DQNode *old = DQ->front;

if (isEmpty(DQ)) return;

else if(DQ->front->rlink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->front = DQ->front->rlink;

DQ->front->llink = NULL;

}

free(old);

}

void removeRear(DQueType *DQ) //연결덱에서 마지막 원소를 삭제

{

DQNode *old = DQ->front;

if (isEmpty(DQ)) return;

else if(DQ->rear->llink == NULL) {

DQ->front = NULL;

DQ->rear = NULL;

}

else {

DQ->rear = DQ->rear->llink;

DQ->rear->rlink = NULL;

}

free(old);

}

element peekFront(DQueType *DQ) //연결덱에서 첫번째 원소를 검색해서변환

{

element item;

if (isEmpty(DQ)) return 0;

else {

item = DQ->front->data;

return item;

}

}

element peekRear(DQueType *DQ) //연결덱에서 마지막 원소를 검색해서변환

{

element item;

if (isEmpty(DQ)) return 0;

else {

item = DQ->rear->data;

return item;

}

}

void printDQ(DQueType *DQ) // 기본 출력 문구 및 출력 위치 선정

{

DQNode *temp = DQ->front;

printf("\n DeQue : [");

while(temp) {

printf("%3c", temp->data);

temp = temp->rlink;

}

printf(" ]");

}

int main(void)

{

DQueType *DQ1 = createDQue();

element data;

insertFront(DQ1, 'A'); printDQ(DQ1); // A

insertFront(DQ1, 'B'); printDQ(DQ1); // BA

insertRear(DQ1, 'C'); printDQ(DQ1); // BAC

deleteFront(DQ1); printDQ(DQ1); // AC

deleteRear(DQ1); printDQ(DQ1); // A

insertRear(DQ1, 'D'); printDQ(DQ1); // AD

insertFront(DQ1, 'E'); printDQ(DQ1); // EAD

insertFront(DQ1, 'F'); printDQ(DQ1); // FEAD

data = peekFront(DQ1); printf("\n peek Front item : %c", data); //F

data = peekRear(DQ1); printf("\n peek Rear item : %c", data); //D

getchar();

return 0;

}

/* remove는 delete와 마찬가지로 원소 하나를 삭제하는 기능을 한다.

둘의 차이는 remove는 삭제 연산만 하고,

delete는 삭제연산한 후에 삭제한 원소의 데이터를 리턴한다 그러므로

삭제한 원소의 데이터가 필요한 경우에는 delete 연산을 사용하고,

삭제한 원소의 데이터가 필요없으면 remove 연산으로 처리해주면 된다.

*/