Проверить, попарно ли отсортированы элементы стека

Опубликовано: 24 Января, 2022

Учитывая стек целых чисел, напишите функцию pairWiseSorted (), которая проверяет, сортируются ли числа в стеке попарно или нет.
Пары должны увеличиваться, и если в стеке нечетное количество элементов, элемент наверху остается вне пары. Функция должна сохранить исходное содержимое стека.

Only following standard operations are allowed on the stack.
push(X): Enter a element X on top of stack.
pop(): Removes top element of the stack.
empty(): To check if stack is empty.

Примеры:

Ввод: 4, 5, 6, 7, 8, 9
Выход: Да

Ввод: 4, 9, 2, 1, 10, 8
Выход: Нет

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать другой стек.

Создайте вспомогательный стек aux.
Перенести содержимое данного стека в доп.
Траверс доп. При перемещении выберите два верхних элемента и проверьте, отсортированы они или нет.
После проверки верните эти элементы в исходную стопку.

Below is the implementation of above approach:

C++

// C++ program to check if successive
// pair of numbers in the stack are
// sorted or not
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if elements are
// pairwise sorted in stack
bool pairWiseConsecutive(stack<int> s)
{
    // Transfer elements of s to aux.
    stack<int> aux;
    while (!s.empty()) {
        aux.push(s.top());
        s.pop();
    }
  
    // Traverse aux and see if
    // elements are pairwise
    // sorted or not. We also
    // need to make sure that original
    // content is retained.
    bool result = true;
    while (!aux.empty()) {
  
        // Fetch current top two
        // elements of aux and check
        // if they are sorted.
        int x = aux.top();
        aux.pop();
        int y = aux.top();
        aux.pop();
        if (x > y)
            result = false;
  
        // Push the elements to original
        // stack.
        s.push(x);
        s.push(y);
    }
  
    if (aux.size() == 1)
        s.push(aux.top());
  
    return result;
}
  
// Driver program
int main()
{
    stack<int> s;
    s.push(4);
    s.push(5);
    s.push(-3);
    s.push(-2);
    s.push(10);
    s.push(11);
    s.push(5);
    s.push(6);
    // s.push(20);
  
    if (pairWiseConsecutive(s))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
  
    cout << "Stack content (from top)"
            " after function call
";
    while (s.empty() == false) {
        cout << s.top() << " ";
        s.pop();
    }
  
    return 0;
}

Java

// Java program to check if successive 
// pair of numbers in the stack are 
// sorted or not 
import java.util.Stack;
  
class GFG {
  
// Function to check if elements are 
// pairwise sorted in stack 
    static boolean pairWiseConsecutive(Stack<Integer> s) {
        // Transfer elements of s to aux. 
        Stack<Integer> aux = new Stack<>();
        while (!s.empty()) {
            aux.push(s.peek());
            s.pop();
        }
  
        // Traverse aux and see if 
        // elements are pairwise 
        // sorted or not. We also 
        // need to make sure that original 
        // content is retained. 
        boolean result = true;
        while (!aux.empty()) {
  
            // Fetch current top two 
            // elements of aux and check 
            // if they are sorted. 
            int x = aux.peek();
            aux.pop();
            int y = aux.peek();
            aux.pop();
            if (x > y) {
                result = false;
            }
  
            // Push the elements to original 
            // stack. 
            s.push(x);
            s.push(y);
        }
  
        if (aux.size() == 1) {
            s.push(aux.peek());
        }
  
        return result;
    }
  
// Driver program 
    public static void main(String[] args) {
  
        Stack<Integer> s = new Stack<>();
        s.push(4);
        s.push(5);
        s.push(-3);
        s.push(-2);
        s.push(10);
        s.push(11);
        s.push(5);
        s.push(6);
        // s.push(20); 
  
        if (pairWiseConsecutive(s)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
  
        System.out.println("Stack content (from top)"
                + " after function call");
        while (s.empty() == false) {
            System.out.print(s.peek() + " ");
            s.pop();
        }
  
    }
  
}

Python 3

# Python program to check if successive
# pair of numbers in the stack are
# sorted or not
  
# using deque as stack
from collections import deque
  
# Function to check if elements are
# pairwise sorted in stack
def pairWiseConsecutive(s):
  
    # Transfer elements of s to aux.
    aux = deque()
    while len(s) > 0:
        aux.append(s.pop())
  
    # Traverse aux and see if
    # elements are pairwise
    # sorted or not. We also
    # need to make sure that original
    # content is retained.
    result = True
    while len(aux) != 0:
  
        # Fetch current top two
        # elements of aux and check
        # if they are sorted.
        x = aux.pop()
        y = aux.pop()
        if x > y:
            result = False
  
        # Push the elements to original
        # stack.
        s.append(x)
        s.append(y)
  
    if len(aux) == 1:
        s.append(aux.pop())
  
    return result
  
  
# Driver Code
if __name__ == "__main__":
    s = deque()
    s.append(4)
    s.append(5)
    s.append(-3)
    s.append(-2)
    s.append(10)
    s.append(11)
    s.append(5)
    s.append(6)
  
    if pairWiseConsecutive(s):
        print("Yes")
    else:
        print("No")
  
    print("Stack content (from top) after function call")
    while len(s) > 0:
        print(s.pop(), end=" ")
  
# This code is contributed by
# sanjeev2552

C#

// C# program to check if successive 
// pair of numbers in the stack are 
using System;
using System.Collections.Generic;
public class GFG{
  
// Function to check if elements are 
// pairwise sorted in stack 
    static bool pairWiseConsecutive(Stack<int> s) {
        // Transfer elements of s to aux. 
        Stack<int> aux = new Stack<int>();
        while (!(s.Count==0)) {
            aux.Push(s.Peek());
            s.Pop();
        }
  
        // Traverse aux and see if 
        // elements are pairwise 
        // sorted or not. We also 
        // need to make sure that original 
        // content is retained. 
        bool result = true;
        while (!(aux.Count==0)) {
  
            // Fetch current top two 
            // elements of aux and check 
            // if they are sorted. 
            int x = aux.Peek();
            aux.Pop();
            int y = aux.Peek();
            aux.Pop();
            if (x > y) {
                result = false;
            }
  
            // Push the elements to original 
            // stack. 
            s.Push(x);
            s.Push(y);
        }
  
        if (aux.Count == 1) {
            s.Push(aux.Peek());
        }
  
        return result;
    }
  
// Driver program 
    public static void Main() {
  
        Stack<int> s = new Stack<int>();
        s.Push(4);
        s.Push(5);
        s.Push(-3);
        s.Push(-2);
        s.Push(10);
        s.Push(11);
        s.Push(5);
        s.Push(6);
        // s.push(20); 
  
        if (pairWiseConsecutive(s)) {
            Console.WriteLine("Yes");
        } else {
            Console.WriteLine("No");
        }
  
        Console.WriteLine("Stack content (from top)"
                + " after function call");
        while (!(s.Count == 0)) {
            Console.Write(s.Peek() + " ");
            s.Pop();
        }
  
    }
  
}

Output:

Yes
Stack content (from top) after function call
6 5 11 10 -2 -3 5 4

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Проверить, попарно ли отсортированы элементы стека

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

Python 3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ