In: Computer Science
In C++
In this lab we will be creating a stack class and a queue class, both with a hybrid method combining linked list and arrays in addition to the Stack methods(push, pop, peek, isEmpty, size, print) and Queue methods (enqueue, deque, peek, isEmpty, size, print).
DO NOT USE ANY LIBRARY, implement each method from scratch.
Both the Stack and Queue classes should be generic classes.
Don't forget to comment your code.
Stack using Link List
// C++ program to Implement a stack
//using singly linked list
#include <bits/stdc++.h>
using namespace std;
// Declare linked list node
struct Node
{
int data;
struct Node* link;
};
struct Node* top;
// Utility function to add an element
// data in the stack insert at the beginning
void push(int data)
{
// Create new node temp and allocate memory
struct Node* temp;
temp = new Node();
// Check if stack (heap) is full.
// Then inserting an element would
// lead to stack overflow
if (!temp)
{
cout << "\nHeap Overflow";
exit(1);
}
// Initialize data into temp data field
temp->data = data;
// Put top pointer reference into temp link
temp->link = top;
// Make temp as top of Stack
top = temp;
}
// Utility function to check if
// the stack is empty or not
int isEmpty()
{
return top == NULL;
}
// Utility function to return top element in a stack
int peek()
{
// Check for empty stack
if (!isEmpty())
return top->data;
else
exit(1);
}
// Utility function to pop top
// element from the stack
void pop()
{
struct Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
// Top assign into temp
temp = top;
// Assign second node to top
top = top->link;
// Destroy connection between
// first and second
temp->link = NULL;
// Release memory of top node
free(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
struct Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow";
exit(1);
}
else
{
temp = top;
while (temp != NULL)
{
// Print node data
cout << temp->data << "-> ";
// Assign temp link to temp
temp = temp->link;
}
}
}
// Driver Code
int main()
{
// Push the elements of stack
push(11);
push(22);
push(33);
push(44);
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
// Delete top elements of stack
pop();
pop();
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
return 0;
}
Stack using array
/* C++ program to implement basic stack
operations */
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
class Stack {
int top;
public:
int a[MAX]; // Maximum size of Stack
Stack() { top = -1; }
bool push(int x);
int pop();
int peek();
bool isEmpty();
};
bool Stack::push(int x)
{
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
}
else {
a[++top] = x;
cout << x << " pushed into stack\n";
return true;
}
}
int Stack::pop()
{
if (top < 0) {
cout << "Stack Underflow";
return 0;
}
else {
int x = a[top--];
return x;
}
}
int Stack::peek()
{
if (top < 0) {
cout << "Stack is Empty";
return 0;
}
else {
int x = a[top];
return x;
}
}
bool Stack::isEmpty()
{
return (top < 0);
}
// Driver program to test above functions
int main()
{
class Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
return 0;
}
Queue using link list
#include <bits/stdc++.h>
using namespace std;
struct QNode {
int data;
QNode* next;
QNode(int d)
{
data = d;
next = NULL;
}
};
struct Queue {
QNode *front, *rear;
Queue()
{
front = rear = NULL;
}
void enQueue(int x)
{
// Create a new LL node
QNode* temp = new QNode(x);
// If queue is empty, then
// new node is front and rear both
if (rear == NULL) {
front = rear = temp;
return;
}
// Add the new node at
// the end of queue and change rear
rear->next = temp;
rear = temp;
}
// Function to remove
// a key from given queue q
void deQueue()
{
// If queue is empty, return NULL.
if (front == NULL)
return;
// Store previous front and
// move front one node ahead
QNode* temp = front;
front = front->next;
// If front becomes NULL, then
// change rear also as NULL
if (front == NULL)
rear = NULL;
delete (temp);
}
};
// Driven Program
int main()
{
Queue q;
q.enQueue(10);
q.enQueue(20);
q.deQueue();
q.deQueue();
q.enQueue(30);
q.enQueue(40);
q.enQueue(50);
q.deQueue();
cout << "Queue Front : " << (q.front)->data << endl;
cout << "Queue Rear : " << (q.rear)->data;
}
Queue using Array
// C++ program to implement a queue using an array
#include <bits/stdc++.h>
using namespace std;
struct Queue {
int front, rear, capacity;
int* queue;
Queue(int c)
{
front = rear = 0;
capacity = c;
queue = new int;
}
~Queue() { delete[] queue; }
// function to insert an element
// at the rear of the queue
void queueEnqueue(int data)
{
// check queue is full or not
if (capacity == rear) {
printf("\nQueue is full\n");
return;
}
// insert element at the rear
else {
queue[rear] = data;
rear++;
}
return;
}
// function to delete an element
// from the front of the queue
void queueDequeue()
{
// if queue is empty
if (front == rear) {
printf("\nQueue is empty\n");
return;
}
// shift all the elements from index 2 till rear
// to the left by one
else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
// decrement rear
rear--;
}
return;
}
// print queue elements
void queueDisplay()
{
int i;
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
// traverse front to rear and print elements
for (i = front; i < rear; i++) {
printf(" %d <-- ", queue[i]);
}
return;
}
// print front of queue
void queueFront()
{
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[front]);
return;
}
};
// Driver code
int main(void)
{
// Create a queue of capacity 4
Queue q(4);
// print Queue elements
q.queueDisplay();
// inserting elements in the queue
q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);
// print Queue elements
q.queueDisplay();
// insert element in the queue
q.queueEnqueue(60);
// print Queue elements
q.queueDisplay();
q.queueDequeue();
q.queueDequeue();
printf("\n\nafter two node deletion\n\n");
// print Queue elements
q.queueDisplay();
// print front of the queue
q.queueFront();
return 0;
}