Java中栈和队列的类

清疚 2022-04-13 04:37 196阅读 0赞

Stack类：栈类  过时    public class Stack<E> extends Vector<E>
    Queue：队列类
    Deque：双端队列（栈操作建议使用）
     
    public class LinkedList<E> 
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
     
     
    public interface Deque<E> extends Queue<E>   扩展了java.util.Collection接口

双端队列

public interface Queue<E> extends Collection<E>

扩展了java.util.Collection接口  
Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

所以Java中实现栈和队列操作都可以通过使用LinkedList类实现，当然底层使用的链表。

public class ArrayDeque<E> extends AbstractCollection<E>
                               implements Deque<E>, Cloneable, Serializable
     
    ArrayDeque是Deque 接口的大小可变数组的实现

/**
     * 功能：模拟生活中罗盘子案例
     * 技能：LinkedList
     * 
     * LinkedList既可以当做线性表处理，也可以当做栈、队列使用
     * @author Administrator*
     */
    public class TestDeque {
     
    	public static void main(String[] args) {
    		//创建一个栈
    		Deque deque =  new LinkedList();		
    		//罗盘子:入栈
    //		deque.addFirst("盘子1");
    //		deque.addFirst("盘子2");
    //		deque.addFirst("盘子3");
    		deque.push("盘子1");
    		deque.push("盘子2");
    		deque.push("盘子3");		
    		//获取最上面的盘子：获取栈顶元素
    //		System.out.println(deque.getFirst());
    //		System.out.println(deque.getFirst());
    //		System.out.println(deque.getFirst());
    		System.out.println(deque.peek());
    		System.out.println(deque.peek());
    		System.out.println(deque.peek());		
    		//拿走盘子：出栈
    //		System.out.println(deque.removeFirst());
    //		System.out.println(deque.removeFirst());
    //		System.out.println(deque.removeFirst());
    		System.out.println(deque.pop());
    		System.out.println(deque.pop());
    		System.out.println(deque.pop());
     
    	}
     
    }

![70][]

/**
     * 功能：模拟生活中超市购物排队结算
     * 技能：使用LinkedList实现队列的操作
     * 
     * @author Administrator
     *
     */
    public class TestQueue {
    	public static void main(String[] args) {
    		//创建一个队列
    		java.util.Queue queue = new LinkedList();		
    		//入队
    		queue.offer("张三");
    		queue.offer("李四");
    		queue.offer("王五");
    		//获取队头元素
    		System.out.println(queue.element());
    		System.out.println(queue.element());
    		System.out.println(queue.element());
    		//出队
    		System.out.println(queue.remove());
    		System.out.println(queue.poll());
    		queue.offer("赵六");
    		System.out.println(queue.poll());
    		System.out.println(queue.poll());
    		System.out.println(queue.poll());
    		System.out.println(queue.poll());
    		System.out.println(queue.poll());
    	}
    }

![70 1][]

/**
     * 借助栈实现进制转换（10----2）
     * @author Administrator
     *
     */
    public class TestConversion {
    	public static void main(String[] args) {		
    		int n = 13;
    		int t = n;
    		//String str = "";
    		Deque<Integer>  deque = new LinkedList<Integer>();
    		while(t>0){
    			//除以2得到余数作为二进制位
    			int mod = t%2;
    			//System.out.print(mod);
    			//str = mod + str;
    			deque.push(mod);
    			//除以2得到商作为被除数继续
    			int result = t/2;
    			t = result;
    		}
    		System.out.print(n+"--------->");
    		while(!deque.isEmpty()){
    			System.out.print(deque.pop());
    		}		
    	}
    }

![70 2][]

总之：

1、深入理解pop的深层含义

2、分清是栈还是堆，以及二者的区别：

①：栈是后进先出，使用的关键词是：pop，push和peek

②：堆是先进先出，使用的关键词是：enqueue、dequeue和peek

[70]: /images/20220413/aa0ae3395236466897aa2d8f57020f28.png
[70 1]: /images/20220413/c913b2a45dc849de87942235df9b193b.png
[70 2]: /images/20220413/f115aa2c88864040ac0256591d8d0937.png