DataStructureAndAlgorithms/src/datastructure/stack/program/KStacksInSingleArray.java at master · kdsalvy/DataStructureAndAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package datastructure.stack.program;

public class KStacksInSingleArray {
    static int free = 0;

    public static void main(String[] args) {
	KStacksInSingleArray stacks = new KStacksInSingleArray();
	// let n be 15 and k be 3
	int n = 15;
	int k = 3;
	int[] arr = new int[n];
	int[] top = new int[k];
	// when set it points to the prev element index and when not set it will
	// point to next available index
	int[] next = new int[n];

	for (int i = 0; i < k; i++) {
	    top[i] = -1;
	}

	for (int i = 0; i < n; i++) {
	    next[i] = i + 1;
	}
	next[n - 1] = -1;

	stacks.push(0, 1, arr, top, next);
	stacks.push(0, 2, arr, top, next);
	stacks.push(0, 3, arr, top, next);
	stacks.push(1, 2, arr, top, next);
	stacks.push(1, 3, arr, top, next);
	stacks.push(1, 4, arr, top, next);
	stacks.push(0, 4, arr, top, next);
	stacks.push(0, 5, arr, top, next);
	stacks.push(2, 3, arr, top, next);
	stacks.push(2, 4, arr, top, next);
	stacks.push(2, 5, arr, top, next);
	stacks.push(1, 5, arr, top, next);
	stacks.push(1, 6, arr, top, next);
	stacks.push(0, 6, arr, top, next);
	stacks.push(0, 1, arr, top, next);
	stacks.push(0, 2, arr, top, next);
	stacks.push(0, 3, arr, top, next);
	stacks.push(1, 2, arr, top, next);
	stacks.push(1, 3, arr, top, next);
	stacks.push(1, 4, arr, top, next);
	stacks.push(0, 4, arr, top, next);
	stacks.push(0, 5, arr, top, next);
	stacks.push(2, 3, arr, top, next);
	stacks.push(2, 4, arr, top, next);
	stacks.push(2, 5, arr, top, next);
	stacks.push(1, 5, arr, top, next);
	stacks.push(1, 6, arr, top, next);
	stacks.push(0, 6, arr, top, next);

	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(1, arr, top, next));
	System.out.println(stacks.pop(1, arr, top, next));
	System.out.println(stacks.pop(2, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(1, arr, top, next));
	System.out.println(stacks.pop(1, arr, top, next));
	System.out.println(stacks.pop(2, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(0, arr, top, next));
	System.out.println(stacks.pop(1, arr, top, next));
	System.out.println(stacks.pop(1, arr, top, next));
	System.out.println(stacks.pop(2, arr, top, next));

    }

    public int pop(int stackIndex, int[] arr, int[] top, int[] next) {
	// find the top pointer
	int curTop = top[stackIndex];
	if (curTop == -1) {
	    System.out.printf("Stack %d is empty: ", stackIndex);
	    return -1;
	}
	// get the element
	int ele = arr[curTop];
	// point the top pointer to prev element
	top[stackIndex] = next[curTop];
	// set the pointer index to next free location
	next[curTop] = free;
	// set free = curTop
	free = curTop;

	return ele;
    }

    public void push(int stackIndex, int element, int[] arr, int[] top, int[] next) {

	if (isFull(free)) {
	    System.out.println("Stack is Full");
	    return;
	}
	// store current top value in temp
	int curTop = top[stackIndex];
	// add the element to free index
	arr[free] = element;
	// update the top of stack at given index to the free index
	top[stackIndex] = free;
	// Update index of free slot to index of next slot in free list
	int prevFree = free;
	free = next[free];
	// Point the next array index to prev top of stack
	next[prevFree] = curTop;
    }

    private boolean isFull(int free) {
	return free == -1;
    }
}