Linked Lists

[d34dw4rd]

Parking lot simulation
This program simulates the operations of a parking lot. This particular parking lot consists of two alleys, each of which is wide enough for only one car and is closed at one end. You must use a Link List.
Alley A
Alley A is the primary parking location. Alley B is used only as a place to move cars out of the way when retrieving a car parked in the middle of Alley A.
Program execution starts with both alleys empty. The program repeatedly prompts the user to specify one of four commands:
1. Park a car
2. Retrieve a car
3. Display the contents of Alley A
4. Terminate the program
To park a car, the program generates a new ticket number (1,2,…), issues a ticket stub to the customer, and parks the car at the front of Alley A.
To retrieve a car, the program prompts the user for the ticket stub number and begins to search Alley A. The program moves each car at the front of Alley A to Alley B until it finds the desired car. All of the cars that were temporarily placed in Alley B are then moved back to Alley A.
Input for the program
Each input command consists of a single lowercase or uppercase letter:
1. 'd' or 'D' (To display the alley contents)
2. 'p' or 'P' (To park a car)
3. 'r' or 'R' (To retrieve a car)
4. 'q' or 'Q' (to terminate the program)

The main prompt for user commands is the following:
D) isplay P) ark R) etrieve Q) uit:
In response to the Park command, the program generates a ticket number and displays this number, denoted below by <t>:
Ticket no. = <t>
In response to Retrieve command, the program displays the following prompt for the ticket stub number:
Ticket no. :
The output for the Display command is as follows, where each <t> represents the integer ticket number of a car in the alley:
Alley A: <t> <t> <t> …
Error-Handling
1. The program ignores invalid user commands.
2. If the user tries to retrieve a car with a nonexistent ticket stub number, the program displays the message: "CAR NOT PARKED IN MY LOT."
3. If Alley A is full and the user wants to park a car, the program displays the message: "PARKING LOT FULL".

I've been able write a functioning programing using the stack class but i found out i'm not allowed to use the stack class and have to follow his starting points. This is my functioning code

#include <iostream>
#include <cctype>
#include <iomanip>
#include <stack>
using namespace std;

void ReadCommand(char&);
void ReadTicket(int&);

class PkgLotType
{
      public:
             void Park();
             void Retrieve(int ticketStub);
             void Display();
             PkgLotType();
      private:
              stack<int> alleyA;
              stack<int> alleyB;
              int ticket;
};

PkgLotType::PkgLotType()
{
   ticket = 0;
}

void PkgLotType::Park()
{
     if (alleyA.size() >= 5)
        cout << "PARKING LOT FULL\n";
     else
     {
         ticket++;
         cout << "Ticket no. = " << ticket << '\n';
         alleyA.push(ticket);
     }  
}

void PkgLotType::Retrieve(int ticketStub)
{
     int topTicket;
     bool found = false;
     
     while(!alleyA.empty() && !found)
     {
         topTicket = alleyA.top();
         alleyA.pop();
         if (topTicket == ticketStub)
            found = true;
         else
            alleyB.push(topTicket);
     }
     if (!found)
        cout << "CAR NOT PARKED IN MY LOT\n";
     while (!alleyB.empty())
     {
        alleyA.push(alleyB.top());
        alleyB.pop();
     }
}

void PkgLotType::Display()
{
     stack<int> tempStk = alleyA;
     
     cout << "Alley A: ";
     while (!tempStk.empty())
     {
        cout << setw(4) << tempStk.top();
        tempStk.pop();
     }
     cout << '\n';
}

int main()
{
    PkgLotType pkgLot;
    char command;
    int ticketStub;
    
    do
    {
        ReadCommand(command);
        switch(command)
        {
           case 'P':
                pkgLot.Park();
                break;
           case 'R':
                ReadTicket(ticketStub);
                pkgLot.Retrieve(ticketStub);
                break;
           case 'D':
                pkgLot.Display();
                break;
           default:
                ;
        }
    }
    while(command != 'Q');
    
    return 0;
}

void ReadCommand(char& command)
{
     cout << "\nD)isplay P)ark R)etrieve Q)uit: ";
     cin >> command;
     command = toupper(command);
}

void ReadTicket(int& ticketStub)
{
     cout << "Ticket no.: ";
     cin >> ticketStub;
}

This is the code i have to work with... i've started writing push and pop but its slow going because i'm not even sure what i'm doing

#include <iostream>
#include <cctype>
#include <iomanip>
using namespace std;

#define MAXSIZE 5
class CarNode {
      public:
             CarNode() : m_pNext(0), m_ticketNum(0) { }
             ~CarNode();
             CarNode(CarNode &): m_pNext(0), m_ticketNum(0) { }
             // assign next pointer
             void SetNext(CarNode* p){m_pNext=p;}
             // assign ticket number
             void SetTicketNum(int tN){m_ticketNum=tN;}
             // get the next pointer
             CarNode *GetNext(void){return(m_pNext);}
             // get the ticket number
             int GetTicketNum(void){return(m_ticketNum);}
      private:
              int m_ticketNum; // ticket number of car
              CarNode *m_pNext; // pointer to next node in stack
};

class CAlley {
      public:
             CAlley () : m_pTop(0), mSize(0), mMaxSize(MAXSIZE) { }
             ~CAlley () {}
             CAlley(CAlley &):m_pTop(0), mSize(0), mMaxSize(MAXSIZE) { }
             int Park(int); // park a car
             void Retrieve(int,CStack *); // retrieve a car
             void Terminate(); // quit the program
             void Display(char *); // display contents af alley
      private:
              void SetTop(CarNode *p){m_pTop=p;} // assign top pointer
              // check if stack is empty
              bool Empty(){return ((mSize==0) ? true : false);}
              // check if stack is full
              bool Full() {return ((mSize==MAXSIZE) ? true : false);}
              int Push(CarNode *); // push one node onto top of stack
              CarNode * Pop(); // pop one node from the top of stack
              CarNode *m_pTop; // pointer to top of Allay (stack)
              int mSize; // number of nodes in Allay (stack)
              int mMaxSize; //max number of nodes in Allay (stack)
};
////////////////////////////////////////////////////////////////
// Function: CAlley::Push
// Purpose: Add a new node to top of stack
// Parameters:
// CarNode * pNewNode- the node to be added to top of stack
// Local Variables:
// status - return 1 if pushed sucessfully
// - return 0 if stack was full
////////////////////////////////////////////////////////////////
int CAlley::Push(CarNode* pNewNode){    
    if(Full()){
         cout << "PARKING LOT IS FULL";
         return 0;
    }
    else{
         m_pTop = pNewNode;
         pNewNode -> GetNext = m_pTop;
         m_pTop = pNewNode;
         return 1;
    }
}
/////////////////////////////////////////////////////////////////
// Function: CAlley::Pop
// Purpose: Remove a node to top of Allay (stack).
// Parameters:
// CarNode * pNewNode- returns the node removed from top of Allay
// is zero if stack is empty
// Local Variables:
/////////////////////////////////////////////////////////////////
CarNode * CAlley::Pop(){
        if(Empty()){
             cout<<"PARKING LOT IS EMPTY";
        }
        else{
             CarNode *pNewNode;
             pNewNode = m_pTop;
             m_pTop = m_pTop -> GetNext;
             delete m_pTop;
        }
}
///////////////////////////////////////////////////////////////
// Function: CAlley::Park ( )
// Purpose: Park a car, if lot is not full. First allocate a
// node, then add it to the top of the stack
// Parameters:
// userTicketNum - the ticket number for the node to be added
// Local Variables:
// CarNode *pNewNode - local pointer to newly allocated node
// int status - 1 if parked sucessfully (lot not full)
// 0 if not parked (lot was full)
///////////////////////////////////////////////////////////////
int CAlley::Park(int userTicketNum){
    if (CarNode.Full())
         cout << "PARKING LOT FULL\n";
    else{
         userTicketNum++;
         cout << "Ticket no. = " << userTicketNum << '\n';
         CarNode.Push(userTicketNum);
    }  
}
///////////////////////////////////////////////////////////////
// Function: CAlley:: Retrieve ( int userTicketNum, CAlley *pB)
// Purpose: Retrieve a car from alley A. Search for the car/node
// based on ticket num. by driving a car (popping off top) out of
// A and driving (pushing onto top) into B.
// If the car is found, it is not pushed onto B, but rather,
// it is deleted. Then the cars in B are moved back into A.
//
// Parameters:
// userTicketNum - the ticket number for the node to be added
// pB - pointer to CAlley B
//
// Local Variables:
// CarNode *pCurr - local pointer used as index
// int found - 1 if car is found, 0 if not found
///////////////////////////////////////////////////////////////
void CAlley::Retrieve(int userTicketNum, CAlley *pB){
     int topTicket;
     bool found = false;
     
     while(!CarNode.Empty() && !found)
     {
         topTicket = CarNode.SetTop();
         CarNode.Pop();
         if (topTicket == userTicketNum)
            found = true;
         else
            pB.Push(topTicket);
     }
     if (!found)
        cout << "CAR NOT PARKED IN MY LOT\n";
     while (!pB.Empty())
     {
        CarNode.Push(pB.SetTop());
        pB.Pop();
     }
}

void CAlley::Display(char *)
{
}

void Terminate()
{
}

int main()
{
}

all the classes and headers names are by the professor... i have to use his variables and stuff to write it

[Lerner]

A stack is often built around a list where insertions and deletions occur only at the tail. So pop removes the last node of the list and push places a new node on the list. In this case the Alley class is also a pseudonym for a list masqueratding as a stack and park and retrieve take on the push and pop functionalilty. In order to get the program to run you will need to declare and give value to MAXSIZE.

In order to park a car you need to declare a new car node and give it a ticket number. I don't see a mechanism dedicated to generate a ticket number in the instruction set, so you will need to do that in main(). Pass the ticket number to Park() which checks if lot is full, and if it isn't then passes the number to Push(). No need to check if the alley is full in Push() cause it'll never be called if it is. In Push declare a new carNode pointer using dynamic memory, assign it the ticket number, assign it to the top node's next pointer and then assign the top node next pointer to top. Last increment the number of nodes in the list. Remember to use the public set/get functions where needed to deal with the private member variables of the carNode variables.

[d34dw4rd]

This is what I have so far:

#include <iostream>
#include <cctype>
#include <iomanip>
using namespace std;

#define MAXSIZE 5
class CarNode {
      public:
             CarNode() : m_pNext(0), m_ticketNum(0) { }
             ~CarNode();
             CarNode(CarNode &): m_pNext(0), m_ticketNum(0) { }
             // assign next pointer
             void SetNext(CarNode* p){m_pNext=p;}
             // assign ticket number
             void SetTicketNum(int tN){m_ticketNum=tN;}
             // get the next pointer
             CarNode *GetNext(void){return(m_pNext);}
             // get the ticket number
             int GetTicketNum(void){return(m_ticketNum);}
      private:
              int m_ticketNum; // ticket number of car
              CarNode *m_pNext; // pointer to next node in stack
};

class CAlley {
      public:
             CAlley () : m_pTop(0), mSize(0), mMaxSize(MAXSIZE) { }
             ~CAlley () {}
             CAlley(CAlley &):m_pTop(0), mSize(0), mMaxSize(MAXSIZE) { }
             int Park(int); // park a car
             void Retrieve(int,CAlley *); // retrieve a car
             void Terminate(); // quit the program
             void Display(char *); // display contents af alley
      private:
              void SetTop(CarNode *p){m_pTop=p;} // assign top pointer
              // check if stack is empty
              bool Empty(){return ((mSize==0) ? true : false);}
              // check if stack is full
              bool Full() {return ((mSize==MAXSIZE) ? true : false);}
              int Push(CarNode *); // push one node onto top of stack
              CarNode * Pop(); // pop one node from the top of stack
              CarNode *m_pTop; // pointer to top of Allay (stack)
              int mSize; // number of nodes in Allay (stack)
              int mMaxSize; //max number of nodes in Allay (stack)
};
////////////////////////////////////////////////////////////////
// Function: CAlley::Push
// Purpose: Add a new node to top of stack
// Parameters:
// CarNode * pNewNode- the node to be added to top of stack
// Local Variables:
// status - return 1 if pushed sucessfully
// - return 0 if stack was full
////////////////////////////////////////////////////////////////
int CAlley::Push(CarNode* pNewNode){    
    if(Full()){
         cout << "PARKING LOT IS FULL";
         return 0;
    }
    else{
//         m_pTop = pNewNode;
         (*pNewNode).SetNext(m_pTop);
         m_pTop = pNewNode;
         return 1;
    }
}
/////////////////////////////////////////////////////////////////
// Function: CAlley::Pop
// Purpose: Remove a node to top of Allay (stack).
// Parameters:
// CarNode * pNewNode- returns the node removed from top of Allay
// is zero if stack is empty
// Local Variables:
/////////////////////////////////////////////////////////////////
CarNode * CAlley::Pop(){
        if(Empty()){
             cout<<"PARKING LOT IS EMPTY";
        }
        else{
             CarNode *pNewNode;
             pNewNode = m_pTop;
             m_pTop = (*pNewNode).GetNext();
             delete m_pTop;
        }
}
///////////////////////////////////////////////////////////////
// Function: CAlley::Park ( )
// Purpose: Park a car, if lot is not full. First allocate a
// node, then add it to the top of the stack
// Parameters:
// userTicketNum - the ticket number for the node to be added
// Local Variables:
// CarNode *pNewNode - local pointer to newly allocated node
// int status - 1 if parked sucessfully (lot not full)
// 0 if not parked (lot was full)
///////////////////////////////////////////////////////////////
int CAlley::Park(int userTicketNum){
    if (Full())
         cout << "PARKING LOT FULL\n";
    else{
         userTicketNum++;
         cout << "Ticket no. = " << userTicketNum << '\n';
         CarNode NewNode;
//         NewNode -> m_ticketNum = m_ticketNum;
//         NewNode -> m_pNext = NULL;
         Push(&NewNode);
    }  
}
///////////////////////////////////////////////////////////////
// Function: CAlley:: Retrieve ( int userTicketNum, CAlley *pB)
// Purpose: Retrieve a car from alley A. Search for the car/node
// based on ticket num. by driving a car (popping off top) out of
// A and driving (pushing onto top) into B.
// If the car is found, it is not pushed onto B, but rather,
// it is deleted. Then the cars in B are moved back into A.
//
// Parameters:
// userTicketNum - the ticket number for the node to be added
// pB - pointer to CAlley B
//
// Local Variables:
// CarNode *pCurr - local pointer used as index
// int found - 1 if car is found, 0 if not found
///////////////////////////////////////////////////////////////
void CAlley::Retrieve(int userTicketNum, CAlley *pB){
     int topTicket;
     bool found = false;
     
     while(!Empty() && !found)
     {
         topTicket = SetTop();
         Pop();
         if (topTicket == userTicketNum)
            found = true;
         else
            pB.Push(topTicket);
     }
     if (!found)
        cout << "CAR NOT PARKED IN MY LOT\n";
     while (!pB.Empty())
     {
        Push(pB.SetTop());
        pB.Pop();
     }
}

void CAlley::Display(char *)
{
}

void Terminate()
{
}

int main()
{
}

[Lerner]

Does it work as is? How do you know if you don't have a driver program? Compiling is different from running.

Here's how I would try the Park/Push pair:

int CAlley::Park(int userTicketNum)
{    
    int returnValue;
    if (Full())  
    {       
       cout << "PARKING LOT FULL\n";    
       returnValue = 0;
     }
     else
    {       
        //declare a new CarNode pointer      
        CarNode * NewNode = new CarNode;       

        //populate variables for a new CarNode pointer      
        NewNode -> SetTicketNum(userTicketNum);         
        NewNode -> SetNext(m_pTop);    
   
        Push(NewNode);    
        returnValue = 1;
     }  
     return returnValue;
}

int CAlley::Push(CarNode* pNewNode)
{       
     SetTop(pNewNode); 
     ++mSize;
     return 1;    
}

This sequence means that the top of the stack, m_pTop, will always be the first node in the list/alley, which works out fine, rather than always being the last node of the list, which would be an alternative.

Here's my version or the Retrieve/Pop pair:

int CAlley::Retrieve(int userTicketNum, CAlley *pB)
{
   int returnValue = 0;
   CarNode * temp;
   bool found = false; 
     
   while(!Empty() && !found)    
   {         
      temp = Pop()   
      if (temp->GetTicketNumber() == userTicketNum)   
      {     
         found = true;   
         returnValue = 1;
         delete temp;
       }      
      else           
        pB.Push(temp);   
   }
   
   if (!found)        
      cout << "CAR NOT PARKED IN MY LOT\n";

   while (!pB.Empty())          
      Push(pB.Pop());  

   return returnValue;   
}

CarNode * CAlley::Pop()
{        
       CarNode * temp = m_pTop;             
       m_pTop = m_pTop->GetNext();               
       --mSize;
       return temp;
}