Linked list implementation of a dequeue, Data Structure & Algorithms

Assignment Help:

Double ended queues are implemented along doubly linked lists.

A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and right pointers. The right pointer points to the next node at the right while the left pointer points to the previous node at the left.  Program 9 described the linked list implementation of a Dequeue.

Program 9 : Linked list implementation of a Dequeue

# include "stdio.h"

#define NULL 0

struct dq {

int info;

int *left;

int *right;

};

typedef struct dq *dqptr;

dqptr p, tp;

dqptr head;

dqptr tail;

main()

{

int choice, I, x;

dqptr n;

dqptr getnode();

printf("\n Enter 1: Start 2 : Insertion at Front 3 : Insertion at Rear 4: Delete at Front 5: Delete at Back");

while (1)

{

printf("\n 1: Start 2 : Add at Front 3 : Add at Back 4: Delete at Front 5: Delete at Back 6 : exit");

scanf("%d", &choice);

switch (choice)

{

case 1:

create_list();

break;

case 2:

eq_front();

break;

case 3:

eq_back();

break;

case 4:

dq_front();

break;

case 5:

 

dq_back();

break;

case 6 :

exit(6);

}

}

}

create_list()

{

int I, x;

dqptr t;

p = getnode();

tp = p;

p->left = getnode();

p->info = 10;

p_right = getnode();

return;

}

dqptr getnode()

{

p = (dqptr) malloc(sizeof(struct dq));

return p;

}

dq_empty(dq q)

{

return q->head = = NULL;

}

eq_front(dq q, void *info)

{

if (dq_empty(q))

q->head = q->tail = dcons(info, NULL, NULL);

else

{

q-> head -> left =dcons(info, NULL, NULL);

q->head -> left ->right = q->head;

q ->head = q->head ->left;

}

}

eq_back(dq q, void *info)

{

if (dq_empty(q))

q->head = q->tail = dcons(info, NULL, NULL)

else

{

q-> tail -> right =dcons(info, NULL, NULL);

q->tail -> right -> left = q->tail;

q ->tail  = q->tail ->right;

}

}

dq_front(dq q)

{

if dq is not empty

{

dq tp = q-> head;

void *info = tp -> info;

q ->head = q->head-> right;

free(tp);

if (q->head = = NULL)

q -> tail = NULL;

else

q -> head -> left = NULL;

return info;

}

}

dq_back(dq q)

{

if (q!=NULL)

{

dq tp = q-> tail;

*info = tp -> info;

q ->tail = q->tail-> left;

free(tp);

if (q->tail = = NULL)

q -> head = NULL;

else

q -> tail -> right = NULL;

return info;

}

}


Related Discussions:- Linked list implementation of a dequeue

Brute force, Determine the number of character comparisons made by the brut...

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Perform breadth -first search, You are given two jugs, a 4-gallon one and a...

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Boar corloring, Board coloring , C/C++ Programming

Board coloring , C/C++ Programming

Mapping constain, one to many one to one many to many many to one

one to many one to one many to many many to one

Simplifying assumptions of wire frame representation, Simplifying Assumptio...

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

General, whats the definition of ADT and data type?

whats the definition of ADT and data type?

Hw7, Handout 15 COMP 264: Introduction to Computer Systems (Section 001) Sp...

Handout 15 COMP 264: Introduction to Computer Systems (Section 001) Spring 2013 R. I. Greenberg Computer Science Department Loyola University Water TowerCampus, Lewis Towers 524 82

Differentiate between nonpersistent and 1-persistent, Differentiate between...

Differentiate between Nonpersistent and 1-persistent Nonpersistent: If the medium is idle, transmit; if the medium is busy, wait an amount of time drawn from a probability dist

Explain the linked list implementation of stack, Question 1 Explain the fo...

Question 1 Explain the following? Arrays Stack Trees Question 2 Explain the Linked list implementation of stack Question 3 What is a binary tree? Expla

Explain the question, Merging 4 sorted files having 50, 10, 25 and 15 recor...

Merging 4 sorted files having 50, 10, 25 and 15 records will take time

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd