can ANYONE help? need to make a queue

[jaeSun]

i havent been able to find anyone to help me ....

i am looking to create a queue ....

i cant use a stack, as that is LIFO (last in, first out) ...

but i need a FIFO (first in, first out) ....

i have some code for a stack class using linked lists .... and i tried modifying the code to do FIFO, but i keep getting an error in this one spot (instead of popping the head of the stack, i would have it traverse the stack to the back and return the end ... but getting the element before the end to point to NULL, well, keeps crashing the program ....

can anyone help?

[vegaseat]

Here is some C code that might help you get started.

//  A linear list of data accessed first in, first out (FIFO) is called a QUEUE.
//  Pelles C  (vegaseat) 

#include <stdio.h>   // in/out function header
#include <string.h>  // string function header
#include <stdlib.h>  // malloc()

void enter(void);
void list(void);
void q_store(char *ptr);
void q_delete(void);
int store = 0;         // next storage position in queue[] 
int retrieve = 0;      // retrieve position in queue[] 
char *queue[100];      // this array forms the queue 

void main(void)
{
  enter();     // enter some data in the queue and list the data 
  puts("\n\nThis is all the data in the fifo queue:");
  list();   
  q_delete();  // delete first entry in queue and list again
  puts("\n\nThis the data after one deletion (first in, first out):");
  list();    
  getchar();
}

//
// prompt for data entry and store in queue via q_store()
//
void enter(void) 
{
  static char str[100], *ptr;

  do {
    printf("Enter name (ENTER only will exit) : ");
    gets(str);
    ptr = (char *) malloc(strlen(str));  // starting address of memory 
    strcpy(ptr,str);
    if (*str)  
      q_store(ptr);   // store in queue if string has info 
  } while (*str);     // until no entry
}

void list(void)   // list the contents of the queue 
{
  int k;

  for (k = retrieve; k < store; k++)
    printf("\n%d) %s",k+1,queue[k]);
}

//
// store data items in the queue 
//
void q_store(char *ptr)
{   
  if (store == 100) { 
    puts("\nList is full!");  
    return; 
  }
  queue[store] = ptr;
  store++;  // point to next available storage position in queue[] 
}

//
// delete data at retrieve position
//
void q_delete(void)     
{
  if (store == retrieve) { 
    puts("\nQueue is empty!"); 
    return; 
  }
  retrieve++;   // move retrieve position to next data item 
}

There could be more modern code for the puts() and gets() functions.

[jaeSun]

hmm ... i was doing it in C++ ...i kinda understand C

this is the code i was trying to do:

here is the main file:

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <string>
#include "stackli.h"
using namespace std;

struct flight {
  int num;
};

int main()
{

  flight ted;
  Stack<flight> readyq2;
  int print;

  ted.num = 1;
  readyq2.push(ted);
  ted.num = 2;
  readyq2.push(ted);
  ted.num = 3;
  readyq2.push(ted);

  ted = readyq2.topAndPop();
  cout<<ted.num<<endl;
  ted = readyq2.topAndPop();
  cout<<ted.num<<endl;
  ted = readyq2.topAndPop();
  cout<<ted.num<<endl;

  cout <<"hello"<<endl;

  return 0;
}

here is the header declaration for the stack:

#ifndef STACKLI_H
#define STACKLI_H
//#include "dsexceptions.h"
#include <iostream>       // For NULL
// Stack class -- linked list implementation
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// void push( x )         --> Insert x
// void pop( )            --> Remove most recently inserted item
// Object top( )          --> Return most recently inserted item
// Object topAndPop( )    --> Return and remove most recently inserted item
// bool isEmpty( )        --> Return true if empty; else false
// bool isFull( )         --> Return true if full; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Overflow and Underflow thrown as needed
template <class Object>
class Stack
{
 public:
  Stack( );
  Stack( const Stack & rhs );
  ~Stack( );
  bool isEmpty( ) const;
  bool isFull( ) const;
  const Object & top( ) const;
  void makeEmpty( );
  void pop( );
  void push( const Object & x );
  Object topAndPop( );
 private:
  struct ListNode
            {
	      Object   element;
	      ListNode *next;
	      ListNode( const Object & theElement, ListNode * n = NULL )
		: element( theElement ), next( n ) { }
            };
            ListNode *topOfStack;
};
#include "stackli.cpp"
#endif

and here is the implementation of the stack:

i commented where the problem lies ....

#include "stackli.h"
        #include <iostream>

/**
 * Construct the stack.
 */
        template <class Object>
        Stack<Object>::Stack( )
{
  topOfStack = NULL;
}

/**
 * Copy constructor.
 */
        template <class Object>
        Stack<Object>::Stack( const Stack<Object> & rhs )
{
  topOfStack = NULL;
  *this = rhs;
}

/**
 * Destructor.
 */
        template <class Object>
        Stack<Object>::~Stack( )
{
  makeEmpty( );
}

/**
 * Test if the stack is logically full.
 * Return false always, in this implementation.
 */
        template <class Object>
        bool Stack<Object>::isFull( ) const
{
  return false;
}

/**
 * Test if the stack is logically empty.
 * Return true if empty, false otherwise.
 */
        template <class Object>
        bool Stack<Object>::isEmpty( ) const
{
  return topOfStack == NULL;
}

/**
 * Make the stack logically empty.
 */
        template <class Object>
        void Stack<Object>::makeEmpty( )
{
  while( !isEmpty( ) )
    pop( );
}

/**
 * Get the most recently inserted item in the stack.
 * Return the most recently inserted item in the stack
 * or throw an exception if empty.
 */
        template <class Object>
        const Object & Stack<Object>::top( ) const
{
  if( isEmpty( ) )
    {}
  ListNode *current = topOfStack;

  while(current->next != NULL)
    {
      current = current->next;
    }

  return current->element;
}

/**
 * Remove the most recently inserted item from the stack.
 * Exception Underflow if the stack is empty.
 */
        template <class Object>
        void Stack<Object>::pop( )
{
  if( isEmpty( ) )
    {}

  ListNode *previous = topOfStack;
  ListNode *toTheEnd = topOfStack;

  while(toTheEnd->next != NULL)
    {
      previous = toTheEnd;
      toTheEnd = toTheEnd->next;
    }

  /*************************
  this next line is where the problem lies
  *************************/
  previous->next = NULL;
  delete toTheEnd;
}

/**
 * Return and remove the most recently inserted item
 * from the stack.
 */
        template <class Object>
        Object Stack<Object>::topAndPop( )
{
  Object topItem = top( );
  pop( );
  return topItem;
}

/**
 * Insert x into the stack.
 */
        template <class Object>
        void Stack<Object>::push( const Object & x )
{
  topOfStack = new ListNode( x, topOfStack );

}

i think the problem was that i cannot legally access the pointer within the struct ......

i thought of another solution to my problem ... i was going to use a binary heap .... and when it enters the queue, it gets a ticket number, and it will just sort based on that (ticket number just increases everytime) .....

not exactly the most effecient, but it works ....