ימפּלעמענט צוויי סטאַקס אין אַ עריי  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין 24 * 7 יננאָוואַטיאָן לאַבס אַקקאָליטע גוגל מייקראָסאָפֿט סאַמסונג סנאַפּדעאַל
מענגע אָנלייגן

פּראָבלעם סטאַטעמענט  

אין די "ימפּלעמענט צוויי סטאַקס אין אַ עריי" פּראָבלעם מיר האָבן צו ינסטרומענט צוויי סטאַקס אין אַ מענגע אַזאַ, אויב דער באַניצער וויל צו שטופּן אַן עלעמענט אין צוויי סטאַקס, עס זאָל נישט זיין אַ טעות ביז די מענגע איז פול.

בייַשפּיל  

Push 5 into stack1.
Push 10 into stack2.
Push 15 into stack2.
Push 11 into stack1.
Push 7 into stack2.
Popped element from stack1. 
Push 40 into stack2.
Popped element from stack2.
Stack Overflow By element: 7
Popped element from stack1 is: 11
Stack Overflow By element: 40
Popped element from stack2 is: 15

אַלגאָריטהם  

דער געדאַנק איז צו אָנהייבן צוויי סטאַקס פון די עקסטרעם עקן פון די מענגע. ביידע די סטאַקס וועט וואַקסן איינער צו דעם אנדערן, סטאַק 1 וועט אָנהייבן פֿון די לינקס ווינקל און סטאַק 2 וועט אָנהייבן פֿון די רעכט רעכט ווינקל פון די מענגע.

1. סטאַק 1 וועט אָנהייבן פֿון אינדעקס 0 און וואַקסן צו די רעכט סוף פון די מענגע

2. סטאַק 2 וועט אָנהייבן פֿון אינדעקס N-1 און וואַקסן צו די לינקס סוף פון די מענגע

3. ווען ביידע סטאַקס טרעפן יעדער אנדערע, מיר קענען נישט שטופּן אַן עלעמענט אין ביידע סטאַקס

מיר נוצן שטופּן, קנאַל פאַנגקשאַנז צו שטופּן עלעמענטן אין ביידע סטאַקס

1. פּוש פונקציע וועט נעמען דעם אָנלייגן נאָמען און ווערט צו זיין ינסערטאַד און פּושיז די נומער אין די ריספּעקטיוו אָנלייגן

זע אויך
קאָקאָ עטינג באַנאַנאַס לעעטקאָדע סאַלושאַן

אַ. לויט דעם אָנלייגן נאָמען גיינ ווייַטער

ב. קאָנטראָלירן צי דער אָנלייגן איז פול אָדער נישט הייסט, טאָפּ 1 <טאָפּ 2 -1 דאָ, טאָפּ 1, טאָפּ 2 זענען די וועריאַבאַלז
צו האַלטן שפּור פון שפּיץ עלעמענטן אין ביידע סטאַקס

ג. אויב נישט, שטופּן דעם עלעמענט אין די ריספּעקטיוו אָנלייגן, דהיינו, אַרר [טאָפּ 1] = ק

2. קנאַל וועט נעמען דעם אָנלייגן נאָמען און פּאָפּ די שפּיץמאָסט עלעמענט אין דעם אָנלייגן

אַ. לויט דעם אָנלייגן נאָמען גיינ ווייַטער

ב. קאָנטראָלירן צי עס איז קיין עלעמענט צו קנאַל

ג. אויב יאָ, דעקראַמענט אָדער ינקראַמאַנט די טאָפּ 1, טאָפּ 2 וועריאַבאַלז אַקאָרדינגלי

ימפּלעמענטאַטיאָן  

C ++ פּראָגראַם צו ימפּלאַמענטאַד צוויי סטאַקס אין אַ עריי

#include <bits/stdc++.h>
using namespace std;

class twoStacks 
{
  int* arr;
  int size;
  int top1, top2;

public:
  twoStacks(int n)
  {
    size = n;
    arr = new int[n];
    top1 = n / 2 + 1;
    top2 = n / 2;
  }
  void push1(int x)
  {
    if (top1 > 0) {
      top1--;
      arr[top1] = x;
    }
    else {
      cout << "Stack Overflow"
        << " By element :" << x << endl;
      return;
    }
  }
  void push2(int x)
  {
    if (top2 < size - 1) {
      top2++;
      arr[top2] = x;
    }
    else {
      cout << "Stack Overflow"
        << " By element : " << x << endl;
      return;
    }
  }
  int pop1()
  {
    if (top1 <= size / 2) {
      int x = arr[top1];
      top1++;
      return x;
    }
    else {
      cout << "Stack UnderFlow";
      exit(1);
    }
  }
  int pop2()
  {
    if (top2 >= size / 2 + 1) {
      int x = arr[top2];
      top2--;
      return x;
    }
    else {
      cout << "Stack UnderFlow";
      exit(1);
    }
  }
};

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()<< endl;
  ts.push2(40);
  cout << "Popped element from stack2 is "<< " : " << ts.pop2()<< endl;
  return 0;
}

Java פּראָגראַם צו ימפּלאַמענטאַד צוויי סטאַקס אין אַ עריי

import java.util.Scanner;
class twoStacks
{
  int[] arr;
  int size;
  int top1, top2;
  twoStacks(int n)
  {
    size = n;
    arr = new int[n];
    top1 = n / 2 + 1;
    top2 = n / 2;
  }
  void push1(int x)
  {
    if (top1 > 0)
    {
      top1--;
      arr[top1] = x;
    }
    else
    {
      System.out.print("Stack Overflow"+ " By element :" +  x +"\n");
      return;
    }
  }
  void push2(int x)
  {
    if (top2 < size - 1)
    {
      top2++;
      arr[top2] = x;
    }
    else
    {
      System.out.print("Stack Overflow"+ " By element : " +  x +"\n");
      return;
    }
  }
 
  // Method to pop an element from first stack
  int pop1()
  {
    if (top1 <= size / 2)
    {
      int x = arr[top1];
      top1++;
      return x;
    }
    else
    {
      System.out.print("Stack UnderFlow");
      System.exit(1);
    }
    return 0;
  }
 
  // Method to pop an element
  // from second stack
  int pop2()
  {
    if (top2 >= size / 2 + 1)
    {
      int x = arr[top2];
      top2--;
      return x;
    }
    else
    {
      System.out.print("Stack UnderFlow");
      System.exit(1);
    }
    return 1;
  }
};
class sum
{
    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.print("Popped element from stack1 is "+ " : " +  ts.pop1() +"\n");
        ts.push2(40);
        System.out.print("Popped element from stack2 is "+ ": " +  ts.pop2()+"\n");
    }
}
Stack Overflow By element :7
Popped element from stack1 is  : 11
Stack Overflow By element : 40
Popped element from stack2 is : 15

קאַמפּלעקסיטי אַנאַליסיס צו ימפּלאַמענטאַד צוויי סטאַקס אין אַ עריי  

צייט קאַמפּלעקסיטי

  • שטופּן אָפּעראַציע: אָ (1) ווייַל מיר שטופּן גלייַך אַ גאַנץ נומער אין די סוף פון די אָנלייגן.
  • קנאַל אָפּעראַציע: אָ (1) ווייַל מיר גלייַך באַזייַטיקן די לעצטע ווערט אָדער די שפּיץ ווערט פון דעם אָנלייגן.
זע אויך
קאָמבינאַציע סאַם

ספעיס קאַמפּלעקסיטי

אָ (N) ווייַל מיר נוצן אַ מענגע צו ינסטרומענט דעם אָנלייגן. עס איז נישט די פּלאַץ-אָפּטימיזעד אופֿן ווי אויבן דערקלערט.