数据结构之栈与队列 淩亂°似流年 2022-04-23 23:44 226阅读 0赞 ### 1.栈与队列 ### 栈与队列是程序设计中广泛使用的两种重要的线性数据结构。 栈是LIFO(Last In First Out),先存进去的数据只能最后被取出来,进出顺序逆序,即先进后出,后进先出。 队列是FIFO(First In First Out),它保持进出顺序一致,即先进先出,后进后出。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70][] ### 4.如何使用两个栈模拟队列操作 ### public class TwoStackForQueue<E> { /* * 用法两个stack 实现队列操作 队列是先进先出的 * 思想:设置两个stack A,B, stackA为入队的栈,stackB为出队的栈 * 入队直接进栈A,出栈需要判断栈B是否为空,如果为空,需要将栈A中的元素放入栈B中 * 如果不为空 直接获取栈B的栈顶元素 */ Stack<E> A = new Stack<>(); Stack<E> B = new Stack<>(); public static void main(String[] args) { TwoStackForQueue<Integer> queue = new TwoStackForQueue<>(); queue.put(1); queue.put(2); queue.put(3); // int i = queue.pop(); // System.out.println(i); // i = queue.pop(); // System.out.println(i); // i = queue.pop(); // System.out.println(i); while(!queue.empty()){ int i = queue.pop(); System.out.println(i); } } //判断是否队空 public boolean empty(){ return A.isEmpty() && B.isEmpty(); } //出队 public synchronized E pop(){ if(B.isEmpty()){ while(!A.isEmpty()) { B.push(A.pop()); } } return B.pop(); } //入队 public synchronized void put(E e){ A.push(e); } } ### 5.如果使用两个队列模拟栈操作 ### public class TwoQueueForStack<E> { /* * 使用两个队列实现栈 栈的特点是先进后出,后进先出 * 思路:两个Queue 使用LinkedList实例化 LinkedList实际上是一个双向链表 * q1作为入栈的队列 即直接将入栈的数据放入q1 * q2作为出栈的队列 即需要出栈时,如果q1只有一个元素 直接出栈 * 如果q1不止一个元素,即可以将q1队列中的数据依次放入q2,最后一个不放入,最后一个元素输出 * 再将q2中的元素依次放回q1 */ private Queue<E> q1 = new LinkedList<E>(); private Queue<E> q2 = new LinkedList<E>();; public static void main(String[] args) { TwoQueueForStack<Integer> stack = new TwoQueueForStack<>(); stack.put(1); stack.put(2); stack.put(3); while(!stack.empty()){ int i = stack.pop(); System.out.println(i); } } //判断是否栈空 public boolean empty(){ return q1.isEmpty() && q2.isEmpty(); } //出栈 public synchronized E pop(){ int size = q1.size(); if(size==1) return q1.poll(); int i=1; while(!(i==size)){ q2.add(q1.poll()); i++; } E e = q1.poll(); while(!q2.isEmpty()){ q1.add(q2.poll()); } return e; } //入栈 public synchronized void put(E e){ q1.add(e); } } 参考:[https://www.cnblogs.com/weiziqiang/p/8998081.html][https_www.cnblogs.com_weiziqiang_p_8998081.html] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70]: /images/20220222/dc3f97f4809f498a9ce176b3fc5b3e21.png [https_www.cnblogs.com_weiziqiang_p_8998081.html]: https://www.cnblogs.com/weiziqiang/p/8998081.html
还没有评论,来说两句吧...