C++ Stacks and Queues use two stacks to implement a queue. You will implement al
ID: 647415 • Letter: C
Question
C++ Stacks and Queues
use two stacks to implement a queue. You will implement all of the basic functions of a queue container:
push: add an element onto the end of the queue (remember that a queue has a FIFO structure)
pop: remove the element at the front of the queue
front: look at the front element
back: look at the back element
size: check the queue's size
empty: check if the queue is empty
swap: given another queue, swap all elements with the other queue
You can use the std::stack container in order to implement your queue. The basic idea is that you will have one stack to take in your inputs, and another stack you will use to output values. Here is the basic pseudo code for enqueuing and dequeuing an element:
Enqueue: push element onto input stack
Dequeue: if output stack is not empty, pop element from output stack. Otherwise, pop elements from input stack and push them onto output stack. Then you can pop elements output stack
You should be able to run this main code with no issues:
int main(){
myQueue<int> q1, q2, q3;
for(int i = 0; i < 10; ++i){
q1.push(i);
}
for(int i = 0; i < 7; ++i){
q2.push(i);
}
cout<< "Initial Queue:"<<endl;
while(!q1.empty()){
cout << q1.front() << " " ;
q3.push(q1.front());
q1.pop();
}
cout<<endl<<"Size of Q3 (Q1 Reversed): "<<q3.size()<<endl;
cout<<"Back element of Q3: "<<q3.back()<<endl;
q3.swap(q2);
cout<<endl<<"Size of Q3 (after swap): "<<q3.size()<<endl;
cout<<endl<<"Size of Q2 (after swap): "<<q2.size()<<endl;
}
The output for the above main program should be:
Initial Queue:
0 1 2 3 4 5 6 7 8 9
Size of Q3 (Q1 Reversed): 10
Back element of Q3: 9
Size of Q3 (after swap): 7
Size of Q2 (after swap): 10
Explanation / Answer
/* Program to implement a queue using two stacks */
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
/* structure of a stack node */
struct sNode
{
int data;
struct sNode *next;
};
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);
/* structure of queue having two stacks */
struct queue
{
struct sNode *stack1;
struct sNode *stack2;
};
/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
push(&q->stack1, x);
}
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
int x;
/* If both stacks are empty then error */
if (q->stack1 == NULL && q->stack2 == NULL)
{
cout << "Queue is empty";
exit(0);
}
/* Move elements from satck1 to stack 2 only if
stack2 is empty */
if (q->stack2 == NULL)
{
while (q->stack1 != NULL)
{
x = pop(&q->stack1);
push(&q->stack2, x);
}
}
x = pop(&q->stack2);
return x;
}
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode));
if (new_node == NULL)
{
cout << "Stack overflow ";
exit(0);
}
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*top_ref);
/* move the head to point to the new node */
(*top_ref) = new_node;
}
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
int res;
struct sNode *top;
/*If stack is empty then error */
if (*top_ref == NULL)
{
cout << "Stack overflow ";
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
/* Driver function to test anove functions */
int main()
{
/* Create a queue with items 1 2 3*/
struct queue *q = (struct queue*) malloc(sizeof(struct queue));
q->stack1 = NULL;
q->stack2 = NULL;
cout << "Enqueuing...";
cout << endl;
enQueue(q, 1);
cout << "Enqueuing...";
cout << endl;
enQueue(q, 2);
cout << "Enqueuing...";
cout << endl;
enQueue(q, 3);
/* Dequeue items */
cout << "Dequeuing...";
cout << deQueue(q) << " ";
cout << endl;
cout << "Dequeuing...";
cout << deQueue(q) << " ";
cout << endl;
cout << "Dequeuing...";
cout << deQueue(q) << " ";
cout << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.