k stacks in an array

Solutions on MaxInterview for k stacks in an array by the best coders in the world

showing results for - "k stacks in an array"
Luigi
29 May 2019
1//Program in C++ to implement k stacks in an array
2
3#include <iostream>
4using namespace std;
5
6class kstack{
7  int *s; //stack
8  int *index; //prev occupied and next available indexes of stack
9  int *top_of_stack; //top of every stack
10  int next_available; //next available index
11  
12  public:
13  //initialize every value
14  kstack(int capacity,int number_of_stacks){
15      s = new int[capacity];
16      index = new int[capacity];
17      top_of_stack = new int[number_of_stacks];
18      next_available = 0;
19      
20      for(int i=0;i<capacity;i++)
21          index[i] = (i != capacity-1)?i+1 : -1;
22      
23      for(int i=0;i<number_of_stacks;i++)
24          top_of_stack[i] = -1;
25  }
26  
27  void push(int,int); //push given element to given stack no.
28  void pop(int); //pop an element from given stack no.
29};
30
31void kstack::push(int stack_num,int value){
32    if(next_available == -1){
33        cout<<"All Stacks overflowed\n";
34        return;
35    }
36    
37    int free_index = index[next_available];
38    
39    //set new value
40    s[next_available] = value;
41    
42    //set prev index for current stack's top index
43    index[next_available] = top_of_stack[stack_num];
44    
45    //set top of stack to curr index
46    top_of_stack[stack_num] = next_available;
47    
48    //set next next_available to next free index
49    next_available = free_index;
50    
51    cout<<"Element pushed successfully\n";
52}
53
54void kstack::pop(int stack_num){
55    int top_index = top_of_stack[stack_num];
56    
57    if(top_index == -1) 
58        cout<<"Stack "<<stack_num<<" is empty!\n";
59    
60    int top_element = s[top_of_stack[stack_num]];
61    cout<<top_element<<" poped\n";
62    
63    //set top of stack to prev top of stack
64    top_of_stack[stack_num] = index[top_index];
65    
66    //set index to point to next available index
67    index[top_index] = next_available;
68    
69    //set next available to current poped index
70    next_available = top_index;
71}
72
73int main() {
74    //instantiate kstack
75	kstack s(6,3);
76	//push elements to respective given stack
77	s.push(0,2);
78	s.push(0,15);
79	s.push(2,10);
80	s.push(1,4);
81	s.pop(0);
82	s.push(2,3);
83	s.pop(2);
84	s.push(2,5);
85	s.push(2,6);
86	s.push(3,7);
87	s.push(2,8); //whole stack array is full at this point
88	return 0;
89}