数据结构之栈和队列及其Java实现

时间:2021-11-24 17:38:03

        栈和队列是数据结构中非常常见和基础的线性表,在某些场合栈和队列使用很多,因此本篇主要介绍栈和队列,并用Java实现基本的栈和队列,同时用栈和队列相互实现。

        栈:栈是一种基于“后进先出”策略的线性表。在插入时(入栈),最先插入的元素在栈尾,最后插入的元素在栈顶;在删除时(出栈),最后插入的元素先出栈,最先插入的元素最后出栈。由此可见,对栈的插入和删除操作都是在栈顶位置进行的。

        在Java中,提供了一个类Stack<E>来实现栈的这些特性,并提供了一些常用的方法来对栈进行操作。

        Stack<E>源码:

数据结构之栈和队列及其Java实现数据结构之栈和队列及其Java实现
package java.util;
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }
    //入栈
    public E push(E item) {
        addElement(item);
        return item;
    }
    //出栈
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }
    //查看栈顶元素,但不会出栈
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    //判断栈是否为空
    public boolean empty() {
        return size() == 0;
    }
    //在栈中查找某个元素,返回其位置
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}
View Code

        通过源码可以看出,类Stack实际上继承了Vector类,而Vector是一个基于数组的集合类,它里面的元素都存储在“protected Object[] elementData;”这个数组里面,而变量“protected int elementCount;”用于统计数组元素个数。通过上面源码来看Stack类里面的push方法,实际上是通过Vector类里面的addElement(item);方法向数组里添加元素(如下面代码),添加之前先判断数组是不是满了,如果满了先进行扩容操作,防止发生溢出(数组下标越界)。然后将新元素添加到数组elementData,元素个数+1。

    public synchronized void addElement(E obj) {  //向数组里面添加元素
        modCount++;
        ensureCapacityHelper(elementCount + 1);  //当数组填满时,对数组“扩容”,防止溢出
        elementData[elementCount++] = obj;  //数组添加新元素,元素个数加1
    }

        再来看Stack类里面的pop方法,先通过peek方法获取数组最后的元素(len - 1位置),然后通过Vector类里面的removeElementAt(int index);方法将数组末尾的元素置空(null)并使元素个数-1。将数组末尾元素置空的目的是防止发生对象游离。Java的垃圾收集策略是回收所有无法被访问的对象的内存,而我们在执行pop操作时,被弹出的元素的引用仍然存在于数组中,但这个元素实际上已经是一个“孤儿”了,它永远都不会被访问了。但它依然占着内存,Java的垃圾收集器不知道这一点,这种情况又称为内存泄漏。因此将将数组末尾的元素置空(null)可以防止这一情况发生。

        实际上我们也可以通过一个普通的数组来实现栈的操作,下面代码实现了这一点。obj数组存放栈中的元素,index记录元素个数。入栈时数组obj从前往后依次添加元素,每添加一个元素,就判断数组是否满了,如果满了,则扩容为原来的2倍,防止发生溢出(数组下标越界)。扩容时,新建一个容量为原来两倍的新数组,将原来数组中的元素逐个复制到新数组中,然后将新数组赋给原来的数组obj,完成数组扩容。出栈时,数组obj从后往前依次取出元素,获取元素值以后,将数组中出栈元素位置置空(null),避免对象游离,原因如上所述。每出栈一次,判断数组空间的使用率是否小于一半,如果小于一半,则缩小为原来的一半(缩容),减少空间浪费。缩容操作与扩容操作原理类似,不再赘述。代码如下所示:

数据结构之栈和队列及其Java实现数据结构之栈和队列及其Java实现
/*
 * 数组实现栈
 */
public class ArrayToStack {

    private Object[] obj;
    private int index;  //元素个数,注意不是数组长度
    
    public ArrayToStack(){
        obj = new Object[4];  //数组初始容量4
        index = 0;
    }
    //入栈,数组obj从前往后依次添加元素
    public void push(Object obj){
        this.obj[index++] = obj;
        if(index == this.obj.length){  //如果数组满了,则扩容为原来的2倍,防止溢出
            this.obj = resize(this.obj.length);  //将扩容后的数组赋给obj
        }
    }
    //出栈,数组obj从后往前依次取出元素
    public Object pop(){
        if(index == 0) return null;
        Object data = this.obj[index-1];  //先取出出栈元素
        this.obj[index-1] = null;  //将数组中出栈元素位置置空(null),避免对象游离
        index--;
        if(index == this.obj.length/2-1){  //如果数组空间使用率小于一半,则缩小为原来的一半,减少空间浪费
            this.obj = reduce(this.obj.length);  //将缩小后的数组赋给obj
        }
        return data;
    }
    
    public boolean isEmpty(){
        return index == 0;
    }
    //元素个数
    public int size(){
        return index;
    }
    
    public void display(){
        for(int i=0;i<index;i++){
            System.out.print(obj[i]+" ");
        }
        System.out.println();
    }
    //数组扩容
    private final Object[] resize(int size){
        Object[] newobj = new Object[size<<1];  //扩容为原来的2倍
        for(int i=0;i<index;i++){
            newobj[i] = this.obj[i];
        }
        return newobj;
    }
    //数组缩小(缩容)
    private final Object[] reduce(int size){
        Object[] newobj = new Object[size>>1];  //缩小为原来的一半
        for(int i=0;i<index;i++){
            newobj[i] = this.obj[i];
        }
        return newobj;
    }
    
    public static void main(String[] args) {
        ArrayToStack stack = new ArrayToStack();
        //入栈
        stack.push(0);
        stack.push(1);
        stack.push(2);
        System.out.println(stack.obj.length);  //4  数组还未扩容
        stack.push(3);                         //入栈顺序:0、1、2、3
        System.out.println(stack.obj.length);  //8  数组进行了扩容
        System.out.println(stack.isEmpty());   //false
        System.out.println(stack.size());      //4
        stack.display();                       //0 1 2 3
        //出栈
        System.out.println(stack.pop());       //3
        System.out.println(stack.obj.length);  //4  数组进行了缩容
        System.out.println(stack.pop());       //2
        System.out.println(stack.pop());       //1
        System.out.println(stack.pop());       //0  出栈顺序:3、2、1、0
        System.out.println(stack.pop());       //null
        System.out.println(stack.isEmpty());   //true
    }
}
View Code

        除了数组,链表也是实现栈的很好的方式,详情可参考前面一篇“数据结构之链表及其Java实现”中,用单向链表实现栈。

        队列:队列是一种基于“先进先出”策略的线性表。插入操作时(入列),每次都在队尾插入一个新元素;删除操作时(出列),每次都在队头插入一个新元素。由此可见,队列的插入操作是在队尾位置进行的,删除操作是在队头位置进行的。

        Java提供了一个队列接口Queue<E>,但这个接口不太常用,往往通过其他方式实现队列的操作。链表是实现队列的很好的方式,详情可参考前面一篇“数据结构之链表及其Java实现”中,用双端链表实现队列。除此之外,还可以通过两个栈实现队列。

        栈和队列相互实现

        两个栈实现队列:两个栈实现队列的原理,可参考前面一篇“剑指offer题目系列二”中“6、用两个栈实现队列”。下面提供两种方式:一种通过Java提供的Stack类来实现队列,另一种通过上面数组实现的栈来实现队列。

        通过Java提供的Stack类来实现队列,代码如下:

数据结构之栈和队列及其Java实现数据结构之栈和队列及其Java实现
/*
 * 两个栈实现队列
 */
import java.util.Stack;


public class TwoStackToQueue {
    
    private Stack<Object> stack1 = new Stack<Object>();  //存放入列元素
    private Stack<Object> stack2 = new Stack<Object>();  //存放出列元素
    private int size;  //元素数量
    
    public TwoStackToQueue(){
        size = 0;
    }
    
    //入列
    public void appendTail(Object obj){
        stack1.push(obj);  //将新入列的元素存放在stack1
        size++;
    }
    //出列
    public Object deleteHead(){
        if(this.isEmpty()) return null;
        if(stack2.empty()){  //如果stack2不为空,则直接出列
            while(!stack1.empty()){  //如果stack2为空,先将stack1中的元素出栈,同时进入stack2
                stack2.push(stack1.pop());
            }
        }
        size--;
        return stack2.pop();  //stack2出栈,完成出列操作
    }
    
    //判断队列是否为空
    public boolean isEmpty(){
        return stack1.empty() && stack2.empty();
    }
    
    public int size(){
        return size;
    }


    public static void main(String[] args) {
        TwoStackToQueue queue = new TwoStackToQueue();
        System.out.println(queue.isEmpty());     //true
        System.out.println(queue.deleteHead());  //null
        //入列
        queue.appendTail(0);
        queue.appendTail(1);
        queue.appendTail(2);
        queue.appendTail(3);
        System.out.println(queue.isEmpty());     //false
        System.out.println(queue.size());        //4
        //出列
        System.out.println(queue.deleteHead());  //0
        System.out.println(queue.deleteHead());  //1
        System.out.println(queue.deleteHead());  //2
        queue.appendTail(1);
        System.out.println(queue.deleteHead());  //3
        System.out.println(queue.deleteHead());  //1
        System.out.println(queue.isEmpty());     //true
        System.out.println(queue.size());        //0
    }
}
View Code

        通过上面数组实现的栈来实现队列,代码如下:

数据结构之栈和队列及其Java实现数据结构之栈和队列及其Java实现
/*
 * 数组实现队列:利用ArrayToStack类中数组实现的栈来间接实现队列。
 * 直接用数组实现队列也能,但很繁琐,用链表实现队列更容易
 */
public class ArrayToQueue {

    private ArrayToStack stack1 = new ArrayToStack();  //存放入列元素
    private ArrayToStack stack2 = new ArrayToStack();  //存放出列元素
    private int size;  //元素数量
    
    public ArrayToQueue(){
        size = 0;
    }
    
    //入列
    public void appendTail(Object obj){
        stack1.push(obj);  //将新入列的元素存放在stack1
        size++;
    }
    //出列
    public Object deleteHead(){
        if(this.isEmpty()) return null;
        if(stack2.isEmpty()){  //如果stack2不为空,则直接出列
            while(!stack1.isEmpty()){  //如果stack2为空,先将stack1中的元素出栈,同时进入stack2
                stack2.push(stack1.pop());
            }
        }
        size--;
        return stack2.pop();  //stack2出栈,完成出列操作
    }
    
    //判断队列是否为空
    public boolean isEmpty(){
        return stack1.isEmpty() && stack2.isEmpty();
    }
    
    public int size(){
        return size;
    }


    public static void main(String[] args) {
        TwoStackToQueue queue = new TwoStackToQueue();
        System.out.println(queue.isEmpty());     //true
        System.out.println(queue.deleteHead());  //null
        //入列
        queue.appendTail(0);
        queue.appendTail(1);
        queue.appendTail(2);
        queue.appendTail(3);
        System.out.println(queue.isEmpty());     //false
        System.out.println(queue.size());        //4
        //出列
        System.out.println(queue.deleteHead());  //0
        System.out.println(queue.deleteHead());  //1
        System.out.println(queue.deleteHead());  //2
        queue.appendTail(1);
        System.out.println(queue.deleteHead());  //3
        System.out.println(queue.deleteHead());  //1
        System.out.println(queue.isEmpty());     //true
        System.out.println(queue.size());        //0
    }
}
View Code

        两个队列实现栈:除了两个栈可以实现队列以外,反过来,两个队列也可以实现一个栈。定义两个队列que1、que2,size变量记录元素数量。入栈时,将新入栈的元素放入que1;出栈时,que1、que2交替进行:如果que1不为空,将que1除队尾最后一个元素外的其余元素出列,放入que2中,然后将que1队尾最后一个元素返回(出列),完成出栈操作,此时que1为空;如果que2不为空,将que2除队尾最后一个元素外的其余元素出列,放入que1中,然后将que2队尾最后一个元素返回(出列),完成出栈操作,此时que2为空。

        下面代码利用上面“通过Java提供的Stack类来实现队列”的两个队列,来实现栈。

数据结构之栈和队列及其Java实现数据结构之栈和队列及其Java实现
/*
 * 两个队列实现栈
 */
public class TwoQueueToStack {

    TwoStackToQueue que1 = new TwoStackToQueue();
    TwoStackToQueue que2 = new TwoStackToQueue();
    private int size;  //元素数量
    
    
    public TwoQueueToStack(){
        size = 0;
    }
    //入栈
    public void pushStack(Object obj){
        que1.appendTail(obj);  //将新入栈的元素放入que1
        size++;
    }
    
    //出栈,出栈时que1、que2交替进行
    public Object popStack(){
        if(this.isEmptyStack()) return null;
        if(!que1.isEmpty()){
            while(que1.size() != 1){  //将que1除队尾最后一个元素外的其余元素出列,放入que2中
                que2.appendTail(que1.deleteHead());
            }
            size--;
            return que1.deleteHead();  //que1队尾最后一个元素出列,完成出栈操作,此时que1为空
        }else{
            while(que2.size() != 1){  //将que2除队尾最后一个元素外的其余元素出列,放入que1中
                que1.appendTail(que2.deleteHead());
            }
            size--;
            return que2.deleteHead();  //que2队尾最后一个元素出列,完成出栈操作,此时que2为空
        }
    }
    
    public boolean isEmptyStack(){
        return que1.size()==0 && que2.size()==0;
    }
    
    public int size(){
        return size;
    }
    
    public static void main(String[] args) {
        TwoQueueToStack stack = new TwoQueueToStack();
        System.out.println(stack.isEmptyStack());  //true
        System.out.println(stack.popStack());      //null
        //入栈
        stack.pushStack(0);
        stack.pushStack(1);
        stack.pushStack(2);
        stack.pushStack(3);
        System.out.println(stack.isEmptyStack());  //false
        System.out.println(stack.size());          //4
        //出栈
        System.out.println(stack.popStack());      //3
        System.out.println(stack.popStack());      //2
        System.out.println(stack.popStack());      //1
        stack.pushStack(2);
        System.out.println(stack.popStack());      //2
        System.out.println(stack.popStack());      //0
        System.out.println(stack.isEmptyStack());  //true
        System.out.println(stack.size());          //0
    }
}
View Code

 

        转载请注明出处 http://www.cnblogs.com/Y-oung/p/8893829.html

        工作、学习、交流或有任何疑问,请联系邮箱:yy1340128046@163.com  微信:yy1340128046