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

Postorder traversal of a binary tree, Postorder traversal of a binary tree ...

Postorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; }; postorder(struct NODE

Explain floyds algorithm, Explain Floyd's algorithm It is convenient to...

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an

Representation of a polynomial with a singly linked list, List areutilized ...

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Binary search, Explain binary search with an example

Explain binary search with an example

Simulation of queues, Simulation of queues: Simulation is the process of f...

Simulation of queues: Simulation is the process of forming an abstract model of a real world situation in order to understand the effect of modifications and the effect of introdu

C++ function, Write c++ function to traverse the threaded binary tree in in...

Write c++ function to traverse the threaded binary tree in inorder traversal

Mathematical-model with a collection of operations, A mathematical-model wi...

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

Comparisons between linear and binary search, Comparative Study of Linear a...

Comparative Study of Linear and Binary Search Binary search is lots quicker than linear search. Some comparisons are following: NUMBER OF ARRAY ELEMENTS EXAMINED array

Prims algorithm, how to write prims algorithms? with example

how to write prims algorithms? with example

Row major representation, Row Major Representation In memory the primar...

Row Major Representation In memory the primary method of representing two-dimensional array is the row major representation. Under this representation, the primary row of the a

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