
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.
-
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.
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
Also read - Data Structure MCQ
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.
Now let’s move on to our key topics.
Also see, Must Do Coding Questions
Also see, Ensemble Learning
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.
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
Recommended Topic, Cognizant Eligibility Criteria
Also see - hash function in data structure