亲宝软件园·资讯

展开

Java 栈和基础队列

Word码鸭 人气:0

栈和队列:都是线性表,都是基于List基础上的实现

线性表:数组,链表,字符串,栈,队列

元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素

栈(stack)

一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

20191212190125865.gif (1920×1080)

20191212204731172.gif (1920×1080)

栈支持的三个核心操作:

栈的常见实际应用:

栈的实现

栈是一种线性表,所以实现它即可使用数组,也可以使用链表

在数组尾部进行删除和插入的时间复杂度为O(1),所以用数组实现栈是我们的首选

实现代码:

//基于数组实现的栈
public class MyStack<E> {
    private int size;//数组长度
    //实际存储数据的动态数组
    private List<E> data = new ArrayList<>();
    
    //入栈,默认尾插
    public void push(E val){
        data.add(val);
        size ++;
    }
    
    //弹出栈顶元素,返回栈顶的值
    public E pop(){
        if(isEmpty()){
            //栈为空
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //删元素
       E val =  data.remove(size-1);
        size--;
        return val;
        //上面三句等同于return data.remove(size-1);
    }
    
    //返回栈顶元素,但不出栈
    public E peek(){
        if(isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek");
        }
        return data.get(size-1);
    }
    
    // 判断当前栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data.get(i));
            if (i != size - 1) {
                // 此时还没到栈顶,还没到数组末尾
                sb.append(", ");
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}
 
//--------------------------
//测试类·
public class StackTest {
    public static void main(String[] args) {
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(3);
        myStack.push(5);
        System.out.println(myStack);
        System.out.println(myStack.pop());//删除栈顶
        System.out.println(myStack.peek());//输出栈顶,此时栈顶为3
        System.out.println(myStack.isEmpty());
    }
}

//输出结果:
[1, 3, 5] top
5
3
false

队列

只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列遵循先进先出FIFO(First In First Out)的原则 :进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头

其实队列的定义很简单,就相当于我们现实生活的排队购物,先排队的人先结账,也就先离开

队列的子类比栈要复杂一些,它有:

无论是哪种队列,都必须支持三个核心操作:

基础队列的实现 

由于队列是从队尾插入,队首出队,而在数组头部删除的时间复杂度为O(n),此时我们用链表会更好一些。而且无论实现哪种队列都需要覆写三个基本操作,因此我们将队列设计为接口

实现代码:

public interface Queue<E> {
    // 入队
    void offer(E val);
    // 出队
    E poll();
    // 返回队首元素
    E peek();
    // 判断队列是否为空
    boolean isEmpty();
}
 
 //基于链表实现的基础队列
public class MyQueue<E> implements Queue<E> {
    // 链表的每个节点
    // ------------------------------
    //内部类
    private class Node {
        E val;
        Node next;
        public Node(E val) {
            this.val = val;
        }
    }
    // ------------------------------
    // 当前队列中的元素个数
    private int size;
    // 队首
    private Node head;
    // 队尾
    private Node tail;
    @Override
    public void offer(E val) {
        Node node = new Node(val);
        if (head == null) {
            // 此时链表为空
            head = tail = node;
        }else {
            tail.next = node;
            tail = node;
        }
        size ++;
    }
 
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        E val = head.val;
        Node node = head;
        head = head.next;
        // 将原来头节点脱钩
        node.next = null;
        size --;
        return val;
    }
 
    @Override
    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        // 链表的遍历
        for (Node x = head;x != null;x = x.next) {
            sb.append(x.val);
            if (x.next != null) {
                // 还没走到链表尾部
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
 
//测试类
public class QueueTest {
    public static void main(String[] args) {
        Queue<Integer> queue = new MyQueue<>();
        queue.offer(1);
        queue.offer(3);
        queue.offer(5);
        System.out.println(queue);
    }
}

作为初学者,我们不能小瞧任何简单的数据结构与算法,基础的数据结构往往作为高阶数据结构的一部分来应用,万丈高楼平地起,平时要多加练习,我们一起加油!

加载全部内容

相关教程
猜你喜欢
用户评论