Рубрики

Реализуйте два стека в массиве

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

push1 (int x) -> помещает x в первый стек
push2 (int x) -> помещает x во второй стек

pop1 () -> выталкивает элемент из первого стека и возвращает извлеченный элемент
pop2 () -> извлекает элемент из второго стека и возвращает извлеченный элемент

Реализация twoStack должна быть экономичной.

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

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

Метод 2 (Пространственно эффективная реализация)
Этот метод эффективно использует доступное пространство. Это не вызывает переполнение, если в arr [] есть свободное место. Идея состоит в том, чтобы начать два стека из двух крайних углов arr []. stack1 начинается с самого левого элемента, первый элемент в stack1 помещается с индексом 0. Stack2 начинается с самого правого угла, первый элемент в stack2 помещается с индексом (n-1). Оба стека растут (или сжимаются) в противоположном направлении. Чтобы проверить переполнение, все, что нам нужно проверить — это пространство между верхними элементами обоих стеков. Эта проверка выделена в приведенном ниже коде.

C ++

#include<iostream>
#include<stdlib.h>

  

using namespace std;

  

class twoStacks

{

    int *arr;

    int size;

    int top1, top2;

public:

   twoStacks(int n)  // конструктор

   {

       size = n;

       arr = new int[n];

       top1 = -1;

       top2 = size;

   }

  

   // Метод для перемещения элемента x в stack1

   void push1(int x)

   {

       // Для нового элемента есть хотя бы одно пустое место

       if (top1 < top2 - 1)

       {

           top1++;

           arr[top1] = x;

       }

       else

       {

           cout << "Stack Overflow";

           exit(1);

       }

   }

  

   // Метод для перемещения элемента x в stack2

   void push2(int x)

   {

       // Для нового элемента есть хотя бы одно пустое место

       if (top1 < top2 - 1)

       {

           top2--;

           arr[top2] = x;

       }

       else

       {

           cout << "Stack Overflow";

           exit(1);

       }

   }

  

   // Метод для извлечения элемента из первого стека

   int pop1()

   {

       if (top1 >= 0 )

       {

          int x = arr[top1];

          top1--;

          return x;

       }

       else

       {

           cout << "Stack UnderFlow";

           exit(1);

       }

   }

  

   // Метод для извлечения элемента из второго стека

   int pop2()

   {

       if (top2 < size)

       {

          int x = arr[top2];

          top2++;

          return x;

       }

       else

       {

           cout << "Stack UnderFlow";

           exit(1);

       }

   }

};

  

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

int main()

{

    twoStacks ts(5);

    ts.push1(5);

    ts.push2(10);

    ts.push2(15);

    ts.push1(11);

    ts.push2(7);

    cout << "Popped element from stack1 is " << ts.pop1();

    ts.push2(40);

    cout << "\nPopped element from stack2 is " << ts.pop2();

    return 0;

}

Джава

// Java-программа для реализации двух стеков в
// один массив

class TwoStacks

{

    int size;

    int top1, top2;

    int arr[];

  

    // Конструктор

    TwoStacks(int n)

    {

        arr = new int[n];

        size = n;

        top1 = -1;

        top2 = size;

    }

  

    // Метод для перемещения элемента x в stack1

    void push1(int x)

    {

        // Есть хотя бы одно пустое место для

        // новый элемент

        if (top1 < top2 - 1)

        {

            top1++;

            arr[top1] = x;

        }

        else

        {

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

            System.exit(1);

        }

    }

  

    // Метод для перемещения элемента x в stack2

    void push2(int x)

    {

        // Есть хотя бы одно пустое место для

        // новый элемент

        if (top1 < top2 -1)

        {

            top2--;

            arr[top2] = x;

        }

        else

        {

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

            System.exit(1);

        }

    }

  

    // Метод для извлечения элемента из первого стека

    int pop1()

    {

        if (top1 >= 0)

        {

            int x = arr[top1];

            top1--;

            return x;

        }

        else

        {

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

            System.exit(1);

        }

        return 0;

    }

  

    // Метод для извлечения элемента из второго стека

    int pop2()

    {

        if(top2 < size)

        {

            int x =arr[top2];

            top2++;

            return x;

        }

        else

        {

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

            System.exit(1);

  

        }

        return 0;

    }

  

    // Драйвер для тестирования класса twoStack

    public static void main(String args[])

    {

        TwoStacks ts = new TwoStacks(5);

        ts.push1(5);

        ts.push2(10);

        ts.push2(15);

        ts.push1(11);

        ts.push2(7);

        System.out.println("Popped element from" +

                           " stack1 is " + ts.pop1());

        ts.push2(40);

        System.out.println("Popped element from" +

                         " stack2 is " + ts.pop2());

    }

}
// Этот код был добавлен
// Амит Хандельвал (Amit Khandelwal 1).

питон

# Python Script для реализации двух стеков в списке

class twoStacks:

      

    def __init__(self, n):     #конструктор

        self.size = n

        self.arr = [None] * n

        self.top1 = -1

        self.top2 = self.size

          

    # Метод, чтобы поместить элемент x в stack1

    def push1(self, x):

          

        # Есть как минимум одно пустое место для нового элемента

        if self.top1 < self.top2 - 1 :

            self.top1 = self.top1 + 1

            self.arr[self.top1] = x

  

        else:

            print("Stack Overflow ")

            exit(1)

  

    # Метод, чтобы поместить элемент x в stack2

    def push2(self, x):

  

        # Есть как минимум одно пустое место для нового элемента

        if self.top1 < self.top2 - 1:

            self.top2 = self.top2 - 1

            self.arr[self.top2] = x

  

        else :

           print("Stack Overflow ")

           exit(1)

  

    # Метод извлечения элемента из первого стека

    def pop1(self):

        if self.top1 >= 0:

            x = self.arr[self.top1]

            self.top1 = self.top1 -1

            return x

        else:

            print("Stack Underflow ")

            exit(1)

  

    # Метод для извлечения элемента из второго стека

    def pop2(self):

        if self.top2 < self.size:

            x = self.arr[self.top2]

            self.top2 = self.top2 + 1

            return x

        else:

            print("Stack Underflow ")

            exit()

  
# Драйверная программа для тестирования класса twoStacks

ts = twoStacks(5)

ts.push1(5)

ts.push2(10)

ts.push2(15)

ts.push1(11)

ts.push2(7)

  

print("Popped element from stack1 is " + str(ts.pop1()))

ts.push2(40)

print("Popped element from stack2 is " + str(ts.pop2()))

  
# Этот код предоставлен Sunny Karira

C #

// C # программа для реализации двух
// стеки в одном массиве

using System;

  

public class TwoStacks

{

public int size;

public int top1, top2;

public int[] arr;

  
// Конструктор

public TwoStacks(int n)

{

    arr = new int[n];

    size = n;

    top1 = -1;

    top2 = size;

}

  
// Метод для перемещения элемента x в stack1

public virtual void push1(int x)

{

    // есть хотя бы один пустой

    // место для нового элемента

    if (top1 < top2 - 1)

    {

        top1++;

        arr[top1] = x;

    }

    else

    {

        Console.WriteLine("Stack Overflow");

        Environment.Exit(1);

    }

}

  
// Метод для перемещения элемента x в stack2

public virtual void push2(int x)

{

    // есть хотя бы один пустой

    // место для нового элемента

    if (top1 < top2 - 1)

    {

        top2--;

        arr[top2] = x;

    }

    else

    {

        Console.WriteLine("Stack Overflow");

        Environment.Exit(1);

    }

}

  
// Метод для выталкивания элемента
// из первого стека

public virtual int pop1()

{

    if (top1 >= 0)

    {

        int x = arr[top1];

        top1--;

        return x;

    }

    else

    {

        Console.WriteLine("Stack Underflow");

        Environment.Exit(1);

    }

    return 0;

}

  
// Метод для выталкивания элемента
// из второго стека

public virtual int pop2()

{

    if (top2 < size)

    {

        int x = arr[top2];

        top2++;

        return x;

    }

    else

    {

        Console.WriteLine("Stack Underflow");

        Environment.Exit(1);

  

    }

    return 0;

}

  
// Код драйвера

public static void Main(string[] args)

{

    TwoStacks ts = new TwoStacks(5);

    ts.push1(5);

    ts.push2(10);

    ts.push2(15);

    ts.push1(11);

    ts.push2(7);

    Console.WriteLine("Popped element from"

                      " stack1 is " + ts.pop1());

    ts.push2(40);

    Console.WriteLine("Popped element from"

                      " stack2 is " + ts.pop2());

}
}

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

PHP

<?php
// PHP-программа для реализации двух
// стеки в одном массиве

class twoStacks 

    private $arr

    private $size

    private $top1;

    private $top2

    function __construct($n)

    {

        $this->size = $n

        $this->arr = array(); 

        $this->top1 = -1; 

        $this->top2 = $this->size; 

    }

  
// Метод для перемещения элемента x в stack1

function push1($x

    // есть хотя бы один пустой

    // место для нового элемента

    if ($this->top1 < $this->top2 - 1) 

    

        $this->top1++; 

        $this->arr[$this->top1] = $x

    

    else

    

        echo "Stack Overflow"

        exit(); 

    

  
// Метод для перемещения элемента x в stack2

function push2($x

    // есть хотя бы одно пустое место

    // для нового элемента

    if ($this->top1 < $this->top2 - 1) 

    

        $this->top2--; 

        $this->arr[$this->top2] = $x

    

    else

    

        echo "Stack Overflow"

        exit(); 

    

  
// Метод для выталкивания элемента
// из первого стека

function pop1() 

    if ($this->top1 >= 0 ) 

    

        $x = $this->arr[$this->top1]; 

        $this->top1--; 

        return $x

    

    else

    

        echo "Stack UnderFlow"

        exit(); 

    

  
// Метод для извлечения элемента из
// второй стек

function pop2() 

    if ($this->top2 < $this->size) 

    

        $x = $this->arr[$this->top2]; 

        $this->top2++; 

        return $x

    

    else

    

        echo "Stack UnderFlow"

        exit(); 

    


}; 

  

  
// Код драйвера

$ts = new twoStacks(5); 

$ts->push1(5); 

$ts->push2(10); 

$ts->push2(15); 

$ts->push1(11); 

$ts->push2(7); 

echo "Popped element from stack1 is "

                           $ts->pop1(); 

$ts->push2(40); 

echo "\nPopped element from stack2 is "

                             $ts->pop2(); 

  
// Этот код предоставлен
// ратбхупендра
?>


Выход:

  Popped element from stack1 is 11
  Popped element from stack2 is 40

Временная сложность всех 4 операций twoStack составляет O (1).
Мы расширим до 3 стеков в массиве в отдельном посте.

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

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

Реализуйте два стека в массиве

0.00 (0%) 0 votes