栈与队列简单剖析

怼烎@ 2022-07-26 00:08 203阅读 0赞

什么是栈？  
和链表的问题一样，熟练掌握了数据结构的基本原理，栈与队列的问题处理起来要容易的多。当然，有些问题也可能相当棘手。、

栈采用了后进先出（LIFO）顺序。

**实现一个栈**

public class Node {
        public Node(Node item) {
            next = item.next;
            data = item.data;
        }
    
        Node next = null;// 指向的下一个链表
    
        public int data;
    }

public class Stack {
        Node top;
    
        Object pop() {
            if (top != null) {
                Object item = top.data;
                top = top.next;
                return item;
            }
            return null;
        }
    
        void push(Node item) {
            Node t = new Node(item);
            t.next = top;
            top = t;
        }
    
        Object peek(){
            return top.data;
        }
    }

队列采用的是先进先出（FIFO）的策略。  
**实现一个队列**  
想要实现一个队列，需要实现两个方法，入队和出队，入队是在队伟插一条数据，出队是在队首拿出来一个。

public class Queue {
        Node first,last;
    
        //入队
        void enqueue(Node item){
            //如果是个空队列，队首和队尾都设置为相同的值
            if(first==null){
                last = new Node(item);
                first = last;
            }else{
                //如果不是空队列，将数据插在队尾
                last.next = new Node(item);
                last = last.next;
            }
        }
    
        //出队
        Node dequeue(){
            //不是空队列，在队首拿出一个
            if(first != null){
                Node item = first;
                first = first.next;
                return item;
            }
            //如果是空队列，返回null
            return null;
        }
    }