数据结构与算法之栈和队列

栈和队列

---

特点

1. 栈是一种先进后出的结构，队列是一种先进先出的结构
2. 栈通常不考虑排序，需要O（n）的时间复杂度才能找到栈中最大或者最小的数据

---

面试题用两个栈实现队列

import java.util.Stack; //使用栈记得引用java.util,Stack包 

public class Solution {  
Stack<Integer> stack1 = new Stack<Integer>();  
Stack<Integer> stack2 = new Stack<Integer>();  

//入栈函数 
public void push(int num) {  
       stack1.push(num);    //要往栈中压入什么就直接用栈的push方法就好了 
    }  

//出栈函数 
public int pop() {  
Integer re=null;   
if(!stack2.empty()){  // 如果栈2不是空的，那么把最上面那个取出来 
           re=stack2.pop();   
       }else{   
//如果栈2是空的，就把栈1里的数一个个取出来，放到栈2里 
while(!stack1.empty()){     
                re=stack1.pop();   
                stack2.push(re);   
                             }   
//栈2里有数之后，再次把里面的数取出来 
if(!stack2.empty()){   
                         re=stack2.pop();   
                   }   
       }   
return re;   
    }