DEQUE Program!

Question

xavier666 56 Junior Poster

14 Years Ago

I've tried to make a DEQUE program. My book on data structures (Seymour Lipschutz) doesn't have an algorithm on DEQUES. Neither does DADS give a good description.
All I heard was that it could be implemented better with two lists (one forward and one backward) & there are 2 types of DEQUES (INPUT & OUTPUT restricted). But the program has become too long. So I was wondering if the code can be made shorter.
Please offer your (constructive) criticisms

#include <stdio.h>
#include <malloc.h>

/*
 *===========================================================
 * PROGRAM DESCRIPTION - IMPLEMENTATION OF A DEQUE          |
 * AUTHOR              - SUMITRO BHAUMIK AKA "XAVIER666"    |
 * DATE                - 11TH DECEMBER, 2009                |
 * COMPILER            - CODE::BLOCKS 8.02                  |
 * OS                  - WINDOWS XP SP2                     |
 *===========================================================
 *
 * NOTES - I THINK THE RESTRICTION CODES (RC) NEEDS TO BE EXPLAINED
 * SINCE DEQUES CAN BE EITHER INPUT OR OUTPUT RESTRICTED,
 * ALL I DID WAS JUST NOT LET THE FUNCTION BE ACCESSSED.
 * THE RCs ARE CLOSELY LINKED WITH THESE (LINE 120) SWITCH CASE VALUES
 * IF THE USER WANTS INPUT TOP RESTRICTED, RC = 1
 * DURING THE DEQUE OPERATIONS MENU, IF THE RC IS SAME AS SWITCH CASE VALUE,
 * THAT OPTION IS RESTRICTED. THE OTHER RC CODES OPERATE THE SAME WAY
 */

typedef struct deque
{
	int data;
	struct deque *forward;
	struct deque *backward;
}node;

void push_top( int );       // SAME AS PUSHING IN STACK
void push_end( int );       // SAME AS PUSHING IN QUEUE
void pop_top( void );       // POPPING THE ELEMENTS FROM THE TOP OF DEQUE
void pop_end( void );       // POPPING THE ELEMENTS FROM THE BOTTOM OF DEQUE
void show_forward( void );  // DISPLAY OF DEQUE : TOP TO BOTTOM
void show_backward( void ); // DISPLAY OF DEQUE : BOTTOM TO TOP
int length_deque( void );   // PRINTS LENGTH OF DEQUE
void print_warning( void ); // PRINTS A RESTRICTION VIOLATION WARNING
void pause( FILE * );       // PAUSES THE PROGRAM DURING RUNTIME FOR READABILITY

int main()
{
    int element;            // STORES THE DATA (AN INTEGER NUMBER) FROM USER
    int option;             // STORES OPTIONS FROM USER
    int fl;                 // A FLAG VARIABLE
    int restriction_code;   // ITS VALUE DENOTES THE TYPE OF RESTRICTION IMPOSED
                            // ON THE DEQUE

    fl = 0;

    // THIS DO-WHILE LOOP FOR THE 'DEQUE OPERATIONS' MENU
    do
    {
                            // THIS MENU WILL NOT ALWAYS RUN EXCEPT WHEN NEEDED,
        if (fl == 0)        // <- HENCE THIS FLAG VARIABLE
        {

            // THIS DO-WHILE FOR THE 'TYPE OF DEQUE' MENU
            do
            {
                printf("\n\n\tWhat Type Of DEQUE Would You Like?");
                printf("\n\n\t\tINPUT Restricted ..... [1]");
                printf("\n\n\t\tOUTPUT Restricted .... [2]");
                printf("\n\n\t\tNon Restricted ....... [3]");
                printf("\n\n\tEnter Your Option : ");
                scanf("%d", &option);

                switch(option)
                {
                    case 1 :
                        restriction_code = 0;

                        printf("\n\n\tINPUT Restrictrion Type");
                        printf("\n\n\t\tTop Restricted ....... [1]");
                        printf("\n\n\t\tBottom Restricted .... [2]");
                        printf("\n\n\tEnter Your Option : ");
                        scanf("%d", &option);
                        pause(stdin);

                        restriction_code += option;
                        break;

                    case 2 :
                        restriction_code = 2;

                        printf("\n\n\tOUTPUT Restrictrion Type");
                        printf("\n\n\t\tTop Restricted ....... [1]");
                        printf("\n\n\t\tBottom Restricted .... [2]");
                        printf("\n\n\tEnter Your Option : ");
                        scanf("%d", &option);
                        pause(stdin);

                        restriction_code += option;
                        break;

                    case 3 :
                        break;

                    default:
                        printf("\n\n\tChoice Does Not Exist");
                        pause(stdin);
                        break;
                }
            }while(option > 3 || option < 1);

                            // THE TYPE OF DEQUE HAS BEEN DECIDED
            fl = 1;         // HENCE, WILL NOT RUN AGAIN EXCEPT WHEN NEEDED
        }

		printf("\n\t==================================\n");
		printf("\t|        DEQUE OPERATIONS        |");
		printf("\n\t==================================\n");
		printf("\n\n\tPush Element From Top ........ [1]");
		printf("\n\n\tPush Element From End ........ [2]");
		printf("\n\n\tPop Element From Top ......... [3]");
		printf("\n\n\tPop Element From End ......... [4]");
		printf("\n\n\tShow DEQUE From Front ........ [5]");
		printf("\n\n\tShow DEQUE From End .......... [6]");
		printf("\n\n\tShow Length Of DEQUE ......... [7]");
		printf("\n\n\tGo Back To DEQUE TYPE ........ [8]");
        printf("\n\n\tExit Program ................. [0]");

        printf("\n\n\tEnter Your Option : ");
        scanf("%d", &option);

        switch(option)
        {
            case 1 :
                if(option == restriction_code)
                {
					print_warning();
                    pause(stdin);
                    break;
                }
                printf("\n\n\tEnter The Element : ");
                scanf("%d",&element);
                push_top(element);
                pause(stdin);
                break;

            case 2 :
                if(option == restriction_code)
                {
					print_warning();
                    pause(stdin);
                    break;
                }
                printf("\n\n\tEnter The Element : ");
                scanf("%d",&element);
                push_end(element);
                pause(stdin);
                break;

            case 3 :
                if(option == restriction_code)
                {
					print_warning();
                    pause(stdin);
                    break;
                }
				pop_top();
                pause(stdin);
                break;

            case 4 :
                if(option == restriction_code)
                {
					print_warning();
                    pause(stdin);
                    break;
                }
				pop_end();
                pause(stdin);
                break;

            case 5 :
                show_forward();
                pause(stdin);
                break;

            case 6 :
                show_backward();
                pause(stdin);
                break;

            case 7 :
                printf("\n\n\tLength Of DEQUE : %d", length_deque());
                pause(stdin);
                break;

            case 8 :
                fl = 0;
                break;

            case 0 :
                printf("\n\n\tThank You ... ");
                break;

            default:
                printf("\n\n\tChoice Does Not Exist!");
                pause(stdin);
                break;
        }

	}while(option != 0);

    return 0;
}

node *head;     // STORES ADRESS OF STARTING ELEMENT
node *tail;     // STORES ADRESS OF ENDING ELEMENT
node *temp1;    // CONTROL VARIABLE FOR ALL FORWARD TRAVERSAL RELATED TASK
node *temp2;    // CONTROL VARIABLE FOR ALL BACKWARD TRAVERSAL RELATED TASK
node *temp3;    // STORES NEWLY GENERATED ADDRESS FOR FORWARD QUEUE
node *temp4;    // STORES NEWLY GENERATED ADDRESS FOR BACKWARD QUEUE
int length;     // STORES LENGTH OF DEQUE
int popped;     // STORES THE POPPED ELEMENT

void push_top( int n )
{
	temp1 = head;
	temp2 = tail;

	if(temp1 == NULL)   // EMPTY DEQUE
	{
		// 1ST TIME CREATING HEAD
		temp1 = (node *)malloc(sizeof(node));
		temp1 -> data = n;
		temp1 -> forward = NULL;
		head = temp1;

        // 1ST TIME CREATING TAIL
		temp2 = (node *)malloc(sizeof(node));
		temp2 -> data = n;
		temp2 -> backward = NULL;
		tail = temp2;
	}
	else
	{
        // ADDING NEW ELEMENT & MAKING IT THE NEW HEAD
        temp3 = (node *)malloc(sizeof(node));
        temp3 -> data = n;
        temp3 -> forward = head;
        head = temp3;

        // GOING TO 2ND LAST ELEMENT OF BACKWARD LIST
        while(temp2 -> backward != NULL)
            temp2 = temp2 -> backward;

        // ADDING NEW ELEMENT & MAKING IT POINT TO NULL
        temp4 = (node *)malloc(sizeof(node));
        temp4 -> data = n;
        temp4 -> backward = NULL;

        // POINTING THE 2ND LAST ELEMENT TO THE NEW LAST ELEMENT
        temp2 -> backward = temp4;
	}
	length ++;
}

void push_end( int n )
{
	temp1 = head;
	temp2 = tail;

	if(temp2 == NULL)   // EMPTY DEQUE
	{
		// 1ST TIME CREATING TAIL
		temp2 = (node *)malloc(sizeof(node));
		temp2 -> data = n;
		temp2 -> backward = NULL;
		tail = temp2;

        // 1ST TIME CREATING HEAD
		temp1 = (node *)malloc(sizeof(node));
		temp1 -> data = n;
		temp1 -> forward = NULL;
		head = temp1;
	}
	else
	{
        // ADDING NEW ELEMENT & MAKING IT TAIL
        temp4 = (node *)malloc(sizeof(node));
        temp4 -> data = n;
        temp4 -> backward = tail;
        tail = temp4;

        // GOING TO 2ND LAST ELEMENT OF FORWARD LIST
        while(temp1 -> forward != NULL)
            temp1 = temp1 -> forward;

        // ADDING NEW ELEMENT & MAKING IT POINT TO NULL
        temp3 = (node *)malloc(sizeof(node));
        temp3 -> data = n;
        temp3 -> forward = NULL;

        // POINTING THE 2ND LAST ELEMENT TO THE NEW LAST ELEMENT
        temp1 -> forward = temp3;
	}
	length ++;
}

void pop_top()
{
    temp1 = head;
    temp2 = tail;

    if(temp1 == NULL)       // EMPTY DEQUE
    {
        printf("\n\n\tDEQUE Empty!\n\tQUEUE UNDERFLOW\n");
        return;
    }
    else if(temp1 -> forward == NULL)   // IF THERE IS ONLY ONE ELEMENT,
    {                                   // THE 3RD 'ELSE' BLOCK WON'T WORK
        popped = temp1 -> data;         // HENCE, THIS 'ELSE IF' BLOCK
        free(temp1);
        head = NULL;

        free(temp2);
        tail = NULL;
        return;
    }
    else
    {
        // GOING TO 2ND ELEMENT OF FORWARD LIST
        temp3 = temp1 -> forward;
        popped = temp1 -> data;
        free(temp1);

        // MAKING THE 2ND ELEMENT THE NEW HEAD
        head = temp3;

        // GOING TO 2ND LAST ELEMENT OF BACKWARD LIST
        while(temp2 -> backward -> backward != NULL)
            temp2 = temp2 -> backward;

        // RELEASING THE LAST ELEMENT
        free(temp2 -> backward);

        // POINTING THE 2ND LAST ELEMENT TO NULL
        temp2 -> backward = NULL;
    }
    printf("\n\n\tPopped Element : %d", popped);
    length --;
}

void pop_end()
{
    temp1 = head;
    temp2 = tail;

    if(temp2 == NULL)       // EMPTY DEQUE
    {
        printf("\n\n\tDEQUE Empty!\n\tQUEUE UNDERFLOW\n");
        return;
    }
    else if(temp2 -> backward == NULL)  // IF THERE IS ONLY ONE ELEMENT,
    {                                   // THE 3RD 'ELSE' BLOCK WON'T WORK
        popped = temp2 -> data;         // HENCE, THIS 'ELSE IF' BLOCK
        free(temp2);
        tail = NULL;

        free(temp1);
        head = NULL;
    }
    else
    {
        // GOING TO 2ND ELEMENT OF BACKWARD LIST
        temp4 = temp2 -> backward;
        popped = temp2 -> data;
        free(temp2);

        // MAKING THE 2ND ELEMENT THE NEW HEAD
        tail = temp4;

        // GOING TO 2ND LAST ELEMENT OF FORWARD LIST
        while(temp1 -> forward -> forward != NULL)
            temp1 = temp1 -> forward;

        // RELEASING THE LAST ELEMENT
        free(temp1 -> forward);

        // POINTING THE 2ND LAST ELEMENT TO NULL
        temp1 -> forward = NULL;
    }

    printf("\n\n\tPopped Element : %d", popped);
    length --;
}

void show_forward()
{
    temp1 = head;

    if(temp1 == NULL)       // EMPTY DEQUE
    {
        printf("\n\n\tEMPTY DEQUE!");
        return;
    }

    printf("\n\n\tThe DEQUE :- ");
    while(temp1 != NULL)
    {
        printf("\n\t%d",temp1 -> data);
        temp1 = temp1 -> forward;
    }
}

void show_backward()
{
    temp2 = tail;

    if(temp2 == NULL)       // EMPTY DEQUE
    {
        printf("\n\n\tEMPTY DEQUE!");
        return;
    }

    printf("\n\n\tThe DEQUE :- ");
    while(temp2 != NULL)
    {
        printf("\n\t%d",temp2 -> data);
        temp2 = temp2 -> backward;
    }
}

int length_deque()
{
    return length;
}

void print_warning()
{
    printf("\n\n\tSorry! Restrictions Are Imposed On This Option");
    printf("\n\n\tTry The Other Options Or Lift The Restrictions");
}

void pause(FILE *in)
{
    printf("\n\n\tPress Enter To Continue ... ");
	if(!feof(in) && !ferror(in))
	{
		int ch;
		do
		{
			ch = getc(in);
		}while ( ch != '\n' && ch != EOF );

		clearerr(in);
	}
	getchar();
}

c

5 Contributors
6 Replies
258 Views
2 Years Discussion Span
Latest Post 12 Years Ago Latest Post by WaltP

WaltP 2,905 Posting Sage w/ dash of thyme

12 Years Ago

Compile the code and time them.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

vijaykrishnabor -7 Newbie Poster · Answer 1 · 2010-10-27T10:39:14+00:00

Hi
Sumitro Bhaumik

i have code for deque and it smaller and easy to understand
if so please let me know

#include <stdio.h>
#define MAX 5
struct deque
{
int arr[MAX];
int rearleft,rearright,frontleft,frontright;
};
void insertleft(struct deque *p ,int v)
{
if(p->rearleft+1==p->rearright)
{
printf("DEQUE OVERFLOW");
}
else
{
p->arr[++p->rearleft]=v;
}
}

void insertright(struct deque *p ,int v)
{
if(p->rearleft+1==p->rearright)
{
printf("DEQUE OVERFLOW");
}
else
{
p->arr[--p->rearright]=v;
}
}

int removeleft(struct deque *p)
{
if(p->frontleft==p->rearleft)
{
printf("DEQUE OVERFLOW");
return 0;
}
else
{
return p->arr[++p->frontleft];
}
}

int removeright(struct deque *p)
{
if(p->frontright==p->rearright)
{
printf("DEQUE OVERFLOW");
return 0;
}
else
{
return p->arr[--p->frontright];
}
}
main()
{
struct deque q;
int no,c;
q.rearleft=-1;
q.rearright=MAX;
q.frontright=MAX;
q.frontleft=-1;
insertleft(&q,11);
insertleft(&q,12);
insertright(&q,21);
insertright(&q,22);
printf("%d",removeleft(&q));
printf("%d",removeright(&q));
return o;
}

please do reply

xavier666 56 Junior Poster · Answer 2 · 2010-10-27T19:45:24+00:00

Hello Vijay,
Even though it's ok but it's using static memory allocation.

Anyways,
1) Correct me if i'm wrong, in the functions removeright & removeleft, shouldn't the error messages be "DEQUE UNDERFLOW"?
2) Line 71, it should be return 0 not return o :P
3) Use proper indentation
Thanks anyway...

PS don't bump old threads...

vijaykrishnabor -7 Newbie Poster · Answer 3 · 2010-10-27T20:01:47+00:00

hi
i am sorry friend bcouz
i was in hurry so i have cut past 1 function 3 time
i am now correcting the code
thank you friend for correcting me

#include <stdio.h>
#define MAX 5
struct deque
{
int arr[MAX];
int rearleft,rearright,frontleft,frontright;
};
void insertleft(struct deque *p ,int v)
{
if(p->rearleft+1==p->rearright)
{
printf("DEQUE OVERFLOW");
}
else
{
p->arr[++p->rearleft]=v;
}
}

void insertright(struct deque *p ,int v)
{
if(p->rearleft+1==p->rearright)
{
printf("DEQUE OVERFLOW");
}
else
{
p->arr[--p->rearright]=v;
}
}

int removeleft(struct deque *p)
{
if(p->frontleft==p->rearleft)
{
printf("DEQUE UNDERFLOW");
return 0;
}
else
{
return p->arr[++p->frontleft];
}
}

int removeright(struct deque *p)
{
if(p->frontright==p->rearright)
{
printf("DEQUE UNDERFLOW");
return 0;
}
else
{
return p->arr[--p->frontright];
}
}
main()
{
struct deque q;
int no,c;
q.rearleft=-1;
q.rearright=MAX;
q.frontright=MAX;
q.frontleft=-1;
insertleft(&q,11);
insertleft(&q,12);
insertright(&q,21);
insertright(&q,22);
printf("%d",removeleft(&q));
printf("%d",removeright(&q));
return 0;
}

dongre.avinash -4 Newbie Poster · Answer 4 · 2011-04-18T13:24:33+00:00

Here is my implementation of Deque but in C.
http://code.google.com/p/clibutils/source/browse/src/c_deque.c

mannika 0 Newbie Poster · Answer 5 · 2012-02-08T04:10:19+00:00

how much time do the functions like insert and remove in this code take?