当前位置：网站首页>栈和队列的基本使用

import java.util.Arrays;

/**
 * 栈的实现
 */
public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[5];
    }

    //压栈
    public void push(int val) {
        if(isFull()) {
            //满了就2倍扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
    }
    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    //出栈,pop 会删除栈元素，peek 获取栈元素，不删除
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("栈为空！");
        }
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("栈为空！");
        }
        int oldVal = this.elem[usedSize-1];
        return oldVal;
    }

    //判断栈是否为空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

}

2.main 函数

import java.util.Stack;

/**
 * 栈，先进后出
 */

public class StackTest {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        //压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        //出栈，pop 是出一个栈顶元素并且在栈中删除
        System.out.println(stack.pop());//6
        // peek 是获取栈顶元素但不删除栈中元素
        System.out.println(stack.peek());//5
        System.out.println(stack.peek());//5
        System.out.println(stack.isEmpty());//false
    }
}

3.运行结果

2.队列(Queue)

2.1 概念

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

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

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

2.2 单链表实现队列

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

单链表实现

/**
 * 队列的实现，使用单链表
 */
class Node {
    public int val;
    public Node next;
    public Node(int val) {
        this.val = val;
    }
}

public class MyQueue {
    public Node head;
    public Node last;

    /**
     * 添加队列元素
     * 使用单链表尾插法
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            last = node;
        }else {
            last.next = node;
            last = last.next;
        }
    }

    /**
     * 出队
     * @return
     */
    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int oldVal = head.val;
        this.head = head.next;
        return oldVal;
    }
    public boolean isEmpty() {
        return this.head == null;
    }

    /**
     * 获取队列元素
     * @return
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
}

main 方法

import java.util.Queue;

public class QueueTest {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        //入队列
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        //获取队列元素
        System.out.println(queue.peek());//1
        //出队
        System.out.println(queue.poll());//1
        System.out.println(queue.poll());//2
        System.out.println(queue.poll());//3

    }
}

效果

2.3 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统在生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

代码

/**
 * 设计循环队列
 */
public class MyCircularQueue {
    public int[] elem;
    public int front;//队头下标
    public int rear;//队尾下标
    public MyCircularQueue(int k) {
        this.elem = new int[k + 1];
    }

    /**
     * 入队
     * @param value
     * @return
     */
    public boolean enQueue(int value) {
        if (isFull()) return false;
        this.elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }

    /**
     * 出队
     * @return
     */
    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front+1) % elem.length;
        return true;
    }

    /**
     * 得到对头元素
     * @return
     */
    public int Front() {
        if (isEmpty()) return -1;
        return elem[front];
    }

    /**
     * 队尾元素
     * @return
     */
    public int Rear() {
        if (isEmpty()) return -1;
        int index = -1;
        if (rear == 0) {
            index = elem.length - 1;
        }else {
            index = rear - 1;
        }
        return elem[index];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        if((this.rear+1) % elem.length == front) {
            return true;
        }
        return false;
    }
}