面试题 03.01. 三合一 【简单题】

三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。
构造函数会传入一个stackSize参数，代表每个栈的大小。
 输入：
["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]
 输出：
[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。

 输入：
["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
 输出：
[null, null, null, null, 2, 1, -1, -1]


题目讲解
【历史重难点题目】

历史重难点题目总结

【核心思想】

数组的下标为[0, 0 + 3, … , 0 + 3 * (stackSize - 1)] 存放stack0;
数组的下标为[1, 1 + 3, … , 1 + 3 * (stackSize - 1)] 存放stack1;
数组的下标为[2, 2 + 3, … , 2 + 3 * (stackSize - 1)] 存放stack2;

【代码】
class TripleInOne {
    private int[] arr;
    private int[] stackTop; // 每个栈当前可push的索引（对应到arr中的索引）
    private int stackSize;

    public TripleInOne(int stackSize) {
        this.stackSize = stackSize;
        arr = new int[stackSize * 3];
        stackTop = new int[]{0, 1, 2};
    }

    public void push(int stackNum, int value) {
        int curStackTop = stackTop[stackNum];
        if (curStackTop / 3 == stackSize)
            // 栈已满
            return;

        arr[curStackTop] = value;
        stackTop[stackNum] += 3;
    }

    public int pop(int stackNum) {
        if (isEmpty(stackNum))
            return -1;
      
        int value = arr[stackTop[stackNum] - 3];
        stackTop[stackNum] -= 3;
        return value;
    }

    public int peek(int stackNum) {
        if (isEmpty(stackNum))
            return -1;
            
        return arr[stackTop[stackNum] - 3];
    }

    public boolean isEmpty(int stackNum) {
        return stackTop[stackNum] < 3;
    }
}

【备注】

帮到你了的话，点个在看吧


关注微信公众号“算法岗从零到无穷”，更多算法知识点告诉你。

                    
                        

                
用数组结构实现大小固定的栈和队列，这是一个面试的常考题目，也是一个比较简单的题目。
1.实现栈结构：栈结构是先进后出的，只需要一个数组和一个记录位置的变量size，当进来一个元素，size就++，出去一个元素size就–。
2.实现队列结构：相对栈结构要难搞一些，队列的先进先出的，需要一个数组和三个变量，size记录已经进来了多少个元素，in记录刚进来的元素应该放在哪个位置，out表示用户要求弹出的元素所在的位置。size的作用不止于此，它还是in与out 的操作的关键信息，使得in与out解耦，避免的很多的麻烦，好像书本讲的是没有size这个变量的。当in或者out达到底部的时候就跳回0处。
/**
 * 固定数组实现一个队列
 * 队列先进先出，方法有push,pull,peek
 */
public class C02_ArrayToQueue {
   public static class MyQueue{
       private int out;//新进来的数 放这
     private int in;//用户要求弹出的数
      private int size;//已经进队列的个数
       
        private int arr[];
      public MyQueue(int iniSize){
            arr = new int[iniSize];
         size = 0;
          in = 0;
            out = 0;
       }
       public void push(int num){
            if(size==arr.length){
             throw new RuntimeException(“the queue is full!”);
          }
           size++;//大小扩展一个
           arr[in] = num;//赋值
            in = in==arr.length-1 ? 0 : in+1;//如果已经到达数组末尾就重新等于0
        }
       public int pull(){
          if(size==0){
             throw new RuntimeException(“the queue is empty!”);
         }
           size–;
         int t = out;//记录
            out = out==arr.length-1 ? 0 : out+1;//如果已经到达数组末尾就重新等于0
         return arr[t];
        }
       public int peek(){
          if(size==0){
             throw new RuntimeException(“the queue is empty!”);
         }
           return arr[out];
      }
   }
   public static void main(String[] args) {
      int iniSize = 3;
     MyQueue myQueue = new MyQueue(iniSize);
       myQueue.push(12);
      myQueue.push(13);
      myQueue.push(15);
      System.out.println(myQueue.pull());
     System.out.println(myQueue.pull());
     System.out.println(myQueue.pull());
     myQueue.push(23);
      myQueue.push(24);
      System.out.println(myQueue.pull());
     System.out.println(myQueue.peek());
 }
}

/**
 * 固定数组实现栈结构
 * 实现方法push,pop,peek
 * 当越界的时候抛出一个运行时异常
 * 简单面试题
 */
public class C01_ArrayToStack {
   public static class MyStack{
       private int size;//指针位置，也表示栈已经压了多少
        private int[]arr;
       MyStack(int iniSize){//构造方法初始化数组
            arr = new int[iniSize];
         size = 0;
      }
       public void push(int num){
            if(size == arr.length){
               throw new RuntimeException("栈下标越界！");
          }
           arr[size++] = num;
      }
       public int pop(){
           if(size == 0){
               throw new RuntimeException("栈中已经没有元素可以弹出！");
           }
           return arr[--size];
       }
       public int peek(){
          if(size == 0){
               throw new RuntimeException("栈中已经没有元素可以弹出！");
           }
           return arr[size];
     }
   }
   public static void main(String[] args) {
      int len = 13;
        MyStack myStack = new MyStack(len);
       for (int i = 0; i < len; i++) {
         myStack.push(i);
        }
       for (int i = 0; i < len; i++) {
         System.out.println(myStack.pop());
      }
   }
}

            

一个想法：分为三部分，如果插入其中一个栈满了，而数组没满，则移动栈。
第二个想法：利用数组实现链表。
转载于:https://www.cnblogs.com/xuehongyang/p/5373830.html

继续我提倡的抠门思想，也不枉我和青菜相交一场。 

网上流传着两种方法; 

方法1 

采用交叉索引的方法 

一号栈所占数组索引为0，2，4,6,8…（K*2） 

二号栈所占数组索引为1,3,5,7,9，，，（K*2+1） 

算法实现如下： 

public class NewStack 

{ 

 object []arr； 

 int top1； 

int top2； 

public NewStack（int capticy） 

{ 

arr = new object[capticy]； 

top1=-1; 

top2=-2; 

} 

public void Push(int type,object element) 

{ 

if(type == 1) 

{ 

if(top1+2>=arr.Length) 

throw new Exception(“The stack is full”); 

else 

{ 

top1+=2; 

arr[top1 ] = element; 

} 

} 

else//type==2 

{ 

if(top2+2>=arr.length) 

throw new Exception(“The stack is full”); 

else 

{ 

top2+=2; 

arr[top2]=element; 

} 

} 

} 

public object Pop(int type) 

{ 

object obj = null; 

if(type == 1) 

{ 

if(top1 == -1) 

throw new Exception(“The stack is empty”); 

else 

{ 

obj = arr[top1]; 

arr[top1]=null; 

top1=-2; 

} 

} 

else//type == 2 

{ 

if(top2==-2) 

throw new Exception(“The stack is empty”); 

else 

{ 

obj = arr[top2]; 

arr[top] = null; 

top2 = 2; 

} 

} 

return obj; 

} 

public object Peek(int type) 

{ 

if(type==1) 

{ 

if(top1==-1) 

throw new Exception(“The stack is empty”); 

return arr[top1]; 

} 

else/type ==2 

{ 

if（top2==-2） 

throw new Eception(“The stack is empty”); 

return arr[top2]; 

} 

} 

} 

方法二； 

第一个栈A：从最左向右增长 

第二个栈B：从最右向左增长； 

代码实现如下： 

public   class NewStack 

{ 

object[]arr; 

int top 1; 

int top 2; 

public NewStack(int capticy) 

{ 

arr= new object[capticy]; 

top1=0; 

top2=capticy; 

} 

public void Push(int type,object element) 

{ 

if(top1==top2) 

throw new Exception(“The stack is full”); 

if(type == 1) 

{ 

arr[top1] = element; 

top1++; 

} 

else//type==2 

{ 

top2–; 

arr[top2] = element; 

} 

} 

public object Pop(int type) 

{ 

object obj = null; 

if(type == 1) 

{ 

if(top1 ==0) 

throw new Exception(“The stack is empty”); 

else 

{ 

top1–; 

obj = arr[top1]; 

arr[top1]=null; 

} 

} 

else//type == 2 

{ 

if(top2 == arr.Length) 

throw new Exception(“The stack is empty“）； 

else 

{ 

obj =arr[top2]; 

arr[top2]=null; 

top2++; 

} 

} 

return obj; 

} 

public object Peek(int type) 

{ 

if (type==1) 

{ 

if(top1 == 0) 

throw new Excetion(“The stack is empty”); 

return arr[top1 - 1]; 

} 

else//type ==2 

{ 

if(top2==arr.Length) 

throw new Exception(“The stack is empty”); 

return arr[top2]; 

} 

} 

} 

综合比较上述两种算法，我们发现，算法1实现的两个栈，每个都只有n/2个字间大小；而算法2实现的两个栈，如果其中一个很小，另一个则可以很大，它们的和为常数n。