STACK DATA STRUCTURE

Stack is an abstract data type with a bounded (predefined) capacity. It is a simple data structure
that allows adding and removing elements in a particular order. Every time an element is added,
it goes on the top of the stack and the only element that can be removed is the element that is at
the top of the stack, just like a pile of objects.

Basic features of Stack

1. Stack is an ordered list of similar data type.

2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to
remove an element from the stack. Both insertion and removal are allowed at only one
end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be
in Underflow state if it is completely empty.

Applications of Stack
The simplest application of a stack is to reverse a word. You push a given word to stack - letter
by letter - and then pop letters from the stack.
There are other uses also like:

1. Parsing
2. Expression Conversion(Infix to Postfix, Postfix to Prefix etc)
Implementation of Stack Data Structure
Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are
limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is
not limited in size. Here we will implement Stack using array.

Algorithm for PUSH operation

1. Check if the stack is full or not.

2. If the stack is full, then print error of overflow and exit the program.
3. If the stack is not full, then increment the top and add the element.

Algorithm for POP operation

1. Check if the stack is empty or not.

2. If the stack is empty, then print error of underflow and exit the program.
3. If the stack is not empty, then print the element at the top and decrement the top.

Below we have a simple C++ program implementing stack data structure while following the
object oriented programming concepts.
/* Below program is written in C++ language */

# include<iostream>

using namespace std;

class Stack
{
int top;
public:
int a[10]; //Maximum size of Stack
Stack()
{
top = -1;
}

// declaring all the function

void push(int x);
int pop();
void isEmpty();
};

// function to insert data into stack

void Stack::push(int x)
{
if(top >= 10)
{
cout << "Stack Overflow \n";
}
else
{
a[++top] = x;
cout << "Element Inserted \n";
}
}

// function to remove data from the top of the stack

int Stack::pop()
{
if(top < 0)
{
cout << "Stack Underflow \n";
return 0;
}
else
{
int d = a[top--];
return d;
}
}

// function to check if stack is empty

void Stack::isEmpty()
{
if(top < 0)
{
cout << "Stack is empty \n";
}
else
{
cout << "Stack is not empty \n";
}
}

// main function
int main() {

Stack s1;
s1.push(10);
s1.push(100);
/*
preform whatever operation you want on the stack
*/
}

Position of Top Status of Stack

-1 Stack is Empty
0 Only one element in Stack
N-1 Stack is Full
N Overflow state of Stack

Analysis of Stack Operations

Below mentioned are the time complexities for various operations that can be performed on the
Stack data structure.

 Push Operation : O(1)

 Pop Operation : O(1)
 Top Operation : O(1)
 Search Operation : O(n)

The time complexities for push() and pop() functions are O(1) because we always have to insert

or remove the data from the top of the stack, which is a one step process.
QUEUE DATA STRUCTURE
Queue is also an abstract data type or a linear data structure, just like stack data structure, in
which the first element is inserted from one end called the REAR(also called tail), and the
removal of existing element takes place from the other end called as FRONT(also called head).
This makes queue as FIFO(First in First Out) data structure, which means that element inserted
first will be removed first.
Which is exactly how queue system works in real world. If you go to a ticket counter to buy
movie tickets, and are first in the queue, then you will be the first one to get the tickets. Right?
Same is the case with Queue data structure. Data inserted first, will leave the queue first.
The process to add an element into queue is called Enqueue and the process of removal of an
element from queue is called Dequeue.

Basic features of Queue

1. Like stack, queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new
element in the queue must be removed, to remove the new element.
4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

Applications of Queue
Queue, as the name suggests is used whenever we need to manage any group of objects in an
order in which the first one coming in, also gets out first while the others wait for their turn, like
in the following scenarios:
 1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life scenario, Call Center phone systems uses Queues to hold people calling them
in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order
as they arrive i.e First come first served.

Implementation of Queue Data Structure

Queue can be implemented using an Array, Stack or Linked List. The easiest way of
implementing a queue is by using an Array.
Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array
(starting the index of array from 0). As we add elements to the queue, the tail keeps on moving
ahead, always pointing to the position where the next element will be inserted, while
the head remains at the first index.
When we remove an element from Queue, we can follow two possible approaches (mentioned
[A] and [B] in above diagram). In [A] approach, we remove the element at head position, and
then one by one shift all the other elements in forward position.
In approach [B] we remove the element from head position and then move head to the next
position.
In approach [A] there is an overhead of shifting the elements one position forward every time
we remove the first element.
In approach [B] there is no such overhead, but whenever we move head one position ahead, after
removal of first element, the size on Queue is reduced by one space each time.

Algorithm for ENQUEUE operation

1. Check if the queue is full or not.

 2. If the queue is full, then print overflow error and exit the program.
3. If the queue is not full, then increment the tail and add the element.

Algorithm for DEQUEUE operation

1. Check if the queue is empty or not.

2. If the queue is empty, then print underflow error and exit the program.
3. If the queue is not empty, then print the element at the head and increment the head.

/* Below program is written in C++ language */

#include<iostream>
using namespace std;
#define SIZE 10
class Queue
{
int a[SIZE];
int rear; //same as tail
int front; //same as head

public:
Queue()
{
rear = front = -1;
}

//declaring enqueue, dequeue and display functions

void enqueue(int x);
int dequeue();
void display();
};

// function enqueue - to add data to queue

void Queue :: enqueue(int x)
{
if(front == -1) {
front++;
}
if( rear == SIZE-1)
{
cout << "Queue is full";
}
else
 {
a[++rear] = x;
}
}

// function dequeue - to remove data from queue

int Queue :: dequeue()
{
return a[++front]; // following approach [B], explained above
}

// function to display the queue elements

void Queue :: display()
{
int i;
for( i = front; i <= rear; i++)
{
cout << a[i] << endl;
}
}

// the main function

int main()
{
Queue q;
q.enqueue(10);
q.enqueue(100);
q.enqueue(1000);
q.enqueue(1001);
q.enqueue(1002);
q.dequeue();
q.enqueue(1003);
q.dequeue();
q.dequeue();
q.enqueue(1004);
q.display();
return 0;
}
To implement approach [A], you simply need to change the dequeue method, and include
a for loop which will shift all the remaining elements by one position.

return a[0]; //returning first element

for (i = 0; i < tail-1; i++) //shifting all other elements
{
a[i] = a[i+1];
tail--;
}

Complexity Analysis of Queue Operations

Just like Stack, in case of a Queue too, we know exactly, on which position new element will be
added and from where an element will be removed, hence both these operations requires a single
step.

 Enqueue: O(1)
 Dequeue: O(1)
 Size: O(1)

What is a Circular Queue?

Before we start to learn about Circular queue, we should first understand, why we need a circular
queue, when we already have linear queue data structure.
In a Linear queue, once the queue is completely full, it's not possible to insert more elements.
Even if we dequeue the queue to remove some of the elements, until the queue is reset, no new
elements can be inserted. You must be wondering why?

When we dequeue any element to remove it from the queue, we are actually moving the front of
the queue forward, thereby reducing the overall size of the queue. And we cannot insert new
elements, because the rear pointer is still at the end of the queue.

The only way is to reset the linear queue, for a fresh start.
Circular Queue is also a linear data structure, which follows the principle of FIFO(First In First
Out), but instead of ending the queue at the last position, it again starts from the first position
after the last, hence making the queue behave like a circular data structure.

Basic features of Circular Queue

1. In case of a circular queue, head pointer will always point to the front of the queue,
and tail pointer will always point to the end of the queue.
2. Initially, the head and the tail pointers will be pointing to the same location, this would
mean that the queue is empty.

3. New data is always added to the location pointed by the tail pointer, and once the data is
added, tail pointer is incremented to point to the next available location.
4. In a circular queue, data is not actually removed from the queue. Only the head pointer is
incremented by one position when dequeue is executed. As the queue data is only the
data between head and tail, hence the data left outside is not a part of the queue anymore,
hence removed.

5. The head and the tail pointer will get reinitialised to 0 every time they reach the end of
the queue.
 6. Also, the head and the tail pointers can cross each other. In other words, head pointer can
be greater than the tail. Sounds odd? This will happen when we dequeue the queue a
couple of times and the tail pointer gets reinitialised upon reaching the end of the queue.

Going Round and Round

Another very important point is keeping the value of the tail and the head pointer within the
maximum queue size.
In the diagrams above the queue has a size of 8, hence, the value of tail and head pointers will
always be between 0 and 7.
This can be controlled either by checking everytime whether tail or head have reached
the maxSize and then setting the value 0 or, we have a better way, which is, for a value x if we
divide it by 8, the remainder will never be greater than 8, it will always be between 0 and 0,
which is exactly what we want.
So the formula to increment the head and tail pointers to make them go round and round over
and again will be, head = (head+1) % maxSize or tail = (tail+1) % maxSize

Application of Circular Queue

Below we have some common real-world examples where circular queues are used:

1. Computer controlled Traffic Signal System uses circular queue.

2. CPU scheduling and Memory management.

Implementation of Circular Queue

Below we have the implementation of a circular queue:
 1. Initialize the queue, with size of the queue defined (maxSize), and head and tail pointers.
2. enqueue: Check if the number of elements is equal to maxSize - 1:
o If Yes, then return Queue is full.
o If No, then add the new data element to the location of tail pointer and increment
the tail pointer.
3. dequeue: Check if the number of elements in the queue is zero:
o If Yes, then return Queue is empty.
o If No, then increment the head pointer.
4. Finding the size:
o If, tail >= head, size = (tail - head) + 1
o But if, head > tail, then size = maxSize - (head - tail) + 1

/* Below program is written in C++ language */

#include<iostream>

using namespace std;

#define SIZE 10

class CircularQueue
{
int a[SIZE];
int rear; //same as tail
int front; //same as head

public:
CircularQueue()
{
rear = front = -1;
}

// function to check if queue is full

bool isFull()
{
if(front == 0 && rear == SIZE - 1)
{
return true;
}
if(front == rear + 1)
 {
return true;
}
return false;
}

// function to check if queue is empty

bool isEmpty()
{
if(front == -1)
{
return true;
}
else
{
return false;
}
}

//declaring enqueue, dequeue, display and size functions

void enqueue(int x);
int dequeue();
void display();
int size();
};

// function enqueue - to add data to queue

void CircularQueue :: enqueue(int x)
{
if(isFull())
{
cout << "Queue is full";
}
else
{
if(front == -1)
{
front = 0;
}
rear = (rear + 1) % SIZE; // going round and round concept
// inserting the element
a[rear] = x;
cout << endl << "Inserted " << x << endl;
}
}

// function dequeue - to remove data from queue

int CircularQueue :: dequeue()
{
int y;

if(isEmpty())
{
cout << "Queue is empty" << endl;
}
else
{
y = a[front];
if(front == rear)
{
// only one element in queue, reset queue after removal
front = -1;
rear = -1;
}
else
{
front = (front+1) % SIZE;
}
return(y);
}
}

void CircularQueue :: display()

{
/* Function to display status of Circular Queue */
int i;
if(isEmpty())
{
cout << endl << "Empty Queue" << endl;
}
else
{
cout << endl << "Front -> " << front;
cout << endl << "Elements -> ";
for(i = front; i != rear; i= (i+1) % SIZE)
{
cout << a[i] << "\t";
}
cout << a[i];
cout << endl << "Rear -> " << rear;
}
}
int CircularQueue :: size()
{
if(rear >= front)
{
return (rear - front) + 1;
}
else
{
return (SIZE - (front - rear) + 1);
}
}

// the main function

int main()
{
CircularQueue cq;
cq.enqueue(10);
cq.enqueue(100);
cq.enqueue(1000);

cout << endl << "Size of queue: " << cq.size();

cout << endl << "Removed element: " << cq.dequeue();

cq.display();

return 0;
}