Table of contents
1.
Introduction
2.
Array
2.1.
Implementation
3.
Queue
3.1.
Implementation
4.
Stack
4.1.
Implementation
5.
Difference
5.1.
 
5.2.
 
5.3.
Frequently Asked Questions(FAQs)
5.4.
What is the time complexity for inserting a new element in an array?
5.5.
What are FIFO and LIFO data structures?
5.6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Difference between Array, Queue and Stack

Author Malay Gain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Stacks

Introduction

Array, queue, and stack are basic Data Structures of computer science. Here we will see the comparison between their properties as well as implementation.

 

Array

An Array is a linear Data structure for storing items of the same data type at contiguous memory locations. 

 

Example

Memory Allocation Array

Here, 200 is the (base address)starting address assigned to its 1st element, and each element of the array is of integer data type that takes 4 bytes in memory.

 

Advantages

  • As each element in an array can be accessed by its index, access time is less for the array.

 

  • It is also easier to find the address of any element by using the address of the first element as location of the first element is denoted by the name of the array itself. We need to add a fixed value to it to reach the required element.

 

Implementation

#include<iostream>
using namespace std;


int main()
{
	int arr[5]={11,9,17,89,1};

	cout<<"base address: "<<arr<<endl; //base address
	cout<<*arr<<endl;

	//accessing  elements  using the address of the first element 
	for(int i=0;i<5;i++)
	{
		cout<<*(arr+i)<<" ";
	}

	return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

 

base address: 0x6ffe00 (it varies for different computer)

11

11 9 17 89 1

Also read about - hash function in data structure

Queue

Queue is also a linear data structure or abstract data type where an element is inserted from one end(i.e., rear), and an element is removed from the opposite end(i.e., front). For such type of property, the queue is called FIFO data structure.

 

Queue performs mainly two operations—

1. Enqueue to insert an element in the queue from the rear.

2. Dequeue to remove elements from the front.

 

Example

Queue Animation

Advantages

  • For dynamic addition and deletion of elements in a data structure, queues are used. We can achieve our tasks very efficiently as the queue requires O(1) time complexity for all the operations like enqueue and dequeue

 

  • It is used for scheduling tasks in the order of arrival by the operating system.

 

  • To implement many Graph Algorithms like breadth-first search, Dijkstra’s algorithm and Prim’s algorithm queues are used.

Must Read Algorithm Types

Implementation

#include<iostream>
using namespace std;
#define SIZE 10
class Queue
{
    int a[SIZE];
    int rear;  
    int front;  
    public:
    Queue()
    {
        rear = front = -1;
    }    
    void enqueue(int x);     
    int dequeue();
    void display();
};

// function for inserting elements to queue
void Queue :: enqueue(int x)
{

    if(front == -1) {
        front++;
    }
    if(rear == SIZE-1)
    {
        cout << "Queue is full";
    }
    else
    {
        a[++rear] = x;
    cout<<"Element inserted:"<<x<<"\n";
    }
}

// function for removeing the element from queue
int Queue :: dequeue()
{
//removes the top element from the queue.
    cout<<"Deleted element:"<<a[++front]<<"\n";
}


void Queue :: display()
{
    int i;
cout<<"The Remaining elements are:"<<"\n";
    for(i = front; i <= rear; i++)
    {
        cout << a[i] << endl;
    }
}

int main()
{
    Queue q;
    q.enqueue(11);
  	//Enqueue adds 13to queue
    q.enqueue(13);
	//adds 21 to queue
    q.enqueue(21);
	//removes the first element from queue
    q.dequeue();
    q.display();    
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

 

Stack

Stack is also a linear data structure or abstract data type where an element is inserted at the front(i.e, top) and an element is also removed from the same end(i.e.,, top). For such a type of property, the stack is called LIFO data structure.

 

Stack performs mainly two operations 
1. push to insert an element at the top.

2. pop to remove elements from the top.

 

Example

Stack

 

Implementation

#include<iostream>
using namespace std;


class Stack
{
    int top; // for locating the top of the stack
    
    public:
    int a[10];  
    Stack()
    {
        top = -1;
    }
    void push(int x);
    int pop();
    void isEmpty();
};

// function for inserting elements to stack
void Stack::push(int x)
{

    if(top >= 10)
    {
        cout << "Stack Overflow......element cannot be inserted\n";
    }
    else
    {
        a[++top] = x;
        cout << "Inserted element: "<<x<<endl;
    }
}

// function for removeing the element from stack
int Stack::pop()
{

    if(top < 0)
    {
        cout << "Stack Underflow--No elements in stack\n";
        return 0;
    }
    else
    {
        int d = a[top--];
        // printing the element which is popped

cout<<"The popped element: "<<d<<"\n";
        return d;
    }
}

// for checking if the stack empty or not
void Stack::isEmpty()
{
    if(top < 0)
    {
        cout << "Stack is empty \n";
    }
    else
    {
        cout << "Stack is not empty \n";
    }
}

int main() {
    Stack s1;
    s1.push(11); //This will push 11 on the stack
    s1.push(13); //This will push 13 onto the stack
    s1.pop(); //This will pop out the topmost element from stack
}
You can also try this code with Online C++ Compiler
Run Code

Read about Application of Queue in Data Structure here.

Must Read Stack Operations

Difference

Here is the tabular representation of their difference.

Array

Stack

Queue

In arrays, insertion and deletion can be done at any specified index. In stacks, insertion and deletion take place only from one end of the list called top. In queues, insertion and deletion take place only from the rear and front, respectively.
Array is a linear data structure in which any specified index can be accessed. It can be used to implement stack and queue. Stack is LIFO principle-based, i.e., last in, first out. A queue is FIFO principle-based, i.e., first in, first out.
There are different types of array based on its dimension, such as 1D, 2D, etc. Stack has no specific types.     There are a few types of queue available such as circular queue, priority queue.
An array contains elements of the same data type. A stack can contain elements of different types. Queue also can contain elements of different types.

 

 

Also read - Data Structure MCQ

Frequently Asked Questions(FAQs)

What is the time complexity for inserting a new element in an array?

As the size of the array is fixed when it is declared, if a new element has to be added to an array that is full, a new array of a greater size has to be declared and the elements in the existing array have to be copied to this array and then the new element is inserted in the end. This had the time complexity of O(n).

What are FIFO and LIFO data structures?

FIFO means First In First Out data structure meaning the element that has been inserted first is removed first e.g. Queue. A LIFO Data Structure is a Last in First Out Data Structure, meaning the element that is inserted last is removed first e.g. Stack

 

Conclusion

This article covered the difference between Array, Queue, and Stack from different perspectives. Having a good hold on these data structures is very important for cracking any coding round. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

You can also consider our Online Coding Courses such as the DSA in PythonC++ DSA CourseDSA in Java Course to give your career an edge over others.

Happy learning!

 

Live masterclass