文档章节

用链表实现的栈和队列

liddblog
 liddblog
发布于 2017/01/12 13:57
字数 568
阅读 23
收藏 0

链表实现的栈

// linkStack.java
// demonstrates a stack implemented as a list
// to run this program: C>java LinkStackApp
////////////////////////////////////////////////////////////////
class Link
   {
   public long dData;             // data item
   public Link next;              // next link in list
// -------------------------------------------------------------
   public Link(long dd)           // constructor
      { dData = dd; }
// -------------------------------------------------------------
   public void displayLink()      // display ourself
      { System.out.print(dData + " "); }
   }  // end class Link
////////////////////////////////////////////////////////////////
class LinkList
   {
   private Link first;            // ref to first item on list
// -------------------------------------------------------------
   public LinkList()              // constructor
      { first = null; }           // no items on list yet
// -------------------------------------------------------------
   public boolean isEmpty()       // true if list is empty
      { return (first==null); }
// -------------------------------------------------------------
   public void insertFirst(long dd) // insert at start of list
      {                           // make new link
      Link newLink = new Link(dd);
      newLink.next = first;       // newLink --> old first
      first = newLink;            // first --> newLink
      }
// -------------------------------------------------------------
   public long deleteFirst()      // delete first item
      {                           // (assumes list not empty)
      Link temp = first;          // save reference to link
      first = first.next;         // delete it: first-->old next
      return temp.dData;          // return deleted link
      }
// -------------------------------------------------------------
   public void displayList()
      {
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      System.out.println("");
      }
// -------------------------------------------------------------
   }  // end class LinkList
////////////////////////////////////////////////////////////////
class LinkStack
   {
   private LinkList theList;
//--------------------------------------------------------------
   public LinkStack()             // constructor
      {
      theList = new LinkList();
      }
//--------------------------------------------------------------
   public void push(long j)     // put item on top of stack
      {
      theList.insertFirst(j);
      }
//--------------------------------------------------------------
   public long pop()            // take item from top of stack
      {
      return theList.deleteFirst();
      }
//--------------------------------------------------------------
   public boolean isEmpty()       // true if stack is empty
      {
      return ( theList.isEmpty() );
      }
//--------------------------------------------------------------
   public void displayStack()
      {
      System.out.print("Stack (top-->bottom): ");
      theList.displayList();
      }
//--------------------------------------------------------------
   }  // end class LinkStack
////////////////////////////////////////////////////////////////
class LinkStackApp
   {
   public static void main(String[] args)
      {
      LinkStack theStack = new LinkStack(); // make stack

      theStack.push(20);                    // push items
      theStack.push(40);

      theStack.displayStack();              // display stack

      theStack.push(60);                    // push items
      theStack.push(80);

      theStack.displayStack();              // display stack

      theStack.pop();                       // pop items
      theStack.pop();

      theStack.displayStack();              // display stack
      }  // end main()
   }  // end class LinkStackApp

用链表实现的队列

// linkQueue.java
// demonstrates queue implemented as double-ended list
// to run this program: C>java LinkQueueApp
////////////////////////////////////////////////////////////////
class Link
   {
   public long dData;                // data item
   public Link next;                 // next link in list
// -------------------------------------------------------------
   public Link(long d)               // constructor
      { dData = d; }
// -------------------------------------------------------------
   public void displayLink()         // display this link
      { System.out.print(dData + " "); }
// -------------------------------------------------------------
   }  // end class Link
////////////////////////////////////////////////////////////////
class FirstLastList
   {
   private Link first;               // ref to first item
   private Link last;                // ref to last item
// -------------------------------------------------------------
   public FirstLastList()            // constructor
      {
      first = null;                  // no items on list yet
      last = null;
      }
// -------------------------------------------------------------
   public boolean isEmpty()          // true if no links
      { return first==null; }
// -------------------------------------------------------------
   public void insertLast(long dd) // insert at end of list
      {
      Link newLink = new Link(dd);   // make new link
      if( isEmpty() )                // if empty list,
         first = newLink;            // first --> newLink
      else
         last.next = newLink;        // old last --> newLink
      last = newLink;                // newLink <-- last
      }
// -------------------------------------------------------------
   public long deleteFirst()         // delete first link
      {                              // (assumes non-empty list)
      long temp = first.dData;
      if(first.next == null)         // if only one item
         last = null;                // null <-- last
      first = first.next;            // first --> old next
      return temp;
      }
// -------------------------------------------------------------
   public void displayList()
      {
      Link current = first;          // start at beginning
      while(current != null)         // until end of list,
         {
         current.displayLink();      // print data
         current = current.next;     // move to next link
         }
      System.out.println("");
      }
// -------------------------------------------------------------
   }  // end class FirstLastList
////////////////////////////////////////////////////////////////
class LinkQueue
   {
   private FirstLastList theList;
//--------------------------------------------------------------
   public LinkQueue()                // constructor
      { theList = new FirstLastList(); }  // make a 2-ended list
//--------------------------------------------------------------
   public boolean isEmpty()          // true if queue is empty
      { return theList.isEmpty(); }
//--------------------------------------------------------------
   public void insert(long j)        // insert, rear of queue
      { theList.insertLast(j); }
//--------------------------------------------------------------
   public long remove()              // remove, front of queue
      {  return theList.deleteFirst();  }
//--------------------------------------------------------------
   public void displayQueue()
      {
      System.out.print("Queue (front-->rear): ");
      theList.displayList();
      }
//--------------------------------------------------------------
   }  // end class LinkQueue
////////////////////////////////////////////////////////////////
class LinkQueueApp
   {
   public static void main(String[] args)
      {
      LinkQueue theQueue = new LinkQueue();
      theQueue.insert(20);                 // insert items
      theQueue.insert(40);

      theQueue.displayQueue();             // display queue

      theQueue.insert(60);                 // insert items
      theQueue.insert(80);

      theQueue.displayQueue();             // display queue

      theQueue.remove();                   // remove items
      theQueue.remove();

      theQueue.displayQueue();             // display queue
      }  // end main()
   }  // end class LinkQueueApp

 

© 著作权归作者所有

上一篇: 有序列表
下一篇: 链表详述
liddblog
粉丝 4
博文 70
码字总数 65593
作品 0
海淀
程序员
私信 提问
【数据结构与算法】-- 5. 如何实现一个队列(顺序队列和链式队列)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/YYZZHC999/article/details/89644239 队列跟栈一样, 也是一种操作受限的线性表数据结构。 它具有先进先出的特...

杨晓慧_Hepburn
04/28
0
0
数据结构和算法基础(偏向前端方向)

提起算法很多CS毕业的人都不会陌生,但是不管你是在学校理论知识学的如何扎实还是在学校中有参加比赛的经历(ACM等),但是到了工作中因为没有实际的应用场景或者说应用场景很少,导致一些原本...

北宸南蓁
09/26
0
0
JavaScript 数据结构与算法之美 - 线性表(数组、栈、队列、链表)

前言 基础知识就像是一座大楼的地基,它决定了我们的技术高度。 我们应该多掌握一些可移值的技术或者再过十几年应该都不会过时的技术,数据结构与算法就是其中之一。 栈、队列、链表、堆 是数...

全栈修炼
06/30
0
0
数据结构-栈&队列&Deque实现比较

栈 栈: 限定仅在表尾进行插入和删除操作的线性表; 后进先出(LIFO)。 在表尾进行操作,表尾是栈顶;最新进栈的元素在栈底。 栈的ADT Stack_ADT 进栈&出栈 栈 栈的存储结构实现 顺序栈 栈也...

IAM四十二
2017/10/22
0
0
数据结构1 线性结构

数据结构是指数据元素的结合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构,元素关系的存储形式成为存储结构。数据结构按照逻辑关系的不同分为线性结构和非线性结构两大...

zhixin9001
2018/02/07
44
0

没有更多内容

加载失败,请刷新页面

加载更多

PCB设计-Allegro软件入门系列-铺铜操作(下)

铺铜是PCB很常见的操作,PCB的敷铜一般都是覆地铜,增大地线面积,有利于地线阻抗降低,使电源和信号传输稳定,在高频的信号线附近敷铜,可大大减少电磁辐射干扰,起屏蔽作用。 本讲讲解啊一...

demyar
24分钟前
3
0
如何通过WASI SDK 在Linux上编译ZXing C++

Mozilla在今年三月份的时候公布了WASI。WASI的目标就是让WebAssembly在任何地方都可以运行,而不仅仅像现在这样只能运行在Node.js和Web浏览器中。WASI目前依然处于初级阶段,这篇文章分享下如...

yushulx
26分钟前
3
0
.Net界面开发神器—DevExpress官方汉化包免费下载!还在等什么?

点击获取DevExpress v19.1.7新版试用下载 DevExpress Localization Service允许您创建一组自定义的附属程序集,要将语言包添加到程序集中,请查看本文中为大家列出的对应版本的汉化包,下载并...

FILA6666
26分钟前
4
0
php生成二维码

        header('Content-Type: image/png');        //清除缓冲区,防止之前面不知道的情况下被加头部信息导致不显示图片内容        ob_clean();        $...

横着走的螃蟹
31分钟前
3
0
伪类和伪元素

伪类和伪元素 伪类和伪元素,对于绝大多数同学来说,都是耳熟能详的名字,但确实又有很多人搞不清楚它们之间的区别,以致于混淆概念。而当概念都混淆的时候,也往往意味着你不会经常使用它,...

不负好时光
34分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部