?
Solved

Queue application/Algorithms

Posted on 2003-02-27
6
Medium Priority
?
630 Views
Last Modified: 2010-04-17
Hi

I am tring to build two queues , then pass the data between them using the enqueue and the dequeue.Now I know I will need to loop , and check to one for end of file,while the other must check that the queue (1)is Not empty.
this is where I am coming up with different solutions.

So here is what I came up with . Maybe you can help me to understand what the output would be.

1 Q1  = createQueue
2 Q2  = createQueue
3 loop ( not end of file ) this one I think should read
                           should read the data.
       1 read number
       2 enqueue  (Q1 , number)
       3 enqueue  (Q2 , number)
       4 loop (not empty Q1)
          1 dequeue (Q1, x)
          2 enqueue (Q2, x)
data to use = 5,7,12,4,0,4,6

I think the Not ( logical ) is throwing me off. the first loop should read the data into both Queues. The second loop as long as the as Q1 is not empty do loop.
But I never get the same answer twice.  
I hope you can help me , thank you
mary
0
Comment
Question by:mary-25
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
6 Comments
 
LVL 4

Expert Comment

by:chaos_hooi
ID: 8040415
What are you trying to do exactly? You will get the following if you input 5(first),7,12,4,0,4,6:

Q1: (empty)
Q2: 5<-5<-7<-7<-12<-12<-4<-4<-0<-0<-4<-4<-6<-6

How did I get this? After you get a value(5), you enqueue both Q1 and Q2 with the value(5). Then, you go into another loop that will loop until Q1 is empty, but Q1 will only have one value(5) at that point, so you dequeue it and enqueue it into Q2... that's why it will have duplicates values in Q2... After that, you get the next number...
0
 

Author Comment

by:mary-25
ID: 8066295
I am a programmer for a Major oil co. (IT) and I am trying to learn Data Structures using Algorithm on my own.Something reccommended by my company.Tho there is no there to help us , we are on our own.
This book uses a approach to Pseudocode to C.....
What I am tring to determine that if I had two Queue's and the data as listed , and the algorithm I am writing ( hope it is right ) what are the contents of the two Queue's after the execution of the example shown.
Now since I am new to this Data Structure and have been programming for a number of years( with several languages learned). I am not sure what one can do with this , CAN I put THIS to C code to test it(HOW)  or can you only test it by hand?
I tried to contact the company where I purchased the book , but they will not sell the answer book, only to school, etc  if you know what I mean. Sure makes it hard to continue your upgrade .Written by Gilberg and Forouzan.
I am tring to improve my skills in programming.
I came across your site and started to look thru the listing but didnt find what I needed. Is there a way to search for what I need as listed above? For I will be using your site as I use this book.
thank you
Hope this answered your question
0
 
LVL 4

Accepted Solution

by:
chaos_hooi earned 200 total points
ID: 8068944
FIRST, this is not my website. It's more like a place for people to gather to get help from each other.

I never done a C program to create a Q before, only use C++... Anyway, here is the program of what your PseudoCode described. Make sure the comments are not in the second line (the comments that I made after the //).

#include <stdio.h>
#include <stdlib.h>

// Node Structure
struct QNode
{
  struct QNode *next;
  int data;
};


// Pointers to First Node and Last Node of both Queue
struct QNode *FirstNodeQ1 = NULL;
struct QNode *FirstNodeQ2 = NULL;
struct QNode *LastNodeQ1 = NULL;
struct QNode *LastNodeQ2 = NULL;

// Declaration of the functions
void Enqueue(int QNumber, int val);
int Dequeue(int QNumber);

int main()
{
  int val=1;

  // Open file for input (5 7 12 4 0 4 6)
  FILE *inp;
  inp = fopen("input.txt","r");

  // The outer while-loop, Enqueue the value to both queue
  while(fscanf(inp, "%d", &val) != EOF) // While not the end-of-file
  {
    Enqueue(1, val);
    Enqueue(2, val);
    // The inner while-loop, Enqueue value to Queue 2 that
    // you get from dequeueing Queue 1.
    while(FirstNodeQ1 != NULL) // While Queue 1 is not empty
    {
      Enqueue(2,Dequeue(1));
    }
  }

  // Print all value from Q2.
  while(FirstNodeQ2 != NULL) // While Queue 2 is not empty
  {
    printf("%d ", Dequeue(2)); // Print the value.
  }
  return 0;
}

void Enqueue(int QNumber, int val)
{
  // Allocate space for NEW Qnode
  struct QNode *newNode = (struct QNode *)malloc(sizeof(struct QNode));

  // Initialize value for the NEW QNode with value that you enqueue
  newNode->data = val;
  newNode->next = NULL;

  // Insert NEW QNode into the Queue 1 or Queue 2
  if(QNumber == 1) // For Queue 1
  {
    if(FirstNodeQ1==NULL) // When Queue 1 is empty
    {
      FirstNodeQ1=LastNodeQ1=newNode;
    }
    else // When Queue 1 is not empty
    {
      LastNodeQ1->next=newNode;
      LastNodeQ1=newNode;
    }
  }
  else // For Queue 2
  {
    if(FirstNodeQ2==NULL) // WHen Queue 2 is empty
    {
      FirstNodeQ2=LastNodeQ2=newNode;
    }
    else // When Queue 2 is not empty
    {
      LastNodeQ2->next=newNode;
      LastNodeQ2=newNode;
    }
  }
}

int Dequeue(int QNumber)
{
  struct QNode *delNode;
  int val;
  if(QNumber == 1) // For QUeue 1
  {
    delNode = FirstNodeQ1;
    val = FirstNodeQ1->data;
    if(FirstNodeQ1 == LastNodeQ1) // When there is only one node in Q1
    {
      FirstNodeQ1=LastNodeQ1=NULL;      
    }
    else // When there is more than one node in Q1
    {
      val = FirstNodeQ1->data;
      FirstNodeQ1=FirstNodeQ1->next;
    }
  }
  else // For QUeue 2
  {
    delNode = FirstNodeQ2;
    val = FirstNodeQ2->data;
    if(FirstNodeQ2 == LastNodeQ2) // When there is only one node in Q2
    {
      FirstNodeQ2=LastNodeQ2=NULL;      
    }
    else // When there is more than one node in Q2
    {
      val = FirstNodeQ2->data;
      FirstNodeQ2=FirstNodeQ2->next;
    }
  }
  // Deallocate space no longer used back to the memory
  free(delNode);

  return val; // Return the value to the calling function
}
0
 
LVL 4

Assisted Solution

by:chaos_hooi
chaos_hooi earned 200 total points
ID: 8069043
As for places to learn about C programming languages, try:

http://dmoz.org/Computers/Programming/Languages/C/

As for pseudocode, it should make sense, as it is, I guess... I hope... that's why pseudo-code is written in a first place to make a complicate code look clearer...

Personally, I would recommend learning about C++, instead, for this kind of stuffs. It's much simpler... For example, instead of using malloc() to allocate space in C, you just need a "new" to allocate space in C++...

http://dmoz.org/Computers/Programming/Languages/C%2b%2b/
0
 

Expert Comment

by:CleanupPing
ID: 9447450
mary-25:
This old question needs to be finalized -- accept an answer, split points, or get a refund.  For information on your options, please click here-> http:/help/closing.jsp#1 
EXPERTS:
Post your closing recommendations!  No comment means you don't care.
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Introduction to Processes

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question