Suppose that you have a stack “myStack” and an empty auxiliary stack “bStack”. S
ID: 3806047 • Letter: S
Question
Suppose that you have a stack “myStack” and an empty auxiliary stack “bStack”. Show how you can do each of the following tasks by using only the ADT stack operations define in the stack ADT below:
stack ADT (Last-In-First-Out data structure)
Data: A sequence of data items that can be accessed at only one end,
called the top of the stack.
Operations:
Construct a stack (usually empty);
Check if the stack is empty;
Push(item): Add an element at the top of the stack;
Top: Retrieve and print the value of the item stored at the top of the stack;
Pop: Remove the top element of the stack;
a.Write code (pseudocode or C++) using the ADT operations to display the contents of myStack in reverse order; this is, display the top last. (hint: use bStack to help solve)
b.Write code (pseudocode or C++) using the ADT operations to count the number of items in myStack, leaving myStack unchanged. ) (hint: use bStack to help solve)
c.Write code (pseudocode or C++) using the ADT operations to delete every occurrence of a specified item from myStack, leaving the order of the remaining items unchanged. ) (hint: use bStack to help solve)
Explanation / Answer
#include <iostream>
#include <string>
using namespace std;
class l_node
{
public:
int info;
l_node *next;
};
class list_node
{
public:
int data;
list_node *next, *prev;
};
class List
{
public:
List();
List(const List &);
~List();
void Print_Div_By_5();
bool Search(int key);
private:
list_node *front;
};
void COPY(l_node * front1, l_node * & front2)
{
l_node *p, *q;
if (front1 == 0)
{
cout<<"Test for empty list ";
front2 = 0;
}
else
{
if (front2 != 0)
{
p = front2;
while(front2!=0)
{
p = front2;
front2 = front2->next;
delete p;
}
}
if (front1->next == 0)
{
cout<<"Test for 1 node ";
front2 = new l_node;
front2->info = front1->info;
front2->next = 0;
}
else
{
cout<<"Test for 2 or more nodes ";
front2 = new l_node;
front2->info = front1->info;
front2->next = 0;
p = front1->next;
q = front2;
while(p!=0)
{
q->next = new l_node;
q->info = p->info;
q = q->next;
q->next = 0;
p = p->next;
}
}
}
}
void Print(l_node *p)
{
while(p!=0)
{
cout<<p->info<<endl;
p=p->next;
}
}
int main()
{
l_node *front2=0, *front1=0, *p, *q;
//test for empty list
COPY(front1,front2);
Print(front2);
//test for list with one node
p = new l_node;
p->info = 1;
p->next = 0;
front1 = p;
COPY(front1, front2);
Print(front2);
q = front1;
for(int i = 0; i<5; i++)
{
q->next = new l_node;
q = q->next;
q->info = i+2;
q->next = 0;
}
COPY(front1,front2);
Print(front1);
/*2. Suppose that you have a stack myStack and an empty auxiliary stack bStack.
Show how you can do each of the following tasks by using only the ADT stack operations
define in the stack ADT below:
stack ADT (Last-In-First-Out data structure)
Data: A sequence of data items that can be accessed at only one end,
called the top of the stack.
Operations:
Construct a stack (usually empty);
Check if the stack is empty;
Push(item): Add an element at the top of the stack;
Top: Retrieve and print the value of the item stored at the top of the stack;
Pop: Remove the top element of the stack;
a. Write code (pseudocode or C++) using the ADT operations to display the contents of
myStack in reverse order; this is, display the top last.
(hint: use bStack to help solve) (10 pts)
while(!myStack.Empty())
{
bStack.push(myStack.pop())
}
while(!bStack.Empty())
{
bStack.Top();
myStack.push(bStack.pop())
}
b. Write code (pseudocode or C++) using the ADT operations to count the number of items in myStack,
leaving myStack unchanged. ) (hint: use bStack to help solve) (10 pts)
int count =0;
while(!myStack.Empty())
{
count++;
bStack.push(myStack.pop())
}
while(!bStack.Empty())
{
bStack.Top();
myStack.push(bStack.pop())
}
cout<<"count = "<<count;
c. Write code (pseudocode or C++) using the ADT operations to delete every occurrence of a specified
item from myStack, leaving the order of the remaining items unchanged. )
(hint: use bStack to help solve) (10 pts)
while(!myStack.Empty())
{
if (myStack.Top() == key)
{
myStack.pop()
}
else
{
bStack.push(myStack.pop())
}
}
while(!bStack.Empty())
{
bStack.Top();
myStack.push(bStack.pop())
}
3. In part a) of this question convert the infix expression to a postfix expression, and in part b) convert the postfix expression to a infix expression.
a) a / b / c * d - e * f + g * h * i / j + k (10 pts)
[[[((((a / b) /) c *) d) - (e * f)] + (((g * h) * i) / j)] + k]
a b / c / d * e f * - g h * i * j / + k +
b) a b c d + - * e f * g h + / /
((a * (b - (c + d))) / ((e * f) / (g + h)))
*/
/*4. Consider a circular list implemented as a doubly linked list with one pointer to the front.
Implement the Print_Div_By_5, Search and destructor for the class declaration below.
Remember to consider any special conditions.
a. Implement the Print_Div_By_5 function that prints all the data items in the nodes of
the list that are divisible by 5. (10 pts)
void Print_Div_By_5(list_node * front)
{
list_node *p = front;
if (p!=0)
{
if (p->next = front)
{
if (p->data % 5 == 0)
{
cout<<p->data<<endl;
}
else
{
while(front!=p->next)
{
if (p->data % 5 == 0)
{
cout<<p->data<<endl;
}
p = p->next;
}
if (p->data % 5 == 0)
{
cout<<p->data<<endl;
}
}
}
}
}
b. Implement the Search function to for the List class. If the key is there the function returns true;
otherwise it should return false. (10 pts)
bool Search(list_node * front, const int key)
{
list_node *p = front;
if (front == 0)
{
return false;
}
else if (front == front->next)
{
return (front->data == key);
}
else
{
while(p->next !=front)
{
if(p->data == key)
return true;
p = p->next;
}
if (p->data == key)
{
return true;
}
return false;
}
}
c. Implement the destructor for the List class. (10 pts)
List::~List()
{
list_node *p = front;
list_node *back = front;
if (front!=0)
{
back = front->prev;
while(front != back)
{
p = front;
front = front->next;
delete p;
}
delete front;
}
}
*/
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.