精华内容
下载资源
问答
  • 是一种基于后进先出(LIFO)策略的集合类型。当邮件在桌上放成一叠时,使用的就是。新邮件会放在最上面,当你要看邮件时,会一封一封从上到下阅读。的顶部称为栈顶,所有操作都在...23 /**4 * 链表实现栈5 * ...

    是一种基于后进先出(LIFO)策略的集合类型。当邮件在桌上放成一叠时,使用的就是栈。新邮件会放在最上面,当你要看邮件时,会一封一封从上到下阅读。栈的顶部称为栈顶,所有操作都在栈顶完成。

    前面提到的新邮件,就是在栈顶入栈(push),阅读的时候从栈顶取出一封就是出栈(pop)。就像下面这个图一样,你不能从最下面直接拿一封信出来。

    512eb14d073c2a25e4cbabf906bc92e7.png

    1 package ABAB;

    2

    3 /**

    4 * 链表实现栈

    5 * @param

    6 */

    7 public class Stack {

    8

    9 private Node first;

    10 private Integer N = 0;

    11

    12 private class Node {

    13 Item item;

    14 Node next;

    15

    16 public Node(Item i) {

    17 this.item = i;

    18 this.next = null;

    19 }

    20 }

    21

    22 public boolean isEmpty() { return N == 0; }

    23

    24 public int size() { return N; }

    25

    26 /**

    27 * 进栈

    28 *

    29 * @param i

    30 */

    31 public void push(Item i) {

    32 Node node = new Node(i);

    33 if (first == null) {

    34 first = node;

    35 N++;

    36 return;

    37 }

    38 Node oldFirst = first;

    39 first = node;

    40 first.next = oldFirst;

    41 N++;

    42 }

    43

    44 /**

    45 * 获取栈顶元素

    46 *

    47 * @return

    48 */

    49 public Item peek() {

    50 if (first == null)

    51 return null;

    52 return first.item;

    53 }

    54

    55 /**

    56 * 出栈

    57 *

    58 * @return

    59 */

    60 public Item pop() {

    61 if (isEmpty())

    62 return null;

    63 Item item = first.item;

    64 first = first.next;

    65 N--;

    66 return item;

    67 }

    68

    69 }

    队列

    队列是一种基于先进先出(FIFO)策略的集合类型。例如排队上车,先排队的人可以先上车。

    队列的链表实现中有两个指针,一个指向队头,一个指向队尾。当有新的元素进入时,新元素被放在队尾。当要出队时,从队头弹出元素,并且将队头后移。

    1 package ABAB;

    2

    3 /**

    4 * 链表实现队列

    5 * @param

    6 */

    7 public class Queue {

    8

    9 private Node first;

    10 private Node last;

    11 private int N = 0;

    12 private class Node{

    13 Item item;

    14 Node next;

    15 public Node(Item i){

    16 this.item = i;

    17 this.next = null;

    18 }

    19 }

    20

    21 public boolean isEmpty(){return N == 0;};

    22 public int size(){return N;}

    23

    24 /**

    25 * 入队

    26 * @param item

    27 */

    28 public void enqueue(Item item){

    29 Node node = new Node(item);

    30 Node oldLast = last;

    31 last = node;

    32 if(isEmpty())

    33 first = last;

    34 else

    35 oldLast.next = last;

    36 N++;

    37 }

    38

    39 /**

    40 * 出队

    41 * @return

    42 */

    43 public Item dequeue(){

    44 Item item;

    45 if(isEmpty())

    46 return null;

    47 item = first.item;

    48 first = first.next;

    49 N--;

    50 return item;

    51 }

    52

    53 /**

    54 * 获取队首元素

    55 * @return

    56 */

    57 public Item peek(){

    58 if(isEmpty())

    59 return null;

    60 return first.item;

    61 }

    62

    63 }

    标签:Node,Java,Item,队列,链表,item,return,public,first

    来源: https://www.cnblogs.com/ELAIRS/p/12131659.html

    展开全文
  • 主要介绍了Java数据结构之链表队列、树的实现方法,结合实例形式分析了Java数据结构中链表队列、树的功能、定义及使用方法,需要的朋友可以参考下
  • Java如何实现栈和队列

    千次阅读 2019-07-03 15:38:52
    Java如何实现栈和队列 (stack)是一种后进先出(LIFO)的集合类型, 即后来添加的数据会先被删除。 可以将其类比于下面文件的取放操作:新到的文件会被先取走,这使得每次取走的文件都是最新的。 可以用...

    Java如何实现栈和队列

    栈(stack)是一种后进先出(LIFO)的集合类型, 即后来添加的数据会先被删除。
    在这里插入图片描述
    可以将其类比于下面文件的取放操作:新到的文件会被先取走,这使得每次取走的文件都是最新的。
    在这里插入图片描述
    栈可以用数组或者队列去实现
    下面要实现的栈的API如下图所示:
    在这里插入图片描述

    用数组实现栈

    下面我们通过数组实现一个指定了初始容量,但随着元素的增加能够动态地扩张容量的栈。注意:因为数组指定大小后不可改变, 所以我们要定义自动扩大栈容量的操作**

    public class ArrayStack<Item> {
      // 栈元素的总数
      private int N = 0;
      // 存放栈元素的数组
      private Item [] items;
      public ArrayStack (int M) {
        items = (Item[]) new Object[M];
      }
      /**
       * @description: 调整栈的大小
       */
      private void resize (int max) {
        Item [] temp = (Item [])new Object[max];
        for (int i =0;i<items.length;i++) {
          temp[i] = items[i];
        }
        items = temp;
      }
      /**
       * @description: 向栈顶插入元素
       */
      public void push (Item item) {
        // 当栈满了的时候, 将栈的数组大小扩大为原来两倍
        if (N==items.length) resize(2*N);
        items[N++] = item;
      }
      /**
       * @description: 从栈顶删除元素,并将删除的元素返回
       */
      public Item pop () {
        // 当栈还是空的时候, 不删除并且返回空
        if(isEmpty()) return null;
        // 保存将要被删除的元素
        Item i = items[N-1];
        // 将该元素删除
        items[N-1] = null;
        // 栈的长度减1
        N--;
        return i;
      }
    
      /**
       * @description: 判断栈是否为空
       */
      public boolean isEmpty () {
        return N == 0;
      }
      /**
       * @description: 返回栈的大小
       */
      public int size () {
        return N;
      }
    
      public static void main (String args []) {
        // 开始时指定栈的容量为2
        ArrayStack<Integer> stack = new ArrayStack<>(2);
        // 向栈顶依次添加3个元素
        stack.push(1);
        stack.push(2);
        stack.push(3);
        // 添加3后栈的容量自动扩大了
        // 依次从栈顶删除3个元素
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
      }
    }
    

    输出:

    3
    2
    1
    

    用链表实现栈

    下面展示用链表实现的栈的代码, 注意:添加和删除操作都是在链表的头部进行的**

    public class LinkedListStack<Item> {
      // 栈中元素的总数
      private int N = 0;
      // 链表头元素
      private Node front;
      // 内部结点类
      private class Node {
        Item item;
        Node next;
      }
      /**
       * @description: 向栈顶插入元素
       */
      public void push (Item item) {
        Node oldFront = front;
        // 向链表头部插入新的结点
        front = new Node();
        front.item = item;
        // 将新头结点的next指针指向旧的头结点
        front.next = oldFront;
        // 栈的长度加1
        N++;
      }
      /**
       * @description: 向栈顶删除元素,并将删除的元素返回
       */
      public Item pop () {
        // 当栈还是空的时候, 不删除并且返回空
        if(isEmpty()) return null;
        // 保存待删除的项以便返回
        Item item = front.item;
        // 删除原头结点
        front = front.next;
        // 栈的长度减1
        N--;
        return item;
      }
      /**
       * @description: 判断栈是否为空
       */
      public boolean isEmpty () {
        return N == 0;
      }
      /**
       * @description: 返回栈的大小
       */
      public int size () {
        return N;
      }
    
      public static void main (String args []) {
        // 创建栈
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        // 向栈顶依次添加3个元素
        stack.push(1);
        stack.push(2);
        stack.push(3);
        // 依次从栈顶删除3个元素
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
      }
    }
    

    输出:

    3
    2
    1
    

    队列(queue)

    队列属于一种遵循先进先出(FIFO)原则的集合类型,可以将其类比为生活中一些以公平性为原则的服务场景:排成一排的客户等待服务,等待最久即最先入列的客户应该最先提供服务(出列)
    在这里插入图片描述
    实现队列也有两种方式,一种是链表, 另一种是循环数组
    队列和栈在实现上的不同

    • 栈遵循后进先出的原则,所以要在数组或链表同一端做添加和删除操作
    • 队列遵循先进先出的原则, 所以要在数组或链表的两端分别做插入和删除的操作

    我们要实现的队列API如下图所示:
    在这里插入图片描述

    通过链表实现队列

    public class LinkedListQueue<Item> {
      // 链表中的结点数目
      private int N = 0;
      // 链表头结点
      private Node front = null;
      // 链表尾结点
      private Node rear = null;
      // 结点内部类
      private class Node {
        Item item;
        Node next;
      }
      /**
       * @description: 元素入列(在链表尾部添加)
       */
      public void enqueue (Item item) {
        Node oldRear = rear;
        rear = new Node();
        rear.item = item;
        if (isEmpty()) front = rear;
        else           oldRear.next = rear;
        N++;
      }
      /**
       * @description: 元素出列(在链表头部删除)
       */
      public Item dequeue () {
        if(isEmpty()) return null;
        Item item = front.item;
        front = front.next;
        N--;
        if(isEmpty()) rear = null;
        return item;
      }
      /**
       * @description: 判断队列是否为空
       */
      public boolean isEmpty () {
        return N == 0;
      }
      /**
       * @description: 返回队列长度
       */
      public int size () {
        return N;
      }
    
      public static void main (String args []) {
        LinkedListQueue<String> queue = new LinkedListQueue<>();
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.enqueue("D");
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
      }
    }
    

    输出:

    A
    B
    C
    D
    

    头部删除-尾部添加 OR 头部添加-尾部删除?
    在上面的代码中,我们是通过在链表尾部添加结点,在链表头部删除结点的操作实现队列, 那能不能通过在链表头部添加结点,在链表尾部删除结点的方式实现队列呢?这是可以的,但并不是一个合适的做法,因为如果这样操作,在单向链表的条件下,需要将链表从头到尾迭代一遍才能实现删除操作,而我们通过上面的“头部删除-尾部添加”就能避免这种开销。

    通过在链表头部添加结点,在链表尾部删除结点实现队列(不推荐)

    /**
       * @description: 元素入列(在链表头部添加)
       */
      public void enqueue (Item item) {
        Node oldFront = front;
        front = new Node();
        front.item = item;
        front.next = oldFront;
        if (isEmpty()) rear = front;
        N++;
      }
      /**
       * @description: 元素出列(在链表尾部删除)
       */
      public Item dequeue () {
        if (isEmpty()) return null;
        if (size()==1) {
          Item item = rear.item;
          front = null;
          rear = null;
          N--;
          return item;
        }
        Node x = front;
        while (!x.next.equals(rear)) {
          x=x.next;
        }
        Item item = x.next.item;
        x.next = null;
        rear = x;
        N--;
        return item;
      }
    

    通过循环数组实现队列
    除了链表之外, 另外一种实现队列的方式是循环数组。

    为什么需要循环数组?
    因为仅靠普通的数组实现队列可能会导致一个问题:数组大量空位元素得不到利用。
    例如下图所示, 在数组的实现方式中,我们会使用front和rear两个指针跟踪队列头部元素和尾部元素的位置,在动态的出列和入列操作中它们的位置会不断发生变化,随着出列操作fron指针t会不断后移(a->b->c->d), 当front和rear到达图d的状态时,我们发现:front前面的元素有一大段因为出列而腾出的空的元素没有得到利用,而此时又无法继续入列了(rear指针到达数组尾部,再次入列将导致数组越界的错误)
    在这里插入图片描述
    现在我们有一个方式可以解决这个问题:将数组的头部和尾部连在一起,构成一个循环数组:
    在这里插入图片描述
    代码如下图所示, 可以看到,实现循环的关键是使用的一个取余数的操作,使得指针在移动到数组尾部的时候,能够重新移动到数组的头部:

    public class CircleArrayQueue<Item> {
      // 队列元素总数
      private int N = 0;
      // 数组长度
      private int M;
      // 队列头部元素指针
      private int front = 0;
      // 队列尾部元素指针
      private int rear = 0;
      private Item [] items;
      public CircleArrayQueue (int M) {
        this.M = M;
        items = (Item [])new Object[M];
      }
      /**
       * @description: 入列操作
       */
      public void enqueue (Item item) {
        // 当队列为空时, 不能进行入列操作
        if (isFull()) return;
        // 向队列尾部插入元素
        items[rear] = item;
        // 用数组长度M取余, 使得rear到达数组尾部时能返回数组头部
        rear = (rear + 1) % M;
        // 增加队列长度
        N++;
      }
      /**
       * @description: 出列,并返回被删除项
       */
      public Item dequeue () {
        // 当队列为满时, 不能进行出列操作
        if (isEmpty()) return null;
        // 保存待删除元素, 以待返回
        Item item = items[front];
        // 删除队列头部元素
        items[front] = null;
        // 用数组长度M取余, 使得front到达数组尾部时能返回数组头部
        front = (front + 1) % M;
        // 减少队列长度
        N--;
        // 返回删除元素
        return item;
      }
      /**
       * @description: 判断队列是否满了
       */
      public boolean isFull () {
        return N == M;
      }
      /**
       * @description: 判断队列是否为空
       */
      public boolean isEmpty () {
        return N == 0;
      }
      /**
       * @description: 返回队列元素总数
       */
      public int size () {
        return N;
      }
    
      public static void main (String args []) {
        CircleArrayQueue<Integer> queue = new CircleArrayQueue<>(3);
        // 依次入列三个元素
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        // 依次出列三个元素
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
      }
    }
    

    输出:

    1
    2
    3
    

    判断循环数组的满状态和空状态
    在循环数组的实现中,一个非常重要的操作就是区分数组是处在"满"状态还是“空”状态,因为当front和rear指向同一个元素位置时,既可能处在满状态也可能处在空状态。上面的代码里我们是通过一个表示队列元素总数的变量N去判断的,除此之外,我们也可以通过另外一种不依赖于变量N的方式去判断数组的满和空的状态, 但代价是少用一个元素空间,例如:

    (下面的代码除了isEmpty和isFull外都和上面相同)

    public class CircleArrayQueue2<Item> {
      private int M;
      private int front = 0;
      private int rear = 0;
      private Item [] items;
      public CircleArrayQueue2 (int M) {
        this.M = M;
        items = (Item [])new Object[M];
      }
    
      public void enqueue (Item item) {
        if (isFull()) return;
        items[rear] = item;
        rear = (rear + 1) % M;
      }
    
      public Item dequeue () {
        if (isEmpty()) return null;
        Item item = items[front];
        items[front] = null;
        front = (front + 1) % M;
        return item;
      }
    
      public boolean isFull () {
        return (rear + 1) % M == front;
      }
    
      public boolean isEmpty () {
        return rear == front;
      }
    
      public static void main (String args []) {
        CircleArrayQueue2<Integer> queue = new CircleArrayQueue2<>(3);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
      }
    }
    

    输出:

    1
    2
    null
    

    由输出可看出, 在数组长度为3时, 我们实际上只能有2个元素位置去存储队列元素

    展开全文
  • 实现 // 的基本方法 public interface Stack&lt;E&gt; { void push(E e); E pop(); E peek(); int getSize(); boolean isEmpty(); } // 链表的基本方法的实现 public class LinkedList&...

    栈的实现

    // 栈的基本方法
    public interface Stack<E> {
    
        void push(E e);
    
        E pop();
    
        E peek();
    
        int getSize();
    
        boolean isEmpty();
    }
    // 链表的基本方法的实现
    public class LinkedList<E> {
    
        private Node dummyHead;
        private int size;
    
        private class Node {
            public E e;
            public Node next;
    
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
    
            public Node(E e) {
                this(e, null);
            }
    
            public Node() {
                this(null, null);
            }
    
            @Override
            public String toString() {
                return e.toString();
            }
        }
    
        public LinkedList() {
            dummyHead = new Node(null, null);
            size = 0;
        }
    
        public int getSize() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
    
        /**
         * 添加
         * 不是一个常用的操作
         * @param index
         * @param e
         */
        public void add(int index, E e) {
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed, Illegal index.");
            Node prev = dummyHead;
            for(int i = 0; i < index; i++) prev = prev.next;
            prev.next = new Node(e, prev.next);
            size++;
        }
    
        /**
         * 在链表头部添加数据
         * @param e
         */
        public void addFirst(E e) {
            add(0, e);
        }
    
        /**
         * 在链表末尾添加元素
         * @param e
         */
        public void addList(E e) {
            add(size, e);
        }
    
        /**
         * 获取索引对应的值
         * @param index
         * @return
         */
        public E get(int index) {
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed, Illegal index.");
            Node cur = dummyHead.next;
            for(int i = 0; i < index; i++) cur = cur.next;
            return cur.e;
        }
    
        /**
         * 获取第一个元素
         * @return
         */
        public E getFirst() {
            return get(0);
        }
    
        /**
         * 获取最后一个元素
         * @return
         */
        public E getLast() {
            return get(size-1);
        }
    
        /**
         * 修改第index位置的元素
         * @param index
         * @param e
         */
        public void set(int index, E e) {
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed, Illegal index.");
            Node cur = dummyHead.next;
            for(int i = 0; i < index; i++) cur = cur.next;
            cur.e = e;
        }
    
        /**
         * 遍历链表中的元素
         * @param e
         * @return
         */
        public boolean contains(E e) {
            Node cur = dummyHead.next;
            while(cur != null) {
                if(cur.e.equals(e))
                    return true;
                cur = cur.next;
            }
            return false;
        }
    
    
        /**
         * 删除指定位置的元素
         * @param index
         * @return
         */
        public E remove(int index) {
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed, Illegal index.");
            Node prev = dummyHead;
            for(int i = 0; i < index; i++) prev = prev.next;
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size--;
            return retNode.e;
        }
    
        /**
         * 删除第一个元素
         * @return
         */
        public E removeFirst() {
            return remove(0);
        }
    
        /**
         * 删除最后一个
         * @return
         */
        public E removeLast() {
            return remove(size - 1);
        }
    
    
        /**
         * 遍历链表
         * @return
         */
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            Node cur = dummyHead.next;
            while(cur != null) {
                res.append(cur + "-->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }
        
    }
    // 借助链表实现栈操作
    public class LinkedListStack<E> implements Stack<E> {
    
        private LinkedList<E> list;
    
        public LinkedListStack() {
            list = new LinkedList<>();
        }
    
        /**
         * 入栈
         * @param e
         */
        @Override
        public void push(E e) {
            list.addFirst(e);
        }
    
        /**
         * 出栈
         * @return
         */
        @Override
        public E pop() {
            return list.removeFirst();
        }
    
        /**
         * 获取栈顶元素
         * @return
         */
        @Override
        public E peek() {
            return list.getFirst();
        }
    
        /**
         * 获取栈数量
         * @return
         */
        @Override
        public int getSize() {
            return list.getSize();
        }
    
        /**
         * 判断栈为空
         * @return
         */
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    
        /**
         * 遍历栈元素
         * @return
         */
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Stack top ");
            res.append(list);
            return res.toString();
        }
    
    
        public static void main(String[] args) {
            LinkedListStack<Integer> stack = new LinkedListStack<>();
            for(int i = 0; i < 5; i++) {
                stack.push(i);
                System.out.println(stack);
            }
            stack.pop();
            System.out.println(stack);
        }
    }
    
    

    队列的实现

    // 队列基本操作
    public interface Queue<E> {
    
        int getSize();
    
        boolean isEmpty();
    
        void enqueue(E e);
    
        E dequeue();
    
        E getFront();
    
    }
    // 队列的基本操作
    public class LinkedListQueue<E> implements Queue<E> {
        // 定义的节点
        private class Node {
            public E e;
            public Node next;
    
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
    
            public Node(E e) {
                this(e, null);
            }
    
            public Node() {
                this(null, null);
            }
    
            @Override
            public String toString() {
                return e.toString();
            }
        }
    
        // 定义一个头指针和尾指针
        private Node head, tail;
        private int size;
    
        public LinkedListQueue() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }
    
        /**
         * 获取队列元素的数量
         * @return
         */
        @Override
        public int getSize() {
            return size;
        }
    
        /**
         * 判断队列是否为空
         * @return
         */
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 入队操作
         * @param e
         */
        @Override
        public void enqueue(E e) {
            if(tail == null) {
                tail = new Node(e);
                head = tail;
            }else{
                tail.next = new Node(e);
                tail = tail.next;
            }
            size++;
        }
    
        /**
         * 出队元素
         * @return
         */
        @Override
        public E dequeue() {
            if(isEmpty())
                throw new IllegalArgumentException("不能出队!");
            Node retNode = head;
            head = head.next;
            retNode.next = null;
            if(head == null)
                tail = null;
            size--;
            return retNode.e;
        }
    
        /**
         * 获取队首
         * @return
         */
        @Override
        public E getFront() {
            if(isEmpty())
                throw new IllegalArgumentException("不能出队!");
            return head.e;
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Queue front ");
            Node cur = head;
            while(cur != null){
                res.append(cur + "-->");
                cur = cur.next;
            }
            res.append("NULL tail");
            return res.toString();
        }
    
        public static void main(String[] args) {
            LinkedListQueue<Integer> queue = new LinkedListQueue<>();
            for(int i = 0; i < 10; i++) {
                queue.enqueue(i);
                System.out.println(queue);
                if(i % 3 == 2) {
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }
    
    展开全文
  • 目录 ...二、自定义类实现栈 三、自定义类实现队列 一、自定义类实现链表 1.定义节点的数据类型 public class NodeClass<T> { private T Date; //数据 private NodeClass<T> Next; //...

    本文为转载--原文链接:https://blog.csdn.net/qq_38605328/article/details/101081328

    目录

    一、自定义类实现链表

    二、自定义类实现栈

    三、自定义类实现队列


    一、自定义类实现链表

    1.定义节点的数据类型

    
     
    1. public class NodeClass<T> {
    2. private T Date; //数据
    3. private NodeClass<T> Next; //指针
    4. public T getDate() {
    5. return Date;
    6. }
    7. public void setDate(T date) {
    8. Date = date;
    9. }
    10. public NodeClass<T> getNext() {
    11. return Next;
    12. }
    13. public void setNext(NodeClass<T> next) {
    14. Next = next;
    15. }
    16. @Override
    17. public String toString()
    18. {
    19. return "NodeClass{" +
    20. "data=" + Date +
    21. ", next=" + Next +
    22. '}';
    23. }
    24. }

    2.定义一个学生类

    
     
    1. public class Student {
    2. private String stuName; // 学生姓名
    3. private String stuNum; // 学号
    4. private String stuInfo; // 学生信息
    5. public String getStuName() {
    6. return StuName;
    7. }
    8. public void setStuName(String stuName) {
    9. this.stuName = stuName;
    10. }
    11. public String getStuNum() {
    12. return stuNum;
    13. }
    14. public void setStuNum(String stuNum) {
    15. this.stuNum = stuNum;
    16. }
    17. public String getStuInfo() {
    18. return stuInfo;
    19. }
    20. public void setStuInfo(String stuInfo) {
    21. this.stuInfo = stuInfo;
    22. }
    23. @Override
    24. public String toString() {
    25. return "Student{" +
    26. "stuNum=" + stuNum +
    27. ", name='" + stuName + '\'' +
    28. ", otherInfo='" + stuInfo + '\'' +
    29. '}';
    30. }
    31. }

     3.测试类

    
     
    1. public class StudentLink {
    2. public static void main(String[] args) {
    3. String[] student = new String[] { "阿里巴巴", "腾讯", "百度", "字节跳动"};
    4. NodeClass<Student> head = new NodeClass<Student>();
    5. NodeClass<Student> flag = head;
    6. for( int i = 0; i < student.length; i++) {
    7. Student stu = new Student();
    8. flag.setDate(stu);
    9. stu.setStuName(student[i]);
    10. stu.setStuNum(String.valueOf(i));
    11. stu.setStuInfo( "this is " + student[i]);
    12. if( i < student.length -1) {
    13. flag.setNext( new NodeClass<Student>());
    14. flag = flag.getNext();
    15. }
    16. }
    17. System. out.println(head);
    18. }
    19. }

    4.输出

    NodeClass{data=Student{stuNum=0, name='阿里巴巴', otherInfo='this is 阿里巴巴'}, next=NodeClass{data=Student{stuNum=1, name='腾讯', otherInfo='this is 腾讯'}, next=NodeClass{data=Student{stuNum=2, name='百度', otherInfo='this is 百度'}, next=NodeClass{data=Student{stuNum=3, name='字节跳动', otherInfo='this is 字节跳动'}, next=null}}}}
    
     

    5.手绘:

     

    二、自定义类实现栈

    1.定义栈类

    
     
    1. public class StackClass<T> {
    2. //栈顶元素
    3. private NodeClass<T> head;
    4. public NodeClass<T> gethead() {
    5. return head;
    6. }
    7. public void sethead(NodeClass<T> head) {
    8. this.head = head;
    9. }
    10. /**
    11. * <p>Description:入栈 </p>
    12. * @return
    13. */
    14. public void push(NodeClass<T> push){
    15. if( head == null ){
    16. head = push;
    17. } else{
    18. push.setNext(head);
    19. head = push;
    20. }
    21. }
    22. /**
    23. * <p>Description:出栈 </p>
    24. * @return 栈顶元素
    25. */
    26. public NodeClass<T> pop(){
    27. NodeClass<T> result = head;
    28. if( head != null ){
    29. head = head.getNext();
    30. }
    31. return result;
    32. }
    33. public void read(){
    34. System.out.println(head.toString());
    35. }
    36. }

    2.测试类

    
     
    1. public static void main(String[] args) {
    2. //入栈出栈
    3. String[] studentNames = new String[] {
    4. "百度", "阿里巴巴", "腾讯", "字节跳动", "美团", "滴滴", "网易",
    5. "58同城", "携程", "牛客网"
    6. };
    7. StackClass<Student> stack = new StackClass<Student>();
    8. for( int i = 0; i < studentNames.length; i++) {
    9. NodeClass<Student> flag1 = new NodeClass<Student>();
    10. Student stu = new Student();
    11. flag1.setData(stu);
    12. stu.setStuNum(String.valueOf(i));
    13. stu.setStuName(studentNames[i]);
    14. stu.setStuInfo( "I am the best!");
    15. stack.push(flag1);
    16. if(i == 3 || i == 6) {
    17. NodeClass<Student> result = stack.pop();
    18. if(result == null) {
    19. System. out.println( "空了");
    20. } else {
    21. System. out.println(result.getData().getStuName());
    22. }
    23. }
    24. }
    25. while( true) {
    26. NodeClass<Student> result = stack.pop();
    27. if(result == null) {
    28. System. out.println( "空了");
    29. break;
    30. } else {
    31. System. out.println(result.getData().getStuName());
    32. }
    33. }
    34. }

    3.输出:

    
     
    1. 腾讯
    2. 滴滴
    3. 牛客网
    4. 携程
    5. 58同城
    6. 网易
    7. 美团
    8. 字节跳动
    9. 阿里巴巴
    10. 百度
    11. 空了

     

    三、自定义类实现队列

    1.定义队列类

    
     
    1. public class QueClass<T> {
    2. private NodeClass<T> start; //队首
    3. private NodeClass<T> end; //队尾
    4. public NodeClass<T> getStart() {
    5. return start;
    6. }
    7. public void setStart(NodeClass<T> start) {
    8. this.start = start;
    9. }
    10. public NodeClass<T> getEnd() {
    11. return end;
    12. }
    13. public void setEnd(NodeClass<T> end) {
    14. this.end = end;
    15. }
    16. public void push( NodeClass<T> add ){
    17. if( start == null ){
    18. start = add;
    19. end = start;
    20. } else{
    21. end.setNext(add);
    22. end = end.getNext();
    23. }
    24. }
    25. public NodeClass<T> pop(){
    26. NodeClass<T> result = start;
    27. if( start != null ){
    28. start = start.getNext();
    29. }
    30. return result;
    31. }
    32. public void read(){
    33. System.out.println(start.toString());
    34. }
    35. }

    2.测试类

    
     
    1. public static void main(String[] args) {
    2. //入队出队
    3. String[] studentNames = new String[] {
    4. "百度", "阿里巴巴", "腾讯", "字节跳动", "美团", "滴滴", "网易",
    5. "58同城", "携程", "牛客网"
    6. };
    7. QueClass<Student> que = new QueClass<Student>();
    8. for( int i = 0; i < studentNames.length; i++) {
    9. NodeClass<Student> flag1 = new NodeClass<Student>();
    10. Student stu = new Student();
    11. flag1.setData(stu);
    12. stu.setStuNum(String.valueOf(i));
    13. stu.setStuName(studentNames[i]);
    14. stu.setStuInfo( "I am the best!");
    15. que.push(flag1);
    16. }
    17. while( true) {
    18. NodeClass<Student> result = que.pop();
    19. if(result == null) {
    20. System. out.println( "空了");
    21. break;
    22. } else {
    23. System. out.println(result.getData().getStuName());
    24. }
    25. }
    26. }

    3.输出

    
     
    1. 百度
    2. 阿里巴巴
    3. 腾讯
    4. 字节跳动
    5. 美团
    6. 滴滴
    7. 网易
    8. 58同城
    9. 携程
    10. 牛客网
    11. 空了

    4.手绘:

    展开全文
  • 栈和队列栈栈的操作实现队列队列的操作队列的类型 用一个有味道的例子来说 就是吃了吐,队列就是吃了拉(emmm) == 栈和队列都是基于顺序表链表实现的。== 的操作 的操作: 1、入栈:把元素通过栈顶往...
  • 链表实现栈和队列

    千次阅读 2018-11-03 22:07:06
    在之前的博文中详细介绍了的数组方式实现和队列的数组方式实现学习了链表当然要再实现一波咯! 单链表实现栈 单链表相关代码下载 import javax.management.RuntimeErrorException; /** * 使用链表实现栈 * @...
  • 前面我们介绍了队列的 ADT,并利用数组加以实现。遗憾的是,尽管这种实现简单明了,但由于数组长度必须固定,在空间效率及适应性方面还存在不足。本节将介绍一种基于链表实现,以消除上述缺陷。 java实现...
  • :这是一个先进后出的数据结构,生活中类似的浏览器的返回上一页就可以利用此结构实现,代码如下:public class Stack{private Object[] data;//存储数据private int top;//表示栈顶元素publicStack(){data= new ...
  • java中要实现栈和队列,需要用到java集合的相关知识,特别是Stack、LinkedList等相关集合类型。一、实现栈实现,有两个方法:一个是用java本身的集合类型Stack类型;另一个是借用LinkedList来间接实现Stack...
  • 双端链表: 双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear 这样在链尾插入会变得非常容易,只需改变rear的next为新增的结点即可,而不需要循环搜索到最后一个节点 所以有insertFirst...
  •  用链表实现的基本操作:入栈、出栈、查看栈顶数据以及判断是否有数据 /** * 用链表实现栈 * @author Administrator * * @param &lt;E&gt; */ public class MyStackLink&lt;E&...
  • 主要用java实现了数据结构中队列、二叉树、链表的常规操作
  • Java中实际上提供了java.util.Stack来实现栈结构,但官方目前已不推荐使用,而是使用java.util.Deque双端队列实现队列的各种需求 ava.util.Deque的实现子类有java.util.LinkedList和java.util.ArrayDeque....
  • Java实现栈和队列

    2021-03-06 13:51:12
    原标题:Java实现栈和队列栈(stack)(stack)是一种后进先出(LIFO)的集合类型, 即后来添加的数据会先被删除 可以将其类比于下面文件的取放操作:新到的文件会被先取走,这使得每次取走的文件都是最新的。...
  • 栈和队列Java实现

    2021-03-06 00:08:25
    的创建队列的创建两个栈实现一个队列两个队列实现一个设计含最小函数min()的,要求min、push、pop、的时间复杂度都是O(1)判断的pushpop序列是否一致1、的创建:我们接下来通过链表的形式来创建,方便...
  • 用两个栈实现队列java代码实现

    千次阅读 2020-04-30 20:07:48
    不管是队列还是,他们的功能都是存储数据,底层实现可以数组也可以是链表,但是他们各自有他们的特点。既然队列也是存储数据的一种数据结构,那么他就有增删改查等功能。队列的添加元素是在队尾添加,删除元素是在...
  • 1.前一篇介绍了链表是什么,怎么实现,今天肝一个小时,顺便把栈和队列的这种基础线性表介绍一下; 2.什么是是一种先进后出的线性结构(FILO),“fist In last out”我是这么理解这个单词缩写,就像你往一个...
  • java 使用数组和链表实现队列示例 队列是一种特殊的线性表它只允许在的前端 (front) 进行删除操作只允许 在的后端 rear 进行插入操作 , 下面介绍一下 java 使用数组和链表实现队列 的示例 1) 用数组实现队列 ...
  • Java栈和队列实现

    2019-11-26 21:52:22
    首先要明确一点,数组列表都是属于物理存储结构,而栈和队列属于逻辑存储结构,他们的物理实现既可以用数组也可以用链表实现。 目录 一、实现 1.的数组的实现 2.链表实现 3.的应用场景 二、...
  • 数组和链表是线性表的物理存储结构:即顺序存储链式存储,栈和队列都属于线性表的逻辑存储结构。 上面这句话啥意思? 我们知道常见的数据结构中有一个线性表,线性表包括:数组、链表队列。 物理存储结构:...
  • 本文内容:使用Java实现:使用数组实现栈,使用数组实现链表,使用链表实现队列,使用链表实现队列 文章目录学习目标:学习内容:具体实现: 具体实现: 使用数组实现栈 //数组实现栈 class MyStack{ int[] data...
  • 栈和队列 一、 1.概念 :一种特殊的线性表,只允许在固定的一端进行插入删除数据操作。进行数据插入删除操作的一端称为 顶,另一端称为底。 中的数据元素遵守后进先出LIFO(Last In First Out)的原则...
  • 数据结构之数组、链表栈和队列

    千次阅读 2020-08-01 14:30:51
    但是有利有弊,这个特性虽然使得访问数组边得非常容易但是也使得数组插入删除操作会变得很低效,插入删除数据后为了保证连续性,要做很多数据搬迁工作。 1.2:逻辑结构物理结构 所谓的数组的逻辑结构指的是...
  • 由于LInkedList可以当做栈和队列来使用,所以同样也有pushpop方法,但是要注意这我们所想的的方法有所区别。 push方法,是push到最前面=addFirst public class test1 { public static void main(String[] ...
  • 二,链表实现 是指限定在表尾进行插入或者删除操作的线性表,的表尾成为栈顶(top),表头成为底(bottom)。这里先介绍的四个基本操作 1、push()方法是将新元素插入内 2、pop()方法是删除并返回...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,389
精华内容 22,555
关键字:

java链表实现栈和队列

java 订阅