Table of contents
1.
Introduction
2.
Problem statement
2.1.
Example
3.
Algorithm
4.
Implementation
5.
Algorithm Complexity
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
6.1.
What sorting algorithm does sort function in C++ use? 
6.2.
What's the difference between a queue and a stack?
6.3.
Stack is a recursive data structure, Why?  
6.4.
What is an example of a stack in real life?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Check if an array is stack sortable

Author SAURABH ANAND
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

We have so many ways to sort an array, starting from spoonfed loop to various sorting algorithms available to us. But today we will see a different approach to sorting an array. We will use a stack to sort the same. We will see if can we sort a given array by just popping and pushing elements into the stack various times to achieve our goal.

Suppose we have an array(arr[]) of size “n” with the elements in random order from 1 to n. Using a temporary stack, we will sort the array in ascending order using only these two methods —

  • Remove the element from the array's initial index and store it in the stack.
  • Append the top of the From stack to the end of another array.

Problem statement

Check if an Array is Stack Sortable. We will be given an array of “n” elements, We have to use the stack (pop and push operation) to sort the array.

Example

a) Let’s have a look at this example.

 int arr[] = {12, 31, 14, 11}; //we have an array

Input Array

This can’t be sorted using Stack

b) Let’s have another example

int arr[] = {12, 31, 14, 11};

Input Array

This array can be sorted using a stack.

Algorithm

Let’s have a look at the step-by-step solution to the problem.

  • Create an array a[] of size n.
  • Create a stack to hold the array's elements and a variable end = 0 to indicate the end.
  • If the stack is empty, traverse from 0 to n-1 and push the value of the array at the current index in the stack. Otherwise, put the stack's top in a variable top. Increase the end and pop the top while the top is equal to end+1. If the stack is empty, the loop is broken. Replace the variable top with the stack's current top.
  • If the stack is completely empty Push the array's value to the stack at the current index.
  • Otherwise, put the stack's top in a variable top. If the array value at the current position is less than the top, push the array element onto the stack. Otherwise, return false.
  • Return true.

Implementation

Let us see the code to check if array is stack sortable or not.

#include <bits/stdc++.h> 
using namespace std; 
  
bool check(int arr[], int x){ 
    stack<int> Stk; 
    int end = 0; 
    for(int i = 0; i < x; i++){ 
        if(!Stk.empty()){      
            int top = Stk.top();   
            while(top == end + 1){ 
                end = end + 1;   
                Stk.pop();   
                if(Stk.empty()){ 
                    break; 
                }   
                top = Stk.top(); 
            }   
            if(Stk.empty()) { 
                Stk.push(arr[i]); 
            } 
            
            else{ 
                top = Stk.top();   
                if(arr[i] < top){ 
                    Stk.push(arr[i]); 
                } 
                else{ 
                    return false; 
                } 
            } 
        } 
        else{ 
            Stk.push(arr[i]); 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    int a[] = {4,1,2,3}; 
    int n = sizeof(a) / sizeof(a[0]);
    
    check(a, n)? cout<<"array is stack sortable": cout<<"array is not stack sortable";    
    
    return 0; 
}
You can also try this code with Online C++ Compiler
Run Code

 

Input: 4,1,2,3

Output:

array is stack sortable

Algorithm Complexity

Let's see the complexity of the code.

Time Complexity

 O(n) because we traverse all the nodes. Here n is the number of nodes in a given binary tree.

Space Complexity

The space complexity of a skewed tree is O(n), while the call stack of a balanced tree consumes O(log n) space (i.e., the height of the balanced tree).

Frequently Asked Questions

What sorting algorithm does sort function in C++ use? 

C++ uses a merge sort algorithm in its Inbuilt sort function.

What's the difference between a queue and a stack?

The main difference between Stack and Queue Data Structures is that Stack uses a LIFO data structure type, whereas Queue uses a FIFO data structure type. Last In First Out (LIFO) is a term that relates to the order in which things are done. When we add data to a Stack, the last entry is processed first. FIFO, on the other hand, is a term that stands for "First In, First Out."

Stack is a recursive data structure, Why?  

A stack is a recursive data structure; it's either empty or made up of a top and the remainder, a stack in and of itself. 

What is an example of a stack in real life?

We use the concept of LIFO/stack in our daily activities such as in a cafeteria, a stack of trays; In a cabinet, a stack of plates; In a classroom; a stack of books.

Conclusion

In this article, we have extensively discussed if an array is stack sortable. We started with the introduction of the problem, the problem statement of if an array is stack sortable, the example of the problem, the algorithm, and finally concluded with the implementation of the same.

After reading about if an array is a stack sortable or not, are you not feeling excited to read/explore more articles on the topic of binary trees? Don't worry; Coding Ninjas has you covered. To learn, see the Introduction to stackReverse an array using Stack and Recursion and stack

Recommended Problems:

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your capacity in coding, you may check out the mock test series and participate in the contests hosted on the Coding Ninjas Studio website. But if you have just started learning and are looking for questions asked by tech giants like Amazon, Microsoft, Google, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

 You may also consider our paid courses to give your career an edge over others!

 Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Conclusion Image

Live masterclass