如何实现一个数组的3个堆栈？
有时，我遇到以下面试问题：如何实现一个数组的3个堆栈？ 当然，任何静态分配都不是解决scheme。
空间（而不是时间）高效。 你可以：
1）定义两个堆栈，从数组端点开始，向相反的方向增长。
2）定义第三个堆栈，从中间开始，向任意方向增长。
3）重新定义Push操作，以便在操作要覆盖其他堆栈时，在推送之前将整个中间堆栈向相反的方向移动。
您需要为前两个堆栈存储堆栈顶部，并在某个结构中存储第三个堆栈的开始和结束。
编辑
以上你可能会看到一个例子。 这个转换是用一个相等的空间分割策略来完成的，尽pipe可以根据你的问题启发式来select其他策略。
编辑
根据@ ruslik的build议， 中间堆栈可以通过交替序列来实现后续的推送。 由此产生的堆栈结构将如下所示：
| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |
在这种情况下，您需要在中间堆栈中存储元素的数量n并使用函数：
f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3 知道下一个数组元素用于这个堆栈。
尽pipe这可能会导致更less的移位，但这三个堆栈的实现并不一致，而且不一致（你知道）会导致特殊情况，更多的错误和维护代码的困难。
只要你尝试从一个堆栈中的所有项目排列在一个“结束”的arrays，你缺乏第三个堆栈的空间。
但是，您可以“穿插”堆栈元素。 第一个堆栈的元素位于索引i * 3 ，第二个堆栈的元素位于索引i * 3 + 1 ，第三个堆栈的元素位于索引i * 3 + 2 （其中i是整数）。
+----+----+----+----+----+----+----+----+----+----+----+----+----+.. | A1 : B1 : C1 | A2 : B2 : C2 | : B3 | C3 | : B4 : | : +----+----+----+----+----+----+----+----+----+----+----+----+----+.. ^ ^ ^ A´s top C´s top B´s top
当然，这个scheme会浪费空间，特别是当堆栈的大小不一样时。 你可以创build类似于上面描述的任意复杂的scheme，但是不知道对于提出的问题有更多的限制，我会在这里停下来。
更新：
由于下面的评论有一个非常好的一点，应该补充的是，散布是没有必要的，甚至可能会降低性能相比，更简单的内存布局，如下所示：
+----+----+----+----+----+----+----+----+----+----+----+----+----+.. | A1 : A2 : : : | B1 : B2 : B3 : B4 : | C1 : C2 : C3 : +----+----+----+----+----+----+----+----+----+----+----+----+----+.. ^ ^ ^ A´s top B´s top C´s top
即给每个堆栈它自己的连续的内存块。 如果真正的问题是如何尽可能好地使用固定的内存量，为了不超过必要的限制每个堆栈，那么我的答案是不会很有帮助的。
在这种情况下，我会用@belisarius的答案去：一个堆栈到内存区域的“底部”端，“向上”增长; 另一个堆栈到达内存区域的“顶端”，向下“增长”，一个堆栈在中间向任意方向生长，但当它靠近其他堆栈时，能够移动。
为所有三个筹码保持一个竞技场。 每个推入堆栈的元素都有一个指向其前一个元素的向后指针。 每个堆栈的底部都有一个指向NULL / None的指针。
竞技场保持一个指向空闲空间中的下一个项目的指针。 推送将该元素添加到相应的堆栈，并将其标记为不再处于空闲空间中。 popup消除从相应的堆栈中的元素，并将其添加到空闲列表。
从这个草图中，堆栈中的元素需要一个反向指针和数据空间。 可用空间中的元素需要两个指针，所以可用空间被实现为双向链表。
包含三个堆栈的对象需要一个指向每个堆栈顶部的指针以及一个指向空闲列表头部的指针。
这个数据结构使用所有的空间，并在不断的推动和popup。 堆栈中的所有数据元素都有单个指针的开销，而空闲列表元素使用最大值（两个指针，一个指针+一个元素）。
后来：python代码是这样的。 注意使用整数索引作为指针。
class StackContainer(object): def __init__(self, stack_count=3, size=256): self.stack_count = stack_count self.stack_top = [None] * stack_count self.size = size # Create arena of doubly linked list self.arena = [{'prev': x-1, 'next': x+1} for x in range(self.size)] self.arena[0]['prev'] = None self.arena[self.size-1]['next'] = None self.arena_head = 0 def _allocate(self): new_pos = self.arena_head free = self.arena[new_pos] next = free['next'] if next: self.arena[next]['prev'] = None self.arena_head = next else: self.arena_head = None return new_pos def _dump(self, stack_num): assert 0 <= stack_num < self.stack_count curr = self.stack_top[stack_num] while curr is not None: d = self.arena[curr] print '\t', curr, d curr = d['prev'] def _dump_all(self): print '-' * 30 for i in range(self.stack_count): print "Stack %d" % i self._dump(i) def _dump_arena(self): print "Dump arena" curr = self.arena_head while curr is not None: d = self.arena[curr] print '\t', d curr = d['next'] def push(self, stack_num, value): assert 0 <= stack_num < self.stack_count # Find space in arena for new value, update pointers new_pos = self._allocate() # Put value-to-push into a stack element d = {'value': value, 'prev': self.stack_top[stack_num], 'pos': new_pos} self.arena[new_pos] = d self.stack_top[stack_num] = new_pos def pop(self, stack_num): assert 0 <= stack_num < self.stack_count top = self.stack_top[stack_num] d = self.arena[top] assert d['pos'] == top self.stack_top[stack_num] = d['prev'] arena_elem = {'prev': None, 'next': self.arena_head} # Link the current head to the new head head = self.arena[self.arena_head] head['prev'] = top # Set the curr_pos to be the new head self.arena[top] = arena_elem self.arena_head = top return d['value'] if __name__ == '__main__': sc = StackContainer(3, 10) sc._dump_arena() sc.push(0, 'First') sc._dump_all() sc.push(0, 'Second') sc.push(0, 'Third') sc._dump_all() sc.push(1, 'Fourth') sc._dump_all() print sc.pop(0) sc._dump_all() print sc.pop(1) sc._dump_all()
为简单起见，如果内存使用效率不高，可以将数组分成列表节点，将它们全部添加到空闲节点列表中，然后将堆栈实现为链表，根据需要从空闲列表中获取节点。 不过，这种方法中没有什么特别之处。
在低级语言中，可以使用内存来存储指针，或者如果堆栈元素的types如int ，可以表示数组中的索引。
我有这个问题的解决scheme。 下面的程序充分利用了数组（在我的情况下是一个StackNode对象数组）。 让我知道你们是否对此有任何疑问。 [这里已经很晚了，所以我懒得去logging代码 – 我知道，我应该:)]
public class StackNode { int value; int prev; StackNode(int value, int prev) { this.value = value; this.prev = prev; } } public class StackMFromArray { private StackNode[] stackNodes = null; private static int CAPACITY = 10; private int freeListTop = 0; private int size = 0; private int[] stackPointers = { -1, -1, -1 }; StackMFromArray() { stackNodes = new StackNode[CAPACITY]; initFreeList(); } private void initFreeList() { for (int i = 0; i < CAPACITY; i++) { stackNodes[i] = new StackNode(0, i + 1); } } public void push(int stackNum, int value) throws Exception { int freeIndex; int currentStackTop = stackPointers[stackNum - 1]; freeIndex = getFreeNodeIndex(); StackNode n = stackNodes[freeIndex]; n.prev = currentStackTop; n.value = value; stackPointers[stackNum - 1] = freeIndex; } public StackNode pop(int stackNum) throws Exception { int currentStackTop = stackPointers[stackNum - 1]; if (currentStackTop == -1) { throw new Exception("UNDERFLOW"); } StackNode temp = stackNodes[currentStackTop]; stackPointers[stackNum - 1] = temp.prev; freeStackNode(currentStackTop); return temp; } private int getFreeNodeIndex() throws Exception { int temp = freeListTop; if (size >= CAPACITY) throw new Exception("OVERFLOW"); freeListTop = stackNodes[temp].prev; size++; return temp; } private void freeStackNode(int index) { stackNodes[index].prev = freeListTop; freeListTop = index; size--; } public static void main(String args[]) { // Test Driver StackMFromArray mulStack = new StackMFromArray(); try { mulStack.push(1, 11); mulStack.push(1, 12); mulStack.push(2, 21); mulStack.push(3, 31); mulStack.push(3, 32); mulStack.push(2, 22); mulStack.push(1, 13); StackNode node = mulStack.pop(1); node = mulStack.pop(1); System.out.println(node.value); mulStack.push(1, 13); } catch (Exception e) { e.printStackTrace(); } } }
以前的答案是一个变体：堆栈＃1从左边开始增长，堆栈＃2从右边开始增长。
堆栈＃3位于中间，但元素依次向左和向右扩展。 如果N是中心索引，则堆栈增长为：N，N-1，N + 1，N-2，N + 2等。一个简单的函数将堆栈索引转换为数组索引。
我想你应该把数组分成3块，第一个栈头在0，第二个栈头在n / 3，第三个栈头在n-1。
所以在下面实施推送操作：
- 第一和第二堆栈使i ++和第三堆栈使i–;
- 如果遇到第一个堆栈没有空间推送，则向前移动第二个堆栈k / 3个位置。 其中k是剩下要填充的位置的数量。
- 如果遇到第二个堆栈没有空间可推，请将第二个堆栈2 * k / 3个位置向后移。 其中k是剩下要填充的位置的数量。
- 如果遇到第三个堆栈没有空间推送，请将第二个堆栈2 * k / 3个位置向后移。 其中k是剩下要填充的位置的数量。
当没有剩余空间时，我们正在移位k / 3和2 * k / 3，所以在中间堆栈移位之后，每个堆栈都有相同的可用空间。
当第一个堆栈进入索引0，然后0 + 3 = 3，然后3 + 3 = 6 …时，以这种方式将堆栈存储在区域中; 第二个进入索引1，1 + 3 = 4，4 + 3 = 7 …; 第三个进入索引2，2 + 3 = 5，5 + 3 = 8因此，如果我们用a来标记第一个堆栈元素，如同一个b和那里与c，我们得到：a1 b1 c1 a2 b2 c2 a3 b3 C3 …
可能会有差距，但我们总是知道存储在3元素topIndex数组中的顶部索引。
在这个页面上已经有很多解决这个问题的方法。 根本的问题，恕我直言，是：
-
每次推/拉操作需要多长时间？
-
多less空间被使用？ 具体而言，可以推送到三个堆栈以导致数据结构空间不足的元素的最小数量是多less？
据我所知，每个已经发布在这个页面上的解决scheme可能会花费线性时间来进行push / pop，或者可能会耗尽空间，而且线性空间仍然是空的。
在这篇文章中，我将参考性能更好的解决scheme，我将介绍最简单的解决scheme。
为了更仔细地描述解决scheme空间，我将以下面的方式参考数据结构的两个function：
除非三个堆栈至less包含n-O个（g（n））个项目，否则将花费O（f（n））分摊时间来执行push / pop并且没有空间不足的结构将被称为f，g）结构。 f和g越小越好。 已经发布在这个页面上的每个结构对于时间或空间都有n个。 我将演示一个（1，√n）结构。
这全部基于：
-
Michael L. Fredman和Deborah L.Goldsmith，“algorithm杂志”第17卷，第1期，1994年7月，第45-70页中的“Three Stacks”
- 1988年的第29届计算机科学基础年度研讨会（FOCS）出现了一个较早的版本
-
Deborah Louise Goldsmith博士gradle于加利福尼亚大学圣地亚哥分校电子工程/计算机科学系，1987年，“有效的内存pipe理> = 3堆栈”
它们表明，尽pipe我不会提出任何S的（log n / log S，S）结构。这相当于任意t的（t，n 1 / t ）结构。 我将展示一个简化版本（1，√n）结构。
将arrays分成大小为Θ（√n）的块。 块的编号从1到Θ（√n），块的编号称为“地址”。 地址可以存储在数组槽中，而不是真实的项目。 给定块内的项目可以用小于O（√n）的数字来引用，这样的数字称为索引。 一个索引也适合在一个数组槽中。
第一个块将被保留用于存储地址和索引，其他块将不会存储任何地址或索引。 第一个块叫做目录 。 每个非目录块将是空的或者只保存来自三个堆栈之一的元素; 也就是说，没有块会有不同的堆栈中的两个元素。 另外，每个堆栈最多只有一个被部分填充的块 – 与堆栈相关的所有其他块将完全填满或完全空出。
只要有一个空的块，一个栈操作将被允许。 stream行操作总是被允许的。 当推送操作失败时，数据结构已满。 此时，不包含其中一个堆栈的元素的槽数最多为O（√n）：堆栈中没有被压入的两个部分填充块以及一个目录块。
每个块都被sorting，以使靠近块前面的元素（较低的索引）更接近堆栈的底部。
该目录成立：
-
三个堆栈顶部的块的三个地址，或者如果特定堆栈中没有块，则为0
-
三个堆栈顶部的元素的三个索引，如果特定堆栈中没有项目，则为0。
-
对于每个完整或部分满块，块的地址低于同一个堆栈中的地址，如果它是堆栈中最低的块，则为0。
-
空闲块的地址，称为引导块，如果没有空闲块，则为0
-
对于每个空闲块，另一个空闲块的地址，如果没有空闲块，则为0
最后两个构成一个堆栈，存储为空闲块的单链表。 也就是说，跟随着以引导块开始的空闲块的地址之后，将给出通过所有空闲块的path，结束于0。
要将项目推入堆栈，请使用该目录在该块内find其顶部块和顶部元素。 如果在这个区域有空间，把物品放在那里然后返回。
否则，通过将引导块的地址更改为空闲块堆栈中下一个空闲块的地址，popup空闲块的堆栈。 将堆栈的地址和索引分别改为刚刚popup的空闲块的地址和1。 将该项目添加到索引1处的刚刚popup的块，然后返回。
所有操作都需要O（1）次。 stream行音乐是对称的。
python
class Stack: def __init__(self): self.pos_1 = 0 self.pos_2 = 1 self.pos_3 = 2 self.stack = [None, None, None] def pop_1(self): if self.pos_2 - 1 > 0: to_ret = self.stack.pop(self.pos_1) self.pos_2 -= 1 self.pos_3 -= 1 return to_ret def push_1(self, value): self.stack.insert(self.pos_1, value) self.pos_2 += 1 self.pos_3 += 1 return None def pop_2(self): if self.pos_2 - 1 < self.pos_3: to_ret = self.stack.pop(self.pos_2) self.pos_3 -= 1 return to_ret def push_2(self, value): self.stack.insert(self.pos_2, value) self.pos_3 += 1 return None def pop_3(self): if self.pos_3 - 1 > self.pos_2: to_ret = self.stack.pop(self.pos_3) return to_ret def push_3(self, value): self.stack.insert(self.pos_3, value) return None if __name__ == "__main__": stack = Stack() stack.push_2(22) stack.push_1(1) stack.push_1(2) print stack.pop_1() print stack.pop_1() print stack.pop_2()
版画： 2 1 22
这是我在C＃中的解决scheme –
/* Program: Implement 3 stacks using a single array * * Date: 12/26/2015 */ using System; namespace CrackingTheCodingInterview { internal class Item { public object data; public int prev; } /// <summary> /// Class implementing 3 stacks using single array /// </summary> public class Stacks { /// <summary> /// Pushing an element 'data' onto a stack 'i' /// </summary> public void Push(int i, object d) { i--; if (available != null) { int ava = (int)available.DeleteHead(); elems[ava].data = d; elems[ava].prev = top[i]; top[i] = ava; } else { Console.WriteLine("Array full. No more space to enter!"); return; } } /// <summary> /// Popping an element from stack 'i' /// </summary> public object Pop(int i) { i--; if (top[i] != -1) { object popVal = elems[top[i]].data; int prevTop = elems[top[i]].prev; elems[top[i]].data = null; elems[top[i]].prev = -1; available.Insert(top[i]); top[i] = prevTop; return popVal; } else { Console.WriteLine("Stack: {0} empty!", i); return null; } } /// <summary> /// Peeking top element of a stack /// </summary> public object Peek(int i) { i--; if (top[i] != -1) { return elems[top[i]].data; } else { Console.WriteLine("Stack: {0} empty!", i); return null; } } /// <summary> /// Constructor initializing array of Nodes of size 'n' and the ability to store 'k' stacks /// </summary> public Stacks(int n, int k) { elems = new Item[n]; top = new int[k]; for (int i = 0; i < k; i++) { top[i] = -1; } for (int i = 0; i < n; i++) { elems[i] = new Item(); elems[i].data = null; elems[i].prev = -1; } available = new SinglyLinkedList(); for (int i = n - 1; i >= 0; i--) { available.Insert(i); } } private Item[] elems; private int[] top; private SinglyLinkedList available; } internal class StacksArrayTest { static void Main() { Stacks s = new Stacks(10, 3); s.Push(1, 'a'); s.Push(1, 'b'); s.Push(1, 'c'); Console.WriteLine("After pushing in stack 1"); Console.WriteLine("Top 1: {0}", s.Peek(1)); s.Push(2, 'd'); s.Push(2, 'e'); s.Push(2, 'f'); s.Push(2, 'g'); Console.WriteLine("After pushing in stack 2"); Console.WriteLine("Top 1: {0}", s.Peek(1)); Console.WriteLine("Top 2: {0}", s.Peek(2)); s.Pop(1); s.Pop(2); Console.WriteLine("After popping from stack 1 and 2"); Console.WriteLine("Top 1: {0}", s.Peek(1)); Console.WriteLine("Top 2: {0}", s.Peek(2)); s.Push(3, 'h'); s.Push(3, 'i'); s.Push(3, 'j'); s.Push(3, 'k'); s.Push(3, 'l'); Console.WriteLine("After pushing in stack 3"); Console.WriteLine("Top 3: {0}", s.Peek(3)); Console.ReadLine(); } } }
输出：
After pushing in stack 1 Top 1: c After pushing in stack 2 Top 1: c Top 2: g After popping from stack 1 and 2 Top 1: b Top 2: f After pushing in stack 3 Top 3: l
我参考这个职位编码 – http://codercareer.blogspot.com/2013/02/no-39-stacks-sharing-array.html
包job.interview; import java.util.Arrays;
public class NStack1ArrayGen<T> { T storage[]; int numOfStacks; Integer top[]; public NStack1ArrayGen(int numOfStks, T myStorage[]){ storage = myStorage; numOfStacks = numOfStks; top = new Integer[numOfStks]; for(int i=0;i<numOfStks;i++){top[i]=-1;} } public void push(int stk_indx, T value){ int r_indx = stk_indx -1; if(top[r_indx]+numOfStacks < storage.length){ top[r_indx] = top[r_indx] < 0 ? stk_indx-1 : top[r_indx]+numOfStacks; storage[top[r_indx]] = value; } } public T pop(int stk_indx){ T ret = top[stk_indx-1]<0 ? null : storage[top[stk_indx-1]]; top[stk_indx-1] -= numOfStacks; return ret; } public void printInfo(){ print("The array", Arrays.toString(storage)); print("The top indices", Arrays.toString(top)); for(int j=1;j<=numOfStacks;j++){ printStack(j); } } public void print(String name, String value){ System.out.println(name + " ==> " + value); } public void printStack(int indx){ String str = ""; while(top[indx-1]>=0){ str+=(str.length()>0 ? "," : "") + pop(indx); } print("Stack#"+indx,str); } public static void main (String args[])throws Exception{ int count=4, tsize=40; int size[]={105,108,310,105}; NStack1ArrayGen<String> mystack = new NStack1ArrayGen<String>(count,new String[tsize]); for(int i=1;i<=count;i++){ for(int j=1;j<=size[i-1];j++){ mystack.push(i, "stk"+i+"_value"+j); } } } }
这打印：
arrays==> [stk1_value1，stk2_value1，stk3_value1，stk4_value1，stk1_value2，stk2_value2，stk3_value2，stk4_value2，stk1_value3，stk2_value3，stk3_value3，stk4_value3，stk1_value4，stk2_value4，stk3_value4，stk4_value4，stk1_value5，stk2_value5，stk3_value5，stk4_value5，stk1_value6，stk2_value6， stk3_value6，stk4_value6，stk1_value7，stk2_value7，stk3_value7，stk4_value7，stk1_value8，stk2_value8，stk3_value8，stk4_value8，stk1_value9，stk2_value9，stk3_value9，stk4_value9，stk1_value10，stk2_value10，stk3_value10，stk4_value10]顶指数==> [36，37，38，39 ]堆栈＃1 ==> stk1_value10，stk1_value9，stk1_value8，stk1_value7，stk1_value6，stk1_value5，stk1_value4，stk1_value3，stk1_value2，stk1_value1堆栈＃2 ==> stk2_value10，stk2_value9，stk2_value8，stk2_value7，stk2_value6，stk2_value5，stk2_value4，stk2_value3，stk2_value2， stk2_value1堆栈＃3 ==> stk3_value10，stk3_value9，stk3_value8，stk3_value7，stk3_value6，stk3_value5，stk3_value4，stk3_value3，stk3_value2，stk3_value1堆栈＃4 ==> stk4_value10， stk4_value9，stk4_value8，stk4_value7，stk4_value6，stk4_value5，stk4_value4，stk4_value3，stk4_value2，stk4_value1
enum stackId{LEFT, MID, RIGHT };
class threeStacks {
int* arr; int leftSize; int rightSize; int midSize; int mid; int maxSize; public: threeStacks(int n):leftSize(0), rightSize(0), midSize(0), mid(n/2), maxSize(n) { arr = new int[n]; } void push(stackId sid, int val){ switch(sid){ case LEFT: pushLeft(val); break; case MID: pushMid(val); break; case RIGHT: pushRight(val); } } int pop(stackId sid){ switch(sid){ case LEFT: return popLeft(); case MID: return popMid(); case RIGHT: return popRight(); } } int top(stackId sid){ switch(sid){ case LEFT: return topLeft(); case MID: return topMid(); case RIGHT: return topRight(); } } void pushMid(int val){ if(midSize+leftSize+rightSize+1 > maxSize){ cout << "Overflow!!"<<endl; return; } if(midSize % 2 == 0){ if(mid - ((midSize+1)/2) == leftSize-1){ //left side OverFlow if(!shiftMid(RIGHT)){ cout << "Overflow!!"<<endl; return; } } midSize++; arr[mid - (midSize/2)] = val; } else{ if(mid + ((midSize+1)/2) == (maxSize - rightSize)){ //right side OverFlow if(!shiftMid(LEFT)){ cout << "Overflow!!"<<endl; return; } } midSize++; arr[mid + (midSize/2)] = val; } } int popMid(){ if(midSize == 0){ cout << "Mid Stack Underflow!!"<<endl; return -1; } int val; if(midSize % 2 == 0) val = arr[mid - (midSize/2)]; else val = arr[mid + (midSize/2)]; midSize--; return val; } int topMid(){ if(midSize == 0){ cout << "Mid Stack Underflow!!"<<endl; return -1; } int val; if(midSize % 2 == 0) val = arr[mid - (midSize/2)]; else val = arr[mid + (midSize/2)]; return val; } bool shiftMid(stackId dir){ int freeSpace; switch (dir){ case LEFT: freeSpace = (mid - midSize/2) - leftSize; if(freeSpace < 1) return false; if(freeSpace > 1) freeSpace /= 2; for(int i=0; i< midSize; i++){ arr[(mid - midSize/2) - freeSpace + i] = arr[(mid - midSize/2) + i]; } mid = mid-freeSpace; break; case RIGHT: freeSpace = maxSize - rightSize - (mid + midSize/2) - 1; if(freeSpace < 1) return false; if(freeSpace > 1) freeSpace /= 2; for(int i=0; i< midSize; i++){ arr[(mid + midSize/2) + freeSpace - i] = arr[(mid + midSize/2) - i]; } mid = mid+freeSpace; break; default: return false; } } void pushLeft(int val){ if(midSize+leftSize+rightSize+1 > maxSize){ cout << "Overflow!!"<<endl; return; } if(leftSize == (mid - midSize/2)){ //left side OverFlow if(!shiftMid(RIGHT)){ cout << "Overflow!!"<<endl; return; } } arr[leftSize] = val; leftSize++; } int popLeft(){ if(leftSize == 0){ cout << "Left Stack Underflow!!"<<endl; return -1; } leftSize--; return arr[leftSize]; } int topLeft(){ if(leftSize == 0){ cout << "Left Stack Underflow!!"<<endl; return -1; } return arr[leftSize - 1]; } void pushRight(int val){ if(midSize+leftSize+rightSize+1 > maxSize){ cout << "Overflow!!"<<endl; return; } if(maxSize - rightSize - 1 == (mid + midSize/2)){ //right side OverFlow if(!shiftMid(LEFT)){ cout << "Overflow!!"<<endl; return; } } rightSize++; arr[maxSize - rightSize] = val; } int popRight(){ if(rightSize == 0){ cout << "Right Stack Underflow!!"<<endl; return -1; } int val = arr[maxSize - rightSize]; rightSize--; return val; } int topRight(){ if(rightSize == 0){ cout << "Right Stack Underflow!!"<<endl; return -1; } return arr[maxSize - rightSize]; }
};
