Introduction to Data Structures for Interviews: Stack And Queue

Introduction to Data Structures for Interviews: Stack And Queue
Introduction to Data Structures for Interviews: Stack And Queue

Introduction

Before learning about stack and queue, let us first focus on Data Structures Interviews. Data Structure is one of the most important subjects in Computer Science and for all people who dream of cracking a Software Development Engineer (SDE) job in product-based companies. Proficient knowledge Data Structures help execute efficient projects.

Today, many programming jobs require extraordinary knowledge of Data Structures. They are likewise an essential piece during coding interviews. Solving Data Structures problems may be challenging during the initial stages, but it becomes a habit when you do it daily.

You can learn different algorithms and solve a lot of problems by using them. To master Data Structures, you need to be well efficient with the basics – Arrays, Linked Lists, Stack and Queue, Strings and finding the Time-Space Complexity for the solutions.

A data structure is a particular way of organizing data in a computer to use it effectively. For example, we can store a list of items having the same data type using the array/string data structure.

Data Structures are of two types: 

  • Primitive Data Structures: Primitive data structures can hold only a single value in one specific location, unlike the non-primitive data structures, which can be in a linear and non-linear order. 
    • These are the fundamental data types of the language—for example, float, integer, character, etc. 
  • Non-Primitive Data Structures: The Non-Primitive Data Structures are created with the help of primitive data structures. They are further classified into linear and nonlinear data types. 
    • The linear data types are storing the data inside the memory in a sequence one after. Ex: Arrays, Strings, Stack, Queue.
    • The Non-linear data types store them in random order. Therefore, they will be spread inside the memory in various places and can only be traced by the address. The example of non-linear data structures is graphs and trees, etc.

Image Source: Medium

Watch Parikh Jain, a Founding member of Coding Ninjas talks about a roadmap to study Stacks and Queues and how to tackle Data Structures Interviews

In this article, we will discuss two linear data structures – Stack and Queue and Data Structures Interviews

You must have seen a stack of books or might have been a part of a long queue of customers at the billing counter of a supermarket. Take a pause and remember how they both work.

Linear data structures work on the same principle. They organize their components in a straight line to grow or shrink if we add or remove an element, respectively. 

blog banner 1

Now let’s move on to our key topics.

What is Stack? 

We can define a stack as an abstract linear data type with a pre-defined capacity. Its functionality depends on the pop and pushes function. The pop removes the elements from the stack, whereas push adds the elements to the stack. 

The key feature of Stack, which makes it different from other data structures, is that it pursues the “Last In First Out”(LIFO) principle for insertion and deletion of the element.

Image Source: Tutorials Point

From the above image, we can picture the functions and principles of the stack’s push and pop functions. Stacks are used for implementing functions, expression evaluation, and some algorithms. 

Ex: We have many real-life examples like a stack of plates or books. Our browsers follow the same principle to collect the track of last visited sites and the call log stored in the mobile phones. Another good example is the undo and redo function in our computer.

Basic Operations of Stack:

  • push(): Push function stores the element in the stack.
  • pop(): Pop function remove the element from the stack,
  • peek(): This operation helps to get the top element of the stack without removing it from the stack.
  • isFull(): This function checks whether the stack is full or empty.
  • isEmpty(): This function checks the stack is empty.

Implementation of Stack:

We can implement a stack using Arrays and Linked lists.

Here, we will learn to implement Stack using the array.

  • Below, C++ code shows the primary two operations on the stack: Push and Pop.
  • Note: The code is written in C++ because it is easy to understand for new learners.

Code To Implement Stack

# include<iostream>
using namespace std;
class Stack
{
    int top;
    public:
    int a[10];  
    Stack()
    {
        top = -1;
    }
    void push(int x);
    int pop();
    void isEmpty();
};
void Stack::push(int x)
{
	//adds elements to stack
    if(top >= 10)
    {
        cout << "Stack Overflow element cannot be inserted\n";
    }
    else
    {
        a[++top] = x;
        cout << "Element Inserted"<<x<<”\n”;
    }
}
int Stack::pop()
{
	//removes the element from stack
    if(top < 0)
    {
        cout << "Stack Underflow--No elements in stack\n";
        return 0;
    }
    else
    {
        int d = a[top--];
// here print the element which is popped
// like print 10 is popped out of stack.
		cout<<"The popped element:"<<d<<"\n";
        return d;
    }
}
void Stack::isEmpty()
{
    if(top < 0)
    {
        cout << "Stack is empty \n";
    }
    else
    {
        cout << "Stack is not empty \n";
    }
}

int main() {
    Stack s1;
    s1.push(10); //This will push 10 on the stack
    s1.push(100); //This will push 100 onto the stack
    s1.pop(); //This will pop out the topmost element from stack
}

Output:
Element Inserted:10
Element Inserted:100
The popped element:100

Explanation: When we insert 10, 100, it shows that an element is inserted. The pop function removes the topmost element from the stack i.e 100, and the remaining element in the stack is 10.

Time Complexity: In the above code

  • Push Operation takes O(1) time
  • Pop Operation takes O(1) time

What is Queue?

A queue is also an abstract linear data type with a predefined capacity. But then, how is it different from the stack? Well, they differ in how elements are removed from them.

Queue follows the “First in First Out” (FIFO) principle; that is, the element which comes first will be removed first just as in an actual queue you would see at a supermarket.

A queue is open from both ends, one end is for inserting, and the other is to remove the data. The diagram below shows the visual representation of queue functionalities.

Image Source: Tutorial and Examples

From the above diagram, we can infer two main functionalities in queue: Enqueue and Dequeue.

The inserting end is called Enqueue, which helps in inserting the data from one end, whereas the removing end is called Dequeue, which helps in removing the data from the queue.

Enqueue and Dequeue are also called  Rear and Front, respectively.

Basic Operations of Queue

  • enqueue(): This adds an item or data to the queue.
  • dequeue(): Dequeue removes the item from the queue.
  • peek(): This function gets the element at the front without removing it.
  • isfull(): This checks if the queue is full.
  • isempty(): This function checks if the queue is empty or not.

Implementation of Queue

The queue can be implemented using Arrays, Stack, and Linked List, but the easiest way to implement it is an Array. 

Initially, the head(front) and the tail(rear) of the queue points to the first index of the array (0-based Indexing). Then, as we add elements to the queue, the tail keeps moving ahead, always pointing to the index of the next element while the head remains at the first index. Thus, to implement a primary queue, we need only two functions: enqueue and dequeue.

Code To Implement Queue

#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();
};
void Queue :: enqueue(int x)
{
	//adds elements to queue
    if(front == -1) {
        front++;
    }
    if(rear == SIZE-1)
    {
        cout << "Queue is full";
    }
    else
    {
        a[++rear] = x;
	    cout<<"Element inserted:"<<x<<"\n";
    }
}
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(10);
    q.enqueue(100);//Enqueue adds 100 to queue
    q.enqueue(1001);//adds 1001 to queue
    q.dequeue(); //removes the first element from queue
    q.display();    
    return 0;
}
Output:
Element inserted:10
Element inserted:100
Element inserted:1001
Deleted element:100
The remaining elements are:
100
1001

Explanation:

The enqueue function adds 10, 100, 1001 and the dequeue function removes the first element inserted, which is 10. So the remaining elements in queue 100,10001.

Time complexity: In the above code

  • Enqueue takes O(1) time
  • Dequeue takes O(1) time

So far, we have discussed all the fundamental aspects of Stack and Queues. 

We know everything has its own pros and cons. So now let’s read about the pros and cons of Stacks and Queues as well.

Advantages of Stack

  • Stack is easy to learn and implement for beginners.
  • Stacks are used to solving problems that work on recursion.
  • It allows you to control how memory is allocated and deallocated.

Disadvantages of Stack

  • Random access of elements is impossible in stacks.
  • Stacks are neither flexible nor scalable.

Advantages of Queue

  • Data queues are fast and optimised.
  • Queues are flexible.
  • They can handle multiple data types.

Disadvantages of Queue

  • Inserting and removing elements from the middle is complex.
  • Queues are not readily searchable. This is because it takes O(N) time to search.

Popular Applications of Stack and Queue:

Interview Questions on Stack and Queue:

Frequently Asked Questions

What is the best way to implement a stack?

We can implement a stack in two ways: arrays and linked lists, but the efficient way is to use arrays to have less time and space complexity.

What is a stack and queue example?

Stack has many applications. Some of them are taking plates or books which are placed one above the other. The best example of the queue is Call Center phone systems used to hold people calling them in order until a service representative is free.

What are the types of queues?

We have two types of queue: the circular queue and the priority queue. The first item of the circular queue is connected to the last to make a circle, and the elements of the priority queue are sorted based on priority.

What is the difference between stack and queue?

Stack is only one end opened, so it follows the principle of Last in last out, and the queue has both ends opened it follows First in first out principle.

Key Takeaways

This focused on stack and queue data structures. We discussed the implementation of both the data structures, their advantages, disadvantages, and popular applications.

At last, we provided all the essential interview questions on the stack and queue, asked by the product-based companies like Amazon, Flipkart, Microsoft, etc. 

By Dharani Mandla