Рубрики

Как эффективно реализовать k стеков в одном массиве?

Мы обсудили эффективное использование двух стеков в одном массиве . В этом посте обсуждается общее решение для k стеков. Ниже приводится подробное изложение проблемы.

Создайте структуру данных kStacks, которая представляет k стеков. Реализация kStacks должна использовать только один массив, т. Е. K стеков должен использовать один и тот же массив для хранения элементов. Следующие функции должны поддерживаться kStacks.

push (int x, int sn) -> толкает x к номеру стека 'sn', где sn от 0 до k-1
pop (int sn) -> выталкивает элемент из стека с номером sn, где sn от 0 до k-1

Способ 1 (разделить массив на слоты размером н / к)
Простой способ реализовать k стеков — это разделить массив на k слотов размером n / k каждый и зафиксировать слоты для разных стеков, т. Е. Использовать arr [0] для arr [n / k-1] для первого стека, и от arr [n / k] до arr [2n / k-1] для stack2, где arr [] — это массив, который будет использоваться для реализации двух стеков, а размер массива равен n.

Проблема с этим методом — неэффективное использование пространства массива. Операция проталкивания стека может привести к переполнению стека, даже если в arr [] есть свободное место. Например, допустим, что k равно 2, а размер массива (n) равен 6, и мы помещаем 3 элемента в первый и ничего не помещаем во второй второй стек. Когда мы переместим 4-й элемент к первому, произойдет переполнение, даже если у нас есть место для еще 3 элементов в массиве.

Метод 2 (Пространственно эффективная реализация)
Идея состоит в том, чтобы использовать два дополнительных массива для эффективной реализации k стеков в массиве. Это может не иметь большого смысла для целочисленных стеков, но элементы стеков могут быть большими, например стеки сотрудников, студентов и т. Д., Где каждый элемент имеет сотни байтов. Для таких больших стеков используемое дополнительное пространство сравнительно очень мало, поскольку в качестве дополнительного пространства мы используем два целочисленных массива.

Ниже приведены два дополнительных массива:
1) top []: имеет размер k и хранит индексы верхних элементов во всех стеках.
2) next []: имеет размер n и хранит индексы следующего элемента для элементов в массиве arr []. Здесь arr [] фактический массив, который хранит k стеков.
Вместе с k стеками также поддерживается стек свободных слотов в arr []. Вершина этого стека хранится в переменной «free».

Все записи в top [] инициализируются как -1, чтобы указать, что все стеки пусты. Все записи next [i] инициализируются как i + 1, потому что все слоты изначально свободны и указывают на следующий слот. Вершина свободного стека, 'free' инициализируется как 0.

Ниже приводится реализация вышеуказанной идеи.

C ++

// Программа на C ++ для демонстрации реализации k стеков в одном
// массив во времени и пространстве эффективным способом
#include<iostream>
#include<climits>

using namespace std;

  
// Класс C ++ для представления k стеков в одном массиве размером n

class kStacks

{

    int *arr;   // Массив размера n для хранения фактического контента, который будет храниться в стеках

    int *top;   // Массив размера k для хранения индексов верхних элементов стеков

    int *next;  // Массив размера n для хранения следующей записи во всех стеках

                // и свободный список

    int n, k;

    int free; // Хранить начальный индекс свободного списка

public:

    // конструктор для создания k стеков в массиве размером n

    kStacks(int k, int n);

  

    // Утилита для проверки наличия свободного места

    bool isFull()   {  return (free == -1);  }

  

    // Вставить элемент в стеке 'sn', где sn от 0 до k-1

    void push(int item, int sn);

  

    // Для извлечения из номера стека 'sn', где sn от 0 до k-1

    int pop(int sn);

  

    // Проверить, является ли номер стека 'sn' пустым или нет

    bool isEmpty(int sn)  {  return (top[sn] == -1); }

};

  
// конструктор для создания k стеков в массиве размером n

kStacks::kStacks(int k1, int n1)

{

    // Инициализируем n и k и выделяем память для всех массивов

    k = k1, n = n1;

    arr = new int[n];

    top = new int[k];

    next = new int[n];

  

    // Инициализируем все стеки как пустые

    for (int i = 0; i < k; i++)

        top[i] = -1;

  

    // Инициализируем все пробелы как свободные

    free = 0;

    for (int i=0; i<n-1; i++)

        next[i] = i+1;

    next[n-1] = -1;  // -1 используется для обозначения конца свободного списка

}

  
// Вставить элемент в стеке 'sn', где sn от 0 до k-1

void kStacks::push(int item, int sn)

{

    // Проверка переполнения

    if (isFull())

    {

        cout << "\nStack Overflow\n";

        return;

    }

  

    int i = free;      // Сохраняем индекс первого свободного слота

  

    // Обновление индекса свободного слота до индекса следующего слота в свободном списке

    free = next[i];

  

    // Обновляем следующий из top, а затем top для номера стека 'sn'

    next[i] = top[sn];

    top[sn] = i;

  

    // Поместить элемент в массив

    arr[i] = item;

}

  
// Для извлечения из номера стека 'sn', где sn от 0 до k-1

int kStacks::pop(int sn)

{

    // Проверка недостаточности

    if (isEmpty(sn))

    {

         cout << "\nStack Underflow\n";

         return INT_MAX;

    }

  

  

    // Находим индекс верхнего элемента в стеке 'sn'

    int i = top[sn];

  

    top[sn] = next[i];  // Изменить вершину, чтобы сохранить следующую предыдущую вершину

  

    // Прикрепляем предыдущую вершину к началу свободного списка

    next[i] = free;

    free = i;

  

    // Возвращаем предыдущий верхний элемент

    return arr[i];

}

  
/ * Программа драйвера для тестирования класса twStacks * /

int main()

{

    // Давайте создадим 3 стека в массиве размером 10

    int k = 3, n = 10;

    kStacks ks(k, n);

  

    // Давайте поместим некоторые элементы в стек № 2

    ks.push(15, 2);

    ks.push(45, 2);

  

    // Давайте поместим некоторые элементы в стек № 1

    ks.push(17, 1);

    ks.push(49, 1);

    ks.push(39, 1);

  

    // Давайте поместим некоторые элементы в стек № 0

    ks.push(11, 0);

    ks.push(9, 0);

    ks.push(7, 0);

  

    cout << "Popped element from stack 2 is " << ks.pop(2) << endl;

    cout << "Popped element from stack 1 is " << ks.pop(1) << endl;

    cout << "Popped element from stack 0 is " << ks.pop(0) << endl;

  

    return 0;

}

Джава

// Java-программа для демонстрации реализации k стеков в одном
// массив во времени и пространстве эффективным способом

  

public class GFG 

{

    // Java-класс для представления k стеков в одном массиве размером n

    static class KStack 

    {

        int arr[];   // Массив размера n для хранения фактического контента, который будет храниться в стеках

        int top[];   // Массив размера k для хранения индексов верхних элементов стеков

        int next[];  // Массив размера n для хранения следующей записи во всех стеках

                     // и свободный список

        int n, k;

        int free; // Хранить начальный индекс свободного списка

  

        // конструктор для создания k стеков в массиве размером n

        KStack(int k1, int n1) 

        {

            // Инициализируем n и k и выделяем память для всех массивов

            k = k1;

            n = n1;

            arr = new int[n];

            top = new int[k];

            next = new int[n];

  

            // Инициализируем все стеки как пустые

            for (int i = 0; i < k; i++)

                top[i] = -1;

  

            // Инициализируем все пробелы как свободные

            free = 0;

            for (int i = 0; i < n - 1; i++)

                next[i] = i + 1;

            next[n - 1] = -1; // -1 используется для обозначения конца свободного списка

        }

  

        // Утилита для проверки наличия свободного места

        boolean isFull() 

        {

            return (free == -1);

        }

  

        // Вставить элемент в стеке 'sn', где sn от 0 до k-1

        void push(int item, int sn) 

        {

            // Проверка переполнения

            if (isFull()) 

            {

                System.out.println("Stack Overflow");

                return;

            }

  

            int i = free; // Сохраняем индекс первого свободного слота

  

            // Обновление индекса свободного слота до индекса следующего слота в свободном списке

            free = next[i];

  

            // Обновляем следующий из top, а затем top для номера стека 'sn'

            next[i] = top[sn];

            top[sn] = i;

  

            // Поместить элемент в массив

            arr[i] = item;

        }

  

        // Для извлечения из номера стека 'sn', где sn от 0 до k-1

        int pop(int sn) 

        {

            // Проверка недостаточности

            if (isEmpty(sn)) 

            {

                System.out.println("Stack Underflow");

                return Integer.MAX_VALUE;

            }

  

            // Находим индекс верхнего элемента в стеке 'sn'

            int i = top[sn];

  

            top[sn] = next[i]; // Изменить вершину, чтобы сохранить следующую предыдущую вершину

  

            // Прикрепляем предыдущую вершину к началу свободного списка

            next[i] = free;

            free = i;

  

            // Возвращаем предыдущий верхний элемент

            return arr[i];

        }

  

        // Проверить, является ли номер стека 'sn' пустым или нет

        boolean isEmpty(int sn) 

        {

            return (top[sn] == -1);

        }

  

    }

  

    // Драйвер программы

    public static void main(String[] args) 

    {

        // Давайте создадим 3 стека в массиве размером 10

        int k = 3, n = 10;

          

        KStack ks = new KStack(k, n);

  

        ks.push(15, 2);

        ks.push(45, 2);

  

        // Давайте поместим некоторые элементы в стек № 1

        ks.push(17, 1);

        ks.push(49, 1);

        ks.push(39, 1);

  

        // Давайте поместим некоторые элементы в стек № 0

        ks.push(11, 0);

        ks.push(9, 0);

        ks.push(7, 0);

  

        System.out.println("Popped element from stack 2 is " + ks.pop(2));

        System.out.println("Popped element from stack 1 is " + ks.pop(1));

        System.out.println("Popped element from stack 0 is " + ks.pop(0));

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Программа Python 3 для демонстрации реализации
Количество k стеков в одном массиве во времени и пространстве
# эффективный способ

class KStacks:

      

    def __init__(self, k, n):

        self.k = k # Количество стеков.

        self.n = n # Общий размер удержания массива

                   # все стеки 'k'.

  

        # Массив, содержащий стеки 'k'.

        self.arr = [0] * self.n

  

        # Все стеки пусты для начала

        # (-1 означает, что стек пуст).

        self.top = [-1] * self.k

  

        # Вершина свободного стека.

        self.free = 0

  

        # Указывает на следующий элемент в любом

        # 1. Один из стеков 'k' или,

        # 2. «Свободный» стек.

        self.next = [i + 1 for i in range(self.n)]

        self.next[self.n - 1] = -1

  

    # Проверить, пуст ли данный стек.

    def isEmpty(self, sn):

        return self.top[sn] == -1

  

    # Проверьте, осталось ли место для

    # толкаем новые элементы или нет.

    def isFull(self):

        return self.free == -1

  

    # Вставьте 'item' в заданный номер стека 'sn'.

    def push(self, item, sn):

        if self.isFull():

            print("Stack Overflow")

            return

  

        # Получить первую свободную позицию

        # для вставки в.

        insert_at = self.free

  

        # Отрегулируйте свободное положение.

        self.free = self.next[self.free]

  

        # Вставьте товар на бесплатную

        # позиция, которую мы получили выше.

        self.arr[insert_at] = item

  

        # Отрегулируйте рядом, чтобы указать на старый

        # вершина стекового элемента.

        self.next[insert_at] = self.top[sn]

  

        # Установите новую вершину стека.

        self.top[sn] = insert_at

  

    # Выгрузить элемент из заданного номера стека 'sn'.

    def pop(self, sn):

        if self.isEmpty(sn):

            return None

  

        # Получить предмет на вершине стека.

        top_of_stack = self.top[sn]

  

        # Установить новую вершину стека.

        self.top[sn] = self.next[self.top[sn]]

  

        # Вставьте старый top_of_stack в

        # «свободный» стек.

        self.next[top_of_stack] = self.free

        self.free = top_of_stack

  

        return self.arr[top_of_stack]

  

    def printstack(self, sn):

        top_index = self.top[sn]

        while (top_index != -1):

            print(self.arr[top_index])

            top_index = self.next[top_index]

  
Код водителя

if __name__ == "__main__":

      

    # Создайте 3 стека, используя

    # массив размером 10.

    kstacks = KStacks(3, 10)

  

    # Поместите некоторые предметы в стек № 2.

    kstacks.push(15, 2)

    kstacks.push(45, 2)

  

    # Поместите некоторые предметы в стек № 1.

    kstacks.push(17, 1)

    kstacks.push(49, 1)

    kstacks.push(39, 1)

  

    # Поместить некоторые предметы в стек № 0.

    kstacks.push(11, 0)

    kstacks.push(9, 0)

    kstacks.push(7, 0)

  

    print("Popped element from stack 2 is " + 

                         str(kstacks.pop(2)))

    print("Popped element from stack 1 is " + 

                         str(kstacks.pop(1)))

    print("Popped element from stack 0 is " + 

                         str(kstacks.pop(0)))

  

    kstacks.printstack(0)

  
# Этот код предоставлен Варуном Патилом

C #

using System;

  
// C # программа для демонстрации реализации k стеков в одном
// массив во времени и пространстве эффективным способом

  

public class GFG

{

    // C # класс для представления k стеков в одном массиве размером n

    public class KStack

    {

        public int[] arr; // Массив размера n для хранения фактического контента, который будет храниться в стеках

        public int[] top; // Массив размера k для хранения индексов верхних элементов стеков

        public int[] next; // Массив размера n для хранения следующей записи во всех стеках

                     // и свободный список

        public int n, k;

        public int free; // Хранить начальный индекс свободного списка

  

        // конструктор для создания k стеков в массиве размером n

        public KStack(int k1, int n1)

        {

            // Инициализируем n и k и выделяем память для всех массивов

            k = k1;

            n = n1;

            arr = new int[n];

            top = new int[k];

            next = new int[n];

  

            // Инициализируем все стеки как пустые

            for (int i = 0; i < k; i++)

            {

                top[i] = -1;

            }

  

            // Инициализируем все пробелы как свободные

            free = 0;

            for (int i = 0; i < n - 1; i++)

            {

                next[i] = i + 1;

            }

            next[n - 1] = -1; // -1 используется для обозначения конца свободного списка

        }

  

        // Утилита для проверки наличия свободного места

        public virtual bool Full

        {

            get

            {

                return (free == -1);

            }

        }

  

        // Вставить элемент в стеке 'sn', где sn от 0 до k-1

        public virtual void push(int item, int sn)

        {

            // Проверка переполнения

            if (Full)

            {

                Console.WriteLine("Stack Overflow");

                return;

            }

  

            int i = free; // Сохраняем индекс первого свободного слота

  

            // Обновление индекса свободного слота до индекса следующего слота в свободном списке

            free = next[i];

  

            // Обновляем следующий из top, а затем top для номера стека 'sn'

            next[i] = top[sn];

            top[sn] = i;

  

            // Поместить элемент в массив

            arr[i] = item;

        }

  

        // Для извлечения из номера стека 'sn', где sn от 0 до k-1

        public virtual int pop(int sn)

        {

            // Проверка недостаточности

            if (isEmpty(sn))

            {

                Console.WriteLine("Stack Underflow");

                return int.MaxValue;

            }

  

            // Находим индекс верхнего элемента в стеке 'sn'

            int i = top[sn];

  

            top[sn] = next[i]; // Изменить вершину, чтобы сохранить следующую предыдущую вершину

  

            // Прикрепляем предыдущую вершину к началу свободного списка

            next[i] = free;

            free = i;

  

            // Возвращаем предыдущий верхний элемент

            return arr[i];

        }

  

        // Проверить, является ли номер стека 'sn' пустым или нет

        public virtual bool isEmpty(int sn)

        {

            return (top[sn] == -1);

        }

  

    }

  

    // Драйвер программы

    public static void Main(string[] args)

    {

        // Давайте создадим 3 стека в массиве размером 10

        int k = 3, n = 10;

  

        KStack ks = new KStack(k, n);

  

        ks.push(15, 2);

        ks.push(45, 2);

  

        // Давайте поместим некоторые элементы в стек № 1

        ks.push(17, 1);

        ks.push(49, 1);

        ks.push(39, 1);

  

        // Давайте поместим некоторые элементы в стек № 0

        ks.push(11, 0);

        ks.push(9, 0);

        ks.push(7, 0);

  

        Console.WriteLine("Popped element from stack 2 is " + ks.pop(2));

        Console.WriteLine("Popped element from stack 1 is " + ks.pop(1));

        Console.WriteLine("Popped element from stack 0 is " + ks.pop(0));

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

Popped element from stack 2 is 45
Popped element from stack 1 is 39
Popped element from stack 0 is 7

Временные сложности операций push () и pop () составляют O (1).

Лучшая часть описанной выше реализации состоит в том, что если в стеке имеется слот, то элемент может быть помещен в любой из стеков, т. Е. Не теряется место.

Эта статья предоставлена Sachin . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Как эффективно реализовать k стеков в одном массиве?

0.00 (0%) 0 votes