数组实现stack和queue，及其相互实现

心已赠人 2023-06-08 14:59 20阅读 0赞

queue:先进先出  
stack:先进后出

stack实现queue  
一般写法 两个stack，元素的出和进都放到stack1，每进一个就倒2次（s1->s2 s1存新 s2->s1），把后加进来的放到最下面；  
高性能算法:s1负责出，s2负责入  
入队时，s2若为空，将s1导入s2，然后将元素压入s2；s2不为空，元素直接加入s2  
出队时，判断s1是否为空，如不为空，则直接弹出顶元素；如为空，则将s2的元素逐个“倒入”s1，把最后一个元素弹出并出队。  
这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。

用queue实现stack  
也需要两个queue，放入的时候直接到有数的queue中即可，后进入的在队尾；但是出的时候因为要出队尾的，所以逐个将元素转移到另一个queue，最后一个的时候直接返回即可；  
或者新来的放进空的queue1，另一个queue的逐个塞入queue1

数组实现stack:挨个向后放即可，出的时候顶端开始出

数组实现对列:保持左边是最先进来的，移除的时候移除第一个，别的左移，保持第0位是最先进来的  
第二种方案:来个标志位 oldest+size,oldest=contenntSize-1出时，oldest=0.

下面仅仅给出用stack实现queue的方案：

public class QueueWithStack {
    
        Stack<String> stack1;
        Stack<String> stack2;
        public int size = 0;
        // 记录压出栈的总次数
        public static  int  operate = 0;
    
    
        public QueueWithStack(){
            this.stack1 = new Stack<>();
            this.stack2 = new Stack<>();
        }
        public void add(String s){
            if(size == 0){
                stack1.push(s);
            }else{
                for(int i =0;i<size;i++){
                    stack2.push(stack1.pop());
                    operate++;
                }
                stack1.push(s);
                for(int i=0;i<size;i++){
                    stack1.push(stack2.pop());
                    operate ++;
                }
            }
            size ++;
        }
    
        public String remove(){
            if(size == 0){
                return null;
            }
            size--;
            return stack1.pop();
        }
    
        public void addInStack1(String s){
            if(size > 0 && stack1.isEmpty()){
                for(int i=0; i<size; i++){
                    stack1.push(stack2.pop());
                    operate ++;
                }
            }
            stack1.push(s);
            size ++ ;
        }
    
        public String removeStFromSack2(){
            if(size == 0){
                return null;
            }
            String tmp ;
            if(stack2.isEmpty()){
                for(int i=0; i<size-1 ;i++){
                    stack2.push(stack1.pop());
                    operate ++;
                }
                tmp = stack1.pop();
            }else{
                tmp = stack2.pop();
            }
            size --;
            return tmp;
        }
    
    
        public static void main(String[] args) {
            QueueWithStack queue = new QueueWithStack();
            queue.addInStack1("1");
            queue.addInStack1("2");
            queue.addInStack1("3");
            queue.addInStack1("1");
            System.out.println(queue.removeStFromSack2());
            System.out.println(queue.removeStFromSack2());
            System.out.println(queue.removeStFromSack2());
            System.out.println(queue.removeStFromSack2());
            System.out.println("方式1："+QueueWithStack.operate);
    
            QueueWithStack.operate = 0;
    
            QueueWithStack queue1 = new QueueWithStack();
            queue1.add("1");
            queue1.add("2");
            queue1.add("3");
            queue1.add("1");
            System.out.println(queue1.remove());
            System.out.println(queue1.remove());
            System.out.println(queue1.remove());
            System.out.println(queue1.remove());
            System.out.println("方式2："+QueueWithStack.operate);
        }
    }