Реализовать два стека в одном массиве

Question

Как реализовать два стека в одном массиве A [1..n] таким образом, чтобы ни один стек не переполнялся, если итоговое нет. элементов в обоих стеках вместе является n. PUSH и POP должны работать в O (1) раз?

Что не так с этим алго?

//A[1...n], top1 is pointer pointing to top of stack1. 

top1=-1; 
top2=-1; 

STACK-EMPTY(A) 

1. if(top1==0 && top2==0) 
2. return 1 
3. else 
4. return 0 

STACK-FULL(A) 

1. if(top1==S1.length && top2==S1.length) 
2.  return 1 
3. else if(top1==S1.length) 
4.  return -1 
5. else if(top2==S2.length) 
6.  return -2 
7. else 
8.  return 0 

PUSH (A,x) 
1. if(!STACK-FULL()) 
2.  if(STACK-FULL()==-1) 
3.   top2=top2+1 
4.   S2[top2]=x 
5.  else if(STACK-FULL()==-2) 
6.   top1=top1+1 
7.   S1[top1]=x 
8.  else 
9.   top1=top1+1 
10.   S1[top1]=x 
11. else 
12. OVERFLOW 

Answer 1

Если вы пытаетесь реализовать его таким образом, чтобы обе стеки начинались с левой стороны массива. Push и pop не будут O (1). Поскольку элементы обоих стеков будут перемешаны между собой, и вы должны поддерживать, принадлежит ли позиция стеку1 или стеке2, и если оно пустое (перечисление).

Когда вы пытаетесь вставить элемент в один из стека, вам нужно найти пустой слот и поместить туда значение (для этого вы могли бы пропустить элементы другого стека, которые будут находиться между ними) ,

Когда вы пытаетесь удалить элемент из одного из стека, вы должны пометить элемент как пустой и найти элемент в левой части выбитого элемента, который принадлежит к соответствующему стеку, и сделать его вершиной стек.

А также для проверки полного или пустого его лучше проверить с суммой элементов в обоих стеках.

Push и Pop будут O (n) вместо того, что вы хотите, как O (1).

Если вы все еще хотите реализовать push и pop в O (1) и оба стека с той же стороны массива, я предлагаю вам поддерживать верхнюю часть стеков, следующий свободный индекс и предыдущий/(следующий свободный индекс) для каждый элемент.

Если элемент занят, он укажет на предыдущий индекс в стеке, если он свободен, он будет содержать следующий свободный индекс.

Ex: free = 0; top1 = -1, -1 = top2 следующая [I] = I + 1 следующая [п-1] = -1 изначально

проверка на полную это просто полный == -1

проверка на пустоту стека будет быть top1 == -1

вставка х в верхней 1

a[free] = x 
next[free] = top1 // useful while poping 
top1 = free 
free = next[free] 

выскакивают из STACK1

temp = top1 // storing top since we have to make this index as free and point next of this index to previous free 
top1 = next[top1] // setting previous element as top 
next[temp] = free 
free = temp 

Drawback для этого Мы используем O (n) дополнительную память