数据结构（三）手写队列

柔情只为你懂 2023-07-04 12:40 4阅读 0赞

1.  前沿  
    本文是手写队列，如果要看栈的实现方式,请关注前文:  
    [数据结构（二) 使用链表实现栈][Link 1]
2.  介绍  
    本文使用数组和栈的方式实现队列,使用栈的方式实现队列需要使用两个栈（ stackPush，stackPop）来实现，必须保证两点：1 stackPush中元素必须一次性全部压入stackPop, 2 stackPush在压入元素时，stackPop必须为空，首先介绍栈实现队列方式:
3.  栈实现队列

/**
     1. Class:基础数据结构-队列(两个栈)
     2. 必须保证两点：1  stackPush必须一次性全部压入stackPop, 2 stackPush在压入数据时，stackPop必须为空
     3.  4. @Author: wangzhong
     5. @Date: 2020-02-10 17:41
     */
    public class MyQueue2 {
        
    	Stack<Integer> stackPush;
    	Stack<Integer> stackPop;
    
    	public MyQueue2(Stack<Integer> stackPush, Stack<Integer> stackPop) {
        
    		this.stackPush = stackPush;
    		this.stackPop = stackPop;
    	}
    
    	/**
    	 * 进队
    	 */
    	public void add(Integer value) {
        
    		stackPush.push(value);
    	}
    
    	/**
    	 * 出队
    	 */
    	public Integer poll() {
        
    		if (stackPush.isEmpty() && stackPop.isEmpty()) {
        
    			throw new RuntimeException("queue is empty");
    		}
    		//在stackPop为空时，压入数据
    		else if (stackPop.isEmpty()) {
        
    			while (!stackPush.isEmpty()) {
        
    				Integer a = stackPush.pop();
    				stackPop.push(a);
    			}
    
    		}
    		//出队
    		return stackPop.pop();
    	}
    
    	public static void main(String[] args) {
        
    		MyQueue2 myQueue2=new MyQueue2(new Stack<Integer>(),new Stack<Integer>());
    		myQueue2.add(2);
    		myQueue2.add(3);
    		myQueue2.add(5);
    		myQueue2.add(4);
    		System.out.println(myQueue2.poll());
    
    
    	}

1.  数组实现队列:

/**
     * Class: 基础数据结构-队列(数组)
     * 实现方式:  1 数组 2 集合arrayList 3 两个栈
     *
     * @Author: wangzhong
     * @Date: 2020-02-10 15:11
     */
    public class MyQueue {
        
    	private int[] array;
    	//指向第一个有效元素
    	private int front;
    	//指向最后一个有效元素的下一个元素
    	private int rear;
    
    	public MyQueue(int[] array, int front, int rear) {
        
    		this.array = array;
    		this.front = front;
    		this.rear = rear;
    	}
    
    	/**
    	 * 是否满
    	 *
    	 * @return
    	 */
    	public boolean isFull() {
        
    		return (rear + 1) % array.length == front;
    	}
    
    	/**
    	 * 是否空
    	 *
    	 * @return
    	 */
    	public boolean isEmpty() {
        
    		return rear == front;
    	}
    
    	/**
    	 * 入队(队尾入队)
    	 */
    	public void enQueue(int value) {
        
    		if (!isFull()) {
        
    			array[rear] = value;
    			rear = (rear + 1) % array.length;
    		}
    	}
    
    	/**
    	 * 出队（队头出队）
    	 */
    	public int outQueue() {
        
    		if (!isEmpty()) {
        
    			int a = array[front];
    			front = (front + 1) % array.length;
    			return a;
    		}
    		return -1;
    	}
    
    	/**
    	 * 遍历
    	 */
    	public void traverse() {
        
    		int a = front;
    		while (a != rear) {
        
    			System.out.print(array[a] + " ");
    			a = (a + 1) % array.length;
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
        
    		MyQueue myQueue = new MyQueue(new int[7], 1, 1);
    		myQueue.enQueue(5);
    		myQueue.enQueue(6);
    		myQueue.enQueue(7);
    		myQueue.traverse();
    		System.out.println(myQueue.isEmpty());
    	}
    }

[Link 1]: https://blog.csdn.net/qq_37220419/article/details/104256319