Чтобы реализовать несколько стеков в одном массиве, один из подходов состоит в том, чтобы разделить массив на k слотов размером n / k каждый и исправить слоты для разных стеков, мы можем использовать arr [0] для arr [n / k-1] для первого стека и от arr [n / k] до arr [2n / k-1] для stack2 и так далее, где arr [] - это массив размера n.
Хотя этот метод прост для понимания, но проблема с этим методом заключается в неэффективном использовании пространства массива. Операция выталкивания стека может привести к переполнению стека, даже если в arr [] есть свободное место.
Examples: Input :Enter the Number of stacks Output :5 Input : 1.Push 2.pop 3.Display 4.exit Input :Enter your choice Output :1 Input :Enter the stack number Output :2 Input :Enter element to push Output :15 Input :Enter your choice Output :2 Input :Enter the stack no to pop Output :2 Output :15 from stack 2 is deleted Input: Enter your choice output: 3 output: Stack is empty Input :Enter your choice Output :4 Output :Program Terminated
Примечание
Язык программирования, используемый в статье, написан на python, чтобы понять, как все работает при построении прогнозов, необходимы некоторые базовые знания Python.
Если вы новичок в python, я бы предложил несколько из моих любимых курсов и настоял бы на прохождении этого замечательного курса DataCamp на тему Введение в Python, все должны попробовать это, все, кто плохо знаком с Python.
Если у вас есть хороший опыт работы с Python и вы хотите погрузиться в глубокое обучение или машинное обучение, всем следует пройти этот курс Введение в глубокое обучение в Python или вы можете попробовать этот новый курс на визуализации данных от Datacamp Веб-парсинг в Python, Введение в Matplotlib в Python и Анализ данных в Python, которые помогли мне много в начале моего пути в науке о данных, или вы можете пройти этот курс Advanced Deep Learning with Keras, если у вас есть хороший опыт в Data Science, попробуйте этот курс Data Scientist с Python или Ученый по машинному обучению с Python .
Кроме того, я заметил, что DataCamp дает большие скидки на некоторые курсы. Так что это буквально было бы лучшее время для получения нескольких годовых подписок (которые у меня есть), которые в основном имеют неограниченный доступ ко всем курсам и другим вещам на DataCamp, и плодотворно использовать свое время, сидя дома во время этой пандемии. Так что дерзайте, ребята, и Удачного обучения.
Алгоритм:
1. Здесь мы используем 2 массива min [] и max [] для представления нижнего
и верхние границы стека
2. В массиве s [] хранятся элементы стека.
3. Массив top [] используется для хранения верхнего индекса для каждого стека.
4. Переменная ns представляет номер стека.
5. Переменный размер представляет размер каждого стека в массиве.
6. Сначала мы создаем функцию init () для инициализации начальных значений.
7. Затем у нас есть функция createstack () для создания стека.
8. Функции Push () и Pop () используются для нажатия и выталкивания элемента в и из куча
9. Функция Display () используется для отображения элементов в определенном стеке.
Ниже представлена реализация вышеуказанного:
/*Implementation of multiple stacks in a single array @author Mrinal Walia */ #include <stdio.h> #include <stdlib.h> /* run this program using the console pauser or add your own getch, system(“pause”) or input loop */ //min represents the lower bound for a stack //max represents the upper bound for a stack int s[50],top[50],min[50],max[50]; //ns is stack number //size is size of the stack int ns,size; //function to initialize starting values of top,min,max and stack void init(void) { int i; for(i=0;i<50;++i) { s[i]=min[i]=max[i] = 0; top[i]=-1; }//end for }//end function //function to create the stack void createstack() { int i ; //min and top of 0th stack will be -1 //and it’s max will be at index one lesser than it’s size min[0]= -1; max[0] = size -1; top[0]=-1; //min and top of 1,2,3,….th stacks for(i=1;i<ns;++i) { min[i]= min[i-1] + size; top[i] = min [i]; }//end for //max of 1,2,3,….th stacks will me min of 2,3,4,….th stack for(i=1;i<ns;++i) { max[i]= min[i+1]; }//end for }//end function //function to push element to stack //parameters passed will be the item user wants to push and the stack no. to //push void push(int ele,int k) { //check for stack overflow if(top[k-1]==max[k-1]) { printf(“Stack no %d is full i.e overflow\n”,k); return; }//end if ++top[k-1]; s[top[k-1]] = ele; }//end function push //function to pop an element form stack //parameters passed is the stack no. from which we want to pop an element void pop(int k) { //check for underflow if(top[k-1]==min[k-1]) { printf(“\nStack no %d is empty i.e underflow\n”,k); return; }//end if //else delete the item printf(“%d from stack %d is deleted:\n”,s[top[k-1]],k); - -top[k-1]; }//end function pop //function to display any stack //parameter passed is the stack number to display void display(int k) { //first check for stack empty condition //variable j is used to iterate through the list int j; if(top[k-1]==min[k-1]) { printf(“\nStack no %d is empty\n”,k); return; }//end if //else display the list printf(“\nStack %d →> “,k); for(j=min[k-1]+1;j<=top[k-1];++j) { printf(“%d”,s[j] ); }//end for } //end function display //main function int main() { //variable choice,stack number and item to push is initialized int ele,ch,skn; init();//function call //input the number of stacks printf(“\nEnter the number of Stacks\n”); scanf(“%d”,&ns); //size of each stack //size = size of array/number of stacks size = 50/ns; createstack();//function call printf(“\n1.Push\n2.Pop\n3.Display\n4.Exit\n”); do{ //ask for users choice printf(“\nEnter your choice : \t”); scanf(“%d”,&ch); switch(ch) { case 1: printf(“\nEnter the stack no : \t”); scanf(“%d”,&skn); printf(“\nEnter the element : \t”); scanf(“%d”,&ele); push(ele,skn); break; case 2 : printf(“\nEnter the stack no to pop : \t”); scanf(“%d”,&skn); pop(skn); break; case 3: printf(“\nEnter the stack no to display : \t”); scanf(“%d”,&skn); display(skn); break; case 4 : printf(“\nProgram Terminating”); break; default : printf(“\nInvalid Option\n”); }//end switch }//end do-while loop while(ch!=4); return 0; }//end main
Результат:
Время сложности операций push () и pop () равно O (1)
Временная сложность функции createstack равна O (n)
Пожалуйста, напишите комментарии, если у вас есть какие-либо сомнения, или если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете более эффективные способы решения той же проблемы.
Вы можете связаться со мной по любой из приведенных ниже ссылок в моем профиле в социальных сетях -