How would I use two stacks to implement the Queue API?? #include <iostream> #inc

Question

How would I use two stacks to implement the Queue API??

#include <iostream> #include <stdlib.h> #include <stack> #include <queue> #include <cassert> using namespace std; class Queue { private: stack<int> stack1; stack<int> stack2; public: //Write these two functions ONLY //edit code here // For this problem only use stack1 and stack2 void enqueue(int value){ // add to the "back" of the queue }; int dequeue(){ // remove and return the "oldest" // element in the queue return 0; }; //end code here }; int main() { //Don't edit main srand(321); Queue myQueue; //I'm using the STL queue side by side with yours //if they behave the same then you win... queue<int> testQueue; for(int i = 0; i < 300; i++){ //every 7 numbers dequeue int inputvalue = rand(); if (inputvalue % 7 == 0){ int value = myQueue.dequeue(); assert(value == testQueue.front()); testQueue.pop(); } else { //otherwise enqueue myQueue.enqueue(inputvalue); testQueue.push(inputvalue); } } while (!testQueue.empty()){ //the rest should match too! int value = myQueue.dequeue(); assert(value == testQueue.front()); testQueue.pop(); } cout << "All tests pass" << endl; }

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
void push(struct node** top, int data);
int pop(struct node** top);
struct queue
{
    struct node *stack1;
    struct node *stack2;
};
void enqueue(struct queue *q, int x)
{
    push(&q->stack1, x);
}
void dequeue(struct queue *q)
{
    int x;
    if (q->stack1 == NULL && q->stack2 == NULL) {
        printf("queue is empty");
        return;
    }
    if (q->stack2 == NULL) {
        while (q->stack1 != NULL) {
        x = pop(&q->stack1);
        push(&q->stack2, x);
        }
    }
    x = pop(&q->stack2);
    printf("%d ", x);
}
void push(struct node** top, int data)
{
    struct node* newnode = (struct node*) malloc(sizeof(struct node));
        if (newnode == NULL) {
            printf("Stack overflow ");
            return;
        }
    newnode->data = data;
    newnode->next = (*top);
    (*top) = newnode;
}
int pop(struct node** top)
{
    int buff;
    struct node *t;
    if (*top == NULL) {
        printf("Stack underflow ");
        return;
    }
    else {
        t = *top;
        buff = t->data;
        *top = t->next;
        free(t);
        return buff;
    }
}
void display(struct node *top1,struct node *top2)
{
    while (top1 != NULL) {
        printf("%d ", top1->data);
        top1 = top1->next;
    }
    while (top2 != NULL) {
        printf("%d ", top2->data);
        top2 = top2->next;
    }
}
int main()
{
    struct queue *q = (struct queue*)malloc(sizeof(struct queue));
    int f = 0, a;
    char ch = 'y';
    q->stack1 = NULL;
    q->stack2 = NULL;
    while (ch == 'y'||ch == 'Y') {
        printf("enter ur choice 1.add to queue 2.remove
               from queue 3.display 4.exit ");
        scanf("%d", &f);
        switch(f) {
            case 1 : printf("enter the element to be added to queue ");
                     scanf("%d", &a);
                     enqueue(q, a);
                     break;
            case 2 : dequeue(q);
                     break;
            case 3 : display(q->stack1, q->stack2);
                     break;
            case 4 : exit(1);
                     break;
            default : printf("invalid ");
                      break;
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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