Analyze the algorithms, provide a brief review of the stack(s) included, and exp
ID: 3811466 • Letter: A
Question
Analyze the algorithms, provide a brief review of the stack(s) included, and explain the time complexity of the individual functions (push & pop).
======================================================================================
Programs:
InventoryItem.h:
// Specification file for the InventoryItem class
#ifndef INVENTORYITEM_H
#define INVENTORYITEM_H
#include <string>
#include <iostream>
using namespace std;
class InventoryItem
{
private:
long serialNum; //integer variable for serial number
string manufactDate; //member that holds the date for part manfactured
int lotNum; //integer hold the lot number
public:
InventoryItem()
{
serialNum=0; //integer variable for serial number
manufactDate="01/01/2000"; //set default date as 01/01/2000
lotNum=0;
}
// Constructor
InventoryItem(long serialNum, string manufactDate,int lotNum)
{
setSerialNum(serialNum);
setManufactDate (manufactDate);
setLotNum(lotNum);
}
// define mutators here
void setSerialNum(long serialNum)
{
this->serialNum = serialNum;
}
void setManufactDate (string manufactDate)
{
this->manufactDate = manufactDate;
}
void setLotNum(int lotNum)
{
this->lotNum=lotNum;
}
// define accessors here
long getSerialNum() const
{
return serialNum;//return serial Number of the manufactured item
}
string getManufactDate()
{
return manufactDate;//return Date of the manufactured item
}
int getLotNum()
{
return lotNum;
}
friend ostream& operator<<(ostream &out,InventoryItem &item)
{
out << " Serial number: " << item.getSerialNum() << endl;
out << " Manufacture date: " << item.getManufactDate() << endl;
out << " LotNum: " << item.getLotNum() << endl;
return out;
}
};
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Stack.h:
// Dynamic type stack class that can hold objects of any class.
#include <iostream>
using namespace std;
// DynStack template
template <class T>
class Stack
{
private:
struct Node
{
T item;
Node *next;
};
Node *top;
public:
Stack(){ top = NULL; }
void push(T);
void pop(T &);
bool isEmpty();
};
template <class T>
void Stack<T>::push(T num)
{
Node *newNode = new Node; //Allocate a new node and store num there
newNode->item = num;
//If there are no nodes in the list, make the newNode first node.
if (isEmpty())
{
top = newNode;
newNode->next = NULL;
}
else //otherwise, insert newNode before top
{
newNode->next = top;
top =newNode;
}
}
template <class T>
void Stack<T>::pop(T &item)
{
Node *t; //temporary point
//make sure the stack isn't empty
if (isEmpty())
{
cout << "The stack is empty. ";
}
else //pop value off top of stack
{
item = top->item;
t = top->next;
delete top;
top = t;
}
}
template <class T>
bool Stack<T>::isEmpty()
{
if (top==NULL)
return true;
else
return false;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Inventory.cpp:
#include <iostream>
#include "InventoryItem.h"
#include "Stack.h"
using namespace std;
int main()
{
Stack<InventoryItem> inventoryStack; // create stack
InventoryItem item; // create inventory item object
int ch; // Menu choice
long serialNum; // Serial number
string manufactDate; // Manufacture date
int lotNum=1;
do
{
// Display the menu.
cout << " ------ Inventory Menu -------- ";
cout << "1. Enter a part into the inventory. ";
cout << "2. Take a part from the inventory. ";
cout << "3. Quit. ";
cout << "Please make a choice (1, 2, or 3): ";
cin >> ch;
// Validate choice
while (ch < 1 || ch > 3)
{
cout << "Please enter 1, 2, or 3: ";
cin >> ch;
}
// Act on the user's choice.
switch(ch)
{
case 1:
// Enter a part into inventory.
cout << " You have chosen to add an item to the inventory bin. ";
cout << "Enter the item's serial number: ";
cin >> serialNum;
cout << "Enter the item's manufacture date: ";
cin >> manufactDate;
inventoryStack.push(InventoryItem(serialNum,manufactDate,lotNum));
lotNum++;
break;
case 2:
// Take a part out of inventory.
cout << " You have chosen to remove an item from the inventory bin. ";
if (inventoryStack.isEmpty())
cout << "No parts to remove. ";
else
{
inventoryStack.pop(item);
cout << " The part you removed was: ";
cout <<item<< endl;
}
break;
case 3:
while (!inventoryStack.isEmpty())
{
inventoryStack.pop(item);//pop item from stack
//print poped item
cout << " The part was left in inventory: ";
cout <<item<< endl;
}
cout << "Goodbye! ";
break;
}
} while (ch != 3);
return 0;
}
Explanation / Answer
Review:
Your stack is completely working fine.
It has It has 3 methods and a constructor.
You can include a destructor too which will remove all the elements until the stack is empty.
//psuedocode
~stack()
{
while(!isEmpty())
pop(data);
}
push() is taking a node and pushing it onto the stack by creating a new node and allocating a memory for it.
If stack is empty, then top’s next is null, else top’s next is old top element
Similarly, pop() is checking if the stack is empty or not.
If it is not empty, then it is deallocating the memory and updating top.
Running time:
Both push() and pop() have running time of O(1) as we do not have any loop and both the operations are taking place in constant time. We are not going through the entire stack contents to push or pop anything. Simple top element is accessed in constant time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.