一、 栈概述

  • 栈是将生活中的场景引入计算机中概念,古代的客栈,供旅客休息进出,我们把休息的过程作为数据的存储过程,进出作为数据的增删,于是有了线性表的另一种结构——栈。
  • 栈是一种先进后出(FILO)的数据结构,是只能在一端进行数据插入和删除的线性表,按照先进后出的原则存储数据。
  • 首先进入的数据被压到栈底,称为压栈,后进入的数据存放在栈顶,称为弹栈。需要读数据的时候则从栈顶一个一个的弹出数据元素。

  

二、 栈实现

import java.util.Iterator;

import com.data.struct.common.list.link.Node;

public class Stack<T> implements Iterable<T> {

      

       // 结点声明

       public Node head;

      

       // 栈的深度

       public int N;

      

       public Stack() {

              head = new Node<T>(null,null);

              N=0;

       }

      

       /**

        * 栈是否为空

        * @return

        */

       public boolean isEmpty() {

              return N==0;

       }

      

       /**

        * 压栈

        * @param t

        */

       public void push(T t) {

              //头结点连接的结点

              Node firstNode = head.next;

             

              //新建指向头结点连接的原结点

              Node newNode = new Node<T>(t,firstNode);

             

              //头结点指向新结点

              head.next = newNode;

             

              N++;

       }

      

       /**

        * 弹栈

        * @param t

        */

       public T pop(T t) {

             

              if(isEmpty()) {

                     return null;

              }

             

              //头结点连接的结点

           Node firstNode = head.next;

          

           //头结点连接的新结点

           Node newFirstNode = firstNode.next;

          

           head.next = newFirstNode;

          

           N--;

          

           return (T) firstNode.item;

       }

      

       /**

        * 栈的深度

        * @return

        */

       public int size() {

              return N;

       }

       @Override

       public Iterator<T> iterator() {

              return new MyIterator();

       }

       public class MyIterator implements Iterator<T> {

              Node node;

             

              public MyIterator() {

                     node = head;

              }

              @Override

              public boolean hasNext() {

                     return node.next != null;

              }

              @Override

              public T next() {

                     return (T) node.next.item;

              }

       }

}

 

三、 队列概述

  队列是一种先进先出(FIFO)的数据结构,是一种在一端插入,在另一端删除的线性表结构,按照先进先出的原则存储数据元素。

   

   

四、 队列实现

public class Queue<T> implements Iterable<T>{

      

       //声明头结点

       public Node head;

      

       //声明尾结点

       public Node last;

      

       //队列大小

       public int N;

       public Queue() {

              head = new Node<T>(null, null);

              last = null;

              N=0;

       }

      

       /**

        * 队列大小

        * @return

        */

       public int size() {

              return N;

       }

      

       /**

        * 队列是否为空

        * @return

        */

       public boolean isEmpty() {

              return N==0;

       }

      

       /**

        * 元素进队列

        * @param t

        */

       public void enqueue(T t) {

              if(last==null) {

                     last = new Node<T>(t, null);

                     head.next = last;

              }else {

                     Node oldLast = last;

                     last = new Node<T>(t, null);

                     oldLast.next = last;

              }

             

              N++;

       }

      

       /**

        * 元素出队列

        * @return

        */

       public T dequeue() {

              if(isEmpty()) {

                     return null;

              }

             

              Node firstNode = head.next;

              Node newFirstNode = firstNode.next;

              head.next = newFirstNode;

             

              N--;

             

              if(isEmpty()) {

                     last = null;

              }

             

              return (T) firstNode.item;

       }

       @Override

       public Iterator<T> iterator() {

              return new MyIterator();

       }

      

       public class MyIterator implements Iterator<T> {

              Node node = null;

             

              public MyIterator() {

                     node = head;

              }

              @Override

              public boolean hasNext() {

                     return node.next != null;

              }

              @Override

              public T next() {

                     Node nextNode = node.next;

                     node = node.next;

                     return (T) nextNode.item;

              }

       }

}


发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

数据结构(三):线性表-顺序表,链表讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。