数据结构 -栈和队列(Java实现)

一. 栈的概念

��       栈是特殊的线性表,其只允许在固定一端进行插入和删除元素.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底. 栈中元素遵守后进先出原则.

        压栈: 栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶.

        出栈: 栈的删除操作叫做出栈.出数据在栈顶.

二.  栈的创建和方法

        1. 栈的创建和方法

                在创建和使用栈的过程中，需要创建一个空白的栈，对栈进行数据元素的压栈和出栈操作，判断栈中元素是否为空。由于Java语法已经定义了这些方法，因此我们在写代码时只需要直接调用这些方法即可。

2.栈的代码实现(Java)

1. 栈的基本算法

(1) 栈的初始化

    public int[] elem;    public int usedSize;  //默认为0    public static final int DEFAULT_CAPACITY = 10;    public MyStack(){  //构造方法        this.elem = new int[DEFAULT_CAPACITY]; //默认10个元素空间    }

 (2) 入栈

//把元素放入栈(压栈)    public void push(int val){        //先检查栈空间是否已满        if(isFull()){            this.elem = Arrays.copyOf(elem,2*elem.length); //2倍扩容        }        elem[usedSize++] = val;  //元素放在usedsize位置并++    }

(3) 是否栈满

public boolean isFull(){        return usedSize == elem.length;  //记录元素个数和数组长度一样说明满了    }

(4) 出栈

出栈操作是usedsize减1,实际上元素还是存在于栈中,下次入栈会直接覆盖

public int pop(){  //出栈        if(isEmpty()){            throw new EmptyStackException("栈为空");        }        int val = elem[usedSize-1];        usedSize--;        return val;    }

(5) 获取栈顶元素

    public boolean isEmpty(){  //判断栈空间是否为0        return usedSize == 0;    }    public int peek(){  //获取栈顶元素        if(isEmpty()){            throw new EmptyStackException("栈为空");        }        int val = elem[usedSize-1];        return val;    }

三. 队列(Queue)

3.1 队列的概念

队列: 只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出,

入队列: 进行插入操作的一端称为队尾

出队列: 进行删除操作的一端称为队头

3.2 队列的常见操作

在Java中,Queue是个接口,底层是通过链表实现的.

 

 注意: Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口.

3.3 队列的模拟实现

队列的模拟实现可采用顺序结构或者链式结构，上面我们已经说过队列采用链式结构比顺序结构效果较好，因此我们这里用双向链表来模拟实现队列。

3.3.1 队列的创建

    static class ListNode{        public int val;  //元素值        public ListNode prv;  //前驱        public ListNode next;  //后继        public ListNode(int val) {            this.val = val;        }  //构造方法    }    public ListNode head;  //定义队列的队头    public ListNode last;  //定义队列的队尾

3.3.2 队列的入队

    public void offer(int val){        ListNode node = new ListNode(val);  //创建一个新的结点把val放进去        if(head == null){  //队列如果为空,队头和队尾都指向插入的结点            head = last = node;        }else {            last.next = node;  //尾插,最后一个结点指向新节点            node.prv = last;   //新结点的前驱指向队列的最后一个结点            last = node;  //把新结点设为队尾        }    }

3.3.3 队列的出队 

    //出队    public int poll(){        if(head == null){  //队列为空时            return -1;        }        int val = -1;        if(head.next == head){  //队列只有一个结点            head = null;            last = null;            return val;        }        val = head.val;  //拿到队头元素的值        head = head.next;  //让队头指向队头的下一个        head.prv = null;  //把队头的前驱设为空        return val;  //返回出队前队头元素的值    }

3.4 循环队列

解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针Q->front = maxsize-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

• 初始时：Q->front = Q->rear=0
• 队首指针进1：Q->front = (Q->front + 1) % MAXSIZE
• 队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE
• 队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE

  出队入队时，指针都按照顺时针方向前进1，如下图所示：

  那么在队列中判断队空和队满的条件是什么?

  显然可见,判断队列为空的条件是: Q->front == Q->rear

  为了区分队列还是队满的情况,有三种处理方式:  (重点是第一种)

  (1) 牺牲一个单元来判断队空还是队满,入队时少用一个单元. 约定以“队头指针在队尾指针的下一位置作为队满的标志”

  • 队满条件： (Q->rear + 1)%Maxsize == Q->front
  • 队空条件： Q->front == Q->rear
  • 队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize

    (2) 使用计数的方法来判断队列是否已满

    (3) 增设一个boolean flag标记,以区分队满还是队空,flag等于false,若因删除导致 Q->front == Q->rear ，则为队空；flag 等于 true 时，若因插入导致 Q ->front == Q->rear ，则为队满 

     3.4.1 循环队列的常见基本算法

    (1) 队列存储结构

        public int[] elem;  //有int型的数组    public int front;   //队头索引,默认是0    public int rear;    //队尾    

    (2) 循环队列的初始化

        public MyCircularQueue(int k) {        elem = new int[k];  //new一个,给k大小    }

    (3) 检查循环队列是否已满

        //判断是否满了    public boolean isFull() {        return (rear + 1) % elem.length == front;  //队尾+1对总数取模等于队头就说明队列满了    }  

    (4) 循环队列入队

        //入队操作    public boolean enQueue(int value) {        //如果满了,就不许再添加        if (isFull()) {            return false;        }        elem[rear] = value;        rear = (rear + 1) % elem.length;  //rear 向后移动一位        return true;    }

    (5) 循环队列出队(删除队头)

        //删除对头操作    public boolean deQueue() {        if (isEmpty()) {            return false;        }        front = (front + 1) % elem.length;  //和队尾删除一样        return true;    }

    (6) 得到队头元素,不删除

        //得到对头元素,不删除    public int Front() {        if (isEmpty()) {  //如果是空,返回-1            return -1;        }        return elem[front];    }

    (7) 得到队尾元素,不删除 (有特殊情况)

     队尾结点在下标0位置时,直接用队列长度减一得到队尾所在的下标

        //得到队尾元素,    //有特殊情况    public int Rear() {        if (isEmpty()) {  //如果是空,返回-1            return -1;        }        int index = (rear == 0) ? elem.length - 1 : rear - 1;        return elem[index];    }

    总结：

           栈和队列是数据结构知识的基础知识，因此我们在学习数据结构的时候需要牢牢记住栈和队列的实现原理以及如何去调用他们各自对应的方法，大家在学习栈和队列的时候可以多敲敲代码来加深理解