使用数组实现栈和循环队列(JAVA语言）

╰半夏微凉° 2022-05-17 07:22 215阅读 0赞

这篇文章将讲述两个问题。一是如何使用数组实现一个栈，栈的大小可以伸缩。二是使用数组实现一个队列，为了充分的利用数组的空间，这里实现一个循环，构成循环队列。

（1）基于数组实现栈

package com.datastructure.stack;
    import java.util.*;
    
    public class MyStack<T> {
    
    	private Object[] array=null;
    	private int capality;
    	private final int defaultsize=10;
    	private int size=0;
    	private int top=-1;
    	
    	public MyStack()
    	{
    		this.capality=this.defaultsize;
    		this.array=new Object[this.capality];
    		this.size=0;
    	}
    	
    	public MyStack(int capality)
    	{
    		this.capality=capality;
    		this.array=new Object[capality];
    		this.size=0;
    	}
    	
    	public boolean isEmpty()
    	{
    		return size==0;
    	}
    	
    	public int size()
    	{
    		return this.size;
    	}
    	
    	public void push(T obj)
    	{
    		if(this.size<this.capality)
    		{
    			this.top++;
    			this.array[top]=obj;
    			this.size++;
    		}else
    		{
    			enableCapality();
    			push(obj);
    		}
    	}
    	
    	private void enableCapality()
    	{
    		this.capality=this.capality*2;
    		Object[] newarray=new Object[this.capality];
    		System.arraycopy(array, 0, newarray, 0, this.size);
    		this.array=newarray;
    	}
    	
    	public T pop()
    	{
    		if(isEmpty())
    		{
    			try {
    				throw new Exception("栈为空！");
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		T temp=(T)array[this.top];
    		array[this.top]=null;
    		this.top--;
    		this.size--;
    		return temp;
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		MyStack<Integer> stack=new MyStack<Integer>();
    		stack.push(1);
    		stack.push(5);
    		stack.push(2);
    		stack.push(4);
    		stack.push(3);
    		while(!stack.isEmpty())
    		{
    			System.out.println(stack.pop());
    		}
    	}
    
    }

运行结果如下所示：

3
    4
    2
    5
    1

（2）基于数组实现循环队列

package com.datastructure.stack;
    
    public class MyQueue {
    	
    	private Object[] array=null;
    	private int size;
    	private int front;
    	private int back;
    	private boolean beginflag=true;
    	private boolean endflag=false;
    	
    	public MyQueue(int size)
    	{
    		array=new Object[size];
    		this.size=size;
    		front=0;
    		back=0;
    	}
    	
    	public MyQueue()
    	{
    		this(10);
    	}
    	
    	public void enqueue(Object obj)
    	{
    		if(isFull())
    		{
    			try {
    				throw new Exception("队列已满！");
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		array[back]=obj;
    		back=(back+1)%size;
    	}
    	
    	public Object dequeue()
    	{
    		if(isEmpty())
    			try {
    				throw new Exception("队列为空！");
    			} catch (Exception e) {
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		Object temp=array[front];
    		array[front]=null;
    		front=(front+1)%size;
    		return temp;
    	}
    	
    	public boolean isEmpty()
    	{
    		if(front==back)
    		{
    			if(!endflag)
    			{
    				endflag=true;
    				return false;
    			}
    			return true;
    		}
    		else
    			return false;
    	}
    	
    	private boolean isFull()
    	{
    		if((back+1)%size==front)
    		{
    			if(beginflag)
    				{beginflag=false;return false;}
    			return true;
    		}else
    		{
    			return false;
    		}
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		MyQueue queue=new MyQueue(5);
    		queue.enqueue(1);
    		queue.enqueue(2);
    		queue.enqueue(3);
    		queue.enqueue(4);
    		queue.enqueue(5);
    		System.out.println(queue.dequeue());
    		System.out.println(queue.dequeue());
    		System.out.println(queue.dequeue());
    		queue.enqueue(5);
    		System.out.println(queue.dequeue());
    		System.out.println(queue.dequeue());
    		System.out.println(queue.dequeue());
    		queue.enqueue(6);
    		System.out.println(queue.dequeue());
    	}
    
    }

运行结果如下所示：

1
    2
    3
    4
    5
    5
    6