i have my ds exam 2moro...plz cn any1 tell hw to do it. Implement the class STEU

Question

i have my ds exam 2moro...plz cn any1 tell hw to do it.
Implement the class STEUE: It’s a data structure which is Stack As well as a Queue, using inside 2-Stack Data structure.

Here is the ADT (Abstract Data Type .h file) of the class and you have to implement the definition of this ADT

class STEUE
{
Stack<int> S1, S2;

// Hint Use S1 for Stack and S2 for the help as for DeQueue Operation

bool Push_back(int T);
bool Pop_back(int & T); // Remove the value which is in the last
bool Dequeue (int & T); // Remove the value which is entered first
bool IsEmpty ();

/*
Above are the functions that you need to implement Also with each function write its time Complexity
*/

};

Explanation / Answer

Dude, my own implementation of Queue, using 2stack. I have 5 files here, 2 header files: Stack.h, Queue.h; 3 source files; Stack.cpp, Queue.cpp, main.cpp(I just check my functions in main, optional)
The Queue implementation using 2linked stacks, so we don't need the tail pointer. The idea is similar to the idea u use in Hanoi towers. If u need to insert to the tail - u push to the first stack. If u want to delete the head - u pop everything from our first stack and push that to the second, reversing the content of the second stack, and then pop from there. So here is my source:(if u have problems with setting up the project with this files, u can send me the message and I can send u my VS2010 project)
Queue class in Queue.h has just the functions u need in your statement.
Ask if u have any questions. And I defined the Data structure my for stack myself, I didn't use STL for the purpose of creation an object of stack.

Time complexities of Queue functions:

T(push) =  (1)
T(pop) =  (1) 
T(dequeue) =  (n)
T(isEmpty) =  (1) 

Stack.h:
#pragma once

#include <iostream>
using namespace std;

class node
{
public:
int value;
node *next;
};

class Stack
{
public:
Stack(); // Constructor, no return, function name as class name
~Stack(); // destructor, no return, function name as class name
bool isEmpty();
int pop();
void push(int value);
void main();
private:
node *top;
};



Queue.h:
#pragma once
#include "Stack.h"

class Queue
{
public:
Queue();
~Queue();
bool isEmpty();
int dequeue();
void enqueue(int value);
private:
Stack staA, staB;
};


Stack.cpp:
#include "Stack.h"
#include <iostream>
using namespace std;

Stack::Stack() // Constructor, no return, function name as class name
{
top = 0;
cout << "Stack constructor" << endl;
}
Stack::~Stack() // destructor, no return, function name as class name
{
// your code here
cout << "Stack destructor" << endl;
}
bool Stack::isEmpty()
{
if(top == 0)
{
return true;
}
return false;
}
int Stack::pop()
{
if(isEmpty()==true)
{
cout << "it is empty." << endl;
return -1;
}
int val = top->value;
node *to_del = top;
top = to_del->next;
delete to_del;
return val;
}
void Stack::push(int value)
{
node *to_push = new node;
to_push->value = value;
to_push->next = top;
top = to_push;
}


Queue.cpp:

#include "Queue.h"
#include "Stack.h"

Queue::Queue(): staA(), staB()
{
cout << "Queue constructor" << endl;
}

Queue::~Queue()
{
cout << "Queue destructor" << endl;
}

bool Queue::isEmpty()
{
if ((staA.isEmpty() == true) && (staB.isEmpty() == true))
return true;

return false;
}

int Queue::dequeue()
{
int temp, temp2;

if (staA.isEmpty() == false)
{
for (; staA.isEmpty() == false ;)
{
temp = staA.pop();
staB.push(temp);
}

temp = staB.pop();
for (; staB.isEmpty() == false ;)
{
temp2 = staB.pop();
staA.push(temp2);
}

return temp;
}

else
return -1;
}

void Queue::enqueue(int value)
{
staA.push(value);
}


main.cpp:

#include "Queue.h"
#include <iostream>
using namespace std;

int main()
{
int n;
Queue queue;

queue.enqueue(322);
cout << queue.dequeue() << endl;
cout << queue.dequeue() << endl;
queue.enqueue(323);
queue.enqueue(324);
cout << queue.dequeue() << endl;
queue.enqueue(325);

cout << "type a number: ";
cin >> n;

for(int i=1; i<=n; i++)
{
queue.enqueue(i);
}

while(queue.isEmpty() == false)
{
cout << queue.dequeue() << endl;
}

queue.enqueue(325);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.