Java实现栈和队列

电玩女神 2022-09-26 03:55 180阅读 0赞

JAVA面试题编程题：

请用JAVA实现两个类，分别实现堆栈（Stack)和队列（Queue）操作

package com.lcx.interview;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /**
     * 29. 请用JAVA实现两个类，分别实现堆栈（Stack)和队列（Queue）操作。 堆栈:
     * 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 栈为后进先出（Last In First Out）的线性表，简称为 LIFO 表。
     * 一般用List来当模拟容器，常用方法 是否有数据、弹出pop数据、压入push数据、数据量
     * 
     * 队列: 是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，
     * 而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。 进行插入操作的端称为队尾，进行删除操作的端称为队头。 模拟
     * 
     * @author 
     */
    public class Interview_29_StackQueue {
    
    	public static void main(String[] args) {
    		System.out.println("--------------------堆栈--------------------");
    		MyStack<Integer> stack = new MyStack<Integer>();
    		System.out.println("刚创建堆栈时，stack.isEmpty():" + stack.isEmpty() +",stack.size():" + stack.size());
    		stack.push(1);
    		stack.push(2);
    		stack.push(3);
    		System.out.println("push 3个元素时，stack.size():" + stack.size() + ",stack.toString()：" + stack.toString());
    		stack.pop();
    		stack.pop();
    		System.out.println("pop 2个元素时，stack.size():" + stack.size() + ",stack.toString()：" + stack.toString());
    
    		System.out.println("--------------------队列--------------------");
    		MyQueue<Integer> queue = new MyQueue<Integer>(5);
    		System.out.println("刚创建堆栈时，queue.isEmpty():" + queue.isEmpty() +",queue.isFull():"+queue.isFull()+ ",queue.size():" + queue.size());
    		for (int i = 0; i < 3; i++) {
    			queue.add(i);
    		}
    		System.out.println("添加3个元素：");
    		System.out.println("queue.getHead():"+queue.getHead()+",queue.getTail()："+queue.getTail()+"，queue.size()："+queue.size());
    		System.out.println(queue);
    		System.out.println("干掉2个元素：");//干掉元素，元素只是不能访问到了，被干掉的元素可以被添加的覆盖
    		queue.remove();queue.remove();
    		System.out.println("queue.getHead():"+queue.getHead()+",queue.getTail()："+queue.getTail()+"，queue.size()："+queue.size());
    		System.out.println(queue);
    		for (int i = 3; i < 7; i++) {
    			queue.add(i);
    		}
    		System.out.println("添加4个元素：");//此时尾指又要从开始出添加元素
    		System.out.println("queue.getHead():"+queue.getHead()+",queue.getTail()："+queue.getTail()+"，queue.size()："+queue.size());
    		System.out.println(queue);
    		
    		System.out.println("干掉4个元素：");//此时尾指又要从开始出添加元素
    		queue.remove();queue.remove();queue.remove();queue.remove();
    		System.out.println("queue.getHead():"+queue.getHead()+",queue.getTail()："+queue.getTail()+"，queue.size()："+queue.size());
    		System.out.println(queue);
    	}
    
    }
    
    class MyStack<E> {
    	private List<E> list;
    
    	public MyStack() {
    		list = new ArrayList<E>();
    	}
    
    	/**
    	 * 栈是否为空
    	 * 
    	 * @return
    	 */
    	public boolean isEmpty() {
    		return list.size() == 0;
    	}
    
    	/**
    	 * 栈内容长度
    	 * 
    	 * @return
    	 */
    	public int size() {
    		return list.size();
    	}
    
    	/**
    	 * 添加元素
    	 * 
    	 * @param e
    	 */
    	public void push(E e) {
    		list.add(e);
    	}
    
    	/**
    	 * 弹出元素
    	 * 
    	 * @return
    	 */
    	public E pop() {
    		if (list.size() > 0) {
    			return list.remove(list.size() - 1);
    		}
    		return null;
    	}
    
    	@Override
    	public String toString() {
    		return Arrays.toString(list.toArray());
    	}
    }
    
    class MyQueue<E> {
    	private int maxSize;// 队列容量
    	private E queue[];// 队列
    	private int head;// 头指针
    	private int tail;// 尾指针
    	private int nItems;// 元素个数
    
    	@SuppressWarnings("unchecked")
    	public MyQueue(int maxSize) {
    		this.maxSize = maxSize;
    		this.queue = (E[]) new Object[maxSize];
    		this.head = 0;// 移除元素一般从下标0开始，头指针指向待移除的元素（也就是移除元素的下标）
    		this.tail = -1;// 一般设为-1，当添加元素后，尾指针数值为当前已经添加的元素的下标位置
    		this.nItems = 0;
    	}
    
    	/**
    	 * 队列是否为空
    	 * 
    	 * @return
    	 */
    	public boolean isEmpty() {
    		return nItems == 0;
    	}
    
    	/**
    	 * 队列是否已满
    	 * 
    	 * @return
    	 */
    	public boolean isFull() {
    		return nItems == queue.length;
    	}
    
    	/**
    	 * 添加从队尾开始
    	 * 
    	 * @param e
    	 */
    	public void add(E e) {
    		if (isFull()) {
    			throw new RuntimeException("队列已满");
    		}
    		// 当队尾指针已经到达数组的末尾，但数组却未填满（数组前面有空缺），此时又从起始位置添加元素
    		if (tail == maxSize - 1) {
    			tail = -1;
    		}
    		queue[++tail] = e;
    		nItems++;
    	}
    
    	/**
    	 * 删除从对头开始
    	 * 
    	 * @return
    	 */
    	public E remove() {
    		if (isEmpty()) {
    			throw new RuntimeException("队列已空");
    		}
    		// 当对头指针到达数组末尾，但数组个数却不为空（说明数组前面还有元素），此时又从起始位置删除元素
    		if (head == maxSize) {
    			head = 0;
    		}
    		nItems--;
    		return queue[head++];
    	}
    
    	/**
    	 * 获取对头元素
    	 * 
    	 * @return
    	 */
    	public E getHead() {
    		return queue[head];
    	}
    
    	/**
    	 * 获取队尾元素
    	 * 
    	 * @return
    	 */
    	public E getTail() {
    		return queue[tail];
    	}
    
    	/**
    	 * 队列元素个数
    	 * 
    	 * @return
    	 */
    	public int size() {
    		return nItems;
    	}
    
    	@Override
    	public String toString() {
    		return Arrays.toString(queue);
    	}
    
    }

结果截图：

![Center][]

[Center]: /images/20220717/ad2a9893fdfd4a27a660aef31136c964.png