Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // IMPLEMENTARE UNA PILA CON I METODI DELLO STACK
- #include <iostream>
- using namespace std;
- template <class H> class LIFO{
- public:
- virtual LIFO<H>* push(H x) = 0;
- virtual H* pop() = 0;
- virtual void print() = 0;
- };
- template <class H> class FIFO{
- public:
- virtual FIFO<H>* enqueue(H x) = 0;
- virtual H* dequeue() = 0;
- virtual void print() = 0;
- };
- template <class T> class ArrayStack : public LIFO<T>{
- T* q; // array
- int top, length; // top: testa dello stack - length: dimensione dell'array
- public:
- ArrayStack(int length){
- q = new T(length);
- this->length = length;
- top = 0;
- }
- int isFull(){ return top == length; }
- int isEmpty(){ return top == 0; }
- int getSize(){ return top; }
- LIFO<T>* push(T x){
- if(!isFull())
- q[top++] = x;
- return this;
- }
- T* pop(){
- if(!isEmpty())
- return &q[--top];
- return NULL;
- }
- void print(){
- for(int i = top-1; i >= 0; i--)
- cout << q[i] << " ";
- cout << endl;
- }
- };
- template <class P> class Queue: public FIFO<P>{
- ArrayStack<P> *S1, *S2, *S3;
- void _swap(ArrayStack<P>* A, ArrayStack<P>* B){
- while(!A->isEmpty()) B->push(*(A->pop()));
- }
- public:
- Queue(int length){
- S1 = new ArrayStack<P>(length);
- S2 = new ArrayStack<P>(length);
- S3 = new ArrayStack<P>(2*length);
- }
- FIFO<P>* enqueue(P x){
- S1->push(x);
- return this;
- }
- P* dequeue(){
- if(S2->isEmpty()) _swap(S1, S2);
- return S2->pop();
- }
- void print(){
- _swap(S1, S3);
- _swap(S2, S1);
- _swap(S1, S3);
- S3->print();
- ArrayStack<P>* tmp = S2;
- S2 = S3;
- S3 = tmp;
- }
- };
- int main(){
- Queue<int> *Q = new Queue<int>(100);
- Q->enqueue(5)->enqueue(3)->enqueue(7)->enqueue(1)->print();
- Q->enqueue(4)->dequeue();
- Q->print();
- Q->dequeue();
- Q->print();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement