`

【数据结构】栈的链式存储结构及实现

 
阅读更多
本文转自:疯狂Java 突破程序员基本功的16课
    程序可以采用单链表来保存栈中所以元素,这种链式结构的栈也被称为链栈。对于链栈而言,栈顶元素不断地改变,程序只有使用一个top引用来记录当前的栈顶元素即可。top引用变量永远引用栈顶元素,再使用一个size变量记录当前栈中包含多少元素即可。

1.进栈
    对于链栈的进栈操作,程序只需要做如下两件事情:
  (1)让top引用指向新添加的元素,新元素的next引用执行原来的栈顶元素;
  (2)让记录栈内元素个数的size变量+1。

2.出栈
    对于链栈的出栈操作,需要将栈顶元素弹出栈,程序需要做两件事情:
  (1)让top引用执行原栈顶元素的下一个元素,并释放原来的栈顶元素;
  (2)让记录栈内元素的size变量-1。

LinkStack.java

package com.syc.crazejava.chapter10;

public class LinkStack<T> {

	// 定义一个内部类Node,Node实例代表链栈的节点
	private class Node{
		// 保存节点的数据
		private T data;
		// 指向下个节点的引用
		private Node next;
		// 无参数的构造器
		public Node(){
		}
		// 初始化全部属性的构造器
		public Node(T data,Node next){
			this.data = data;
			this.next = next;
		}
	}
	
	// 保存该链栈的栈顶元素
	private Node top;
	// 保存该链栈中已包含的节点数
	private int size;
	// 创建空链栈
	public LinkStack(){
		// 空链栈,top的值为null
		top = null;
	}
	// 以指定数据元素来创建链栈,该链栈只有一个元素
	public LinkStack(T element){
		top = new Node(element,null);
		size ++;
	}
	// 返回链栈的长度
	public int length(){
		return size;
	}
	// 进栈
	public void push(T element){
		// 让top指向新创建的元素,新元素的next引用指向原来的栈顶元素
		top = new Node(element,top);
		size ++;
	}
	// 出栈
	public T pop(){
		Node oldTop = top;
		// 让top引用指向原栈顶元素的下一个元素
		top = top.next;
		// 释放原栈顶元素的next引用
		oldTop.next = null;
		size--;
		return oldTop.data;
	}
	// 访问栈顶元素,但不删除栈顶元素
	public T peek(){
		return top.data;
	}
	// 判断链栈是否为空栈
	public boolean empty(){
		return size == 0;
	}
	// 清空链栈
	public void clear(){
		// 将底层数组所有元素赋为null
		top = null;
		size = 0;
	}
	
	public String toString(){
		// 链栈为空链栈时
		if(empty()){
			return "[]";
		}else{
			StringBuilder sb = new StringBuilder("[");
			for(Node current = top; current != null; current = current.next){
				sb.append(current.data.toString() + ",");
			}
			int len = sb.length();
			return sb.delete(len - 1, len).append("]").toString();
		}
	}
}

LinkStackTest.java
package com.syc.crazejava.chapter10;

public class LinkStackTest {

	public static void main(String[] args){
		LinkStack<String> stack = new LinkStack<String>();
		// 不断入账
		stack.push("aaa");
		stack.push("bbb");
		stack.push("ccc");
		stack.push("ddd");
		System.out.println(stack);
		// 访问栈顶元素
		System.out.println("访问栈顶元素:" + stack.peek());
		// 弹出一个元素
		System.out.println("第一次弹出栈顶元素:" + stack.pop());
		// 再次弹出一个元素
		System.out.println("第二次弹出栈顶元素:" + stack.pop());
		System.out.println("两次pop之后的栈:" + stack);
	}
}
引用
[ddd,ccc,bbb,aaa]
访问栈顶元素:ddd
第一次弹出栈顶元素:ddd
第二次弹出栈顶元素:ccc
两次pop之后的栈:[bbb,aaa]
分享到:
评论

相关推荐

    数据结构---链式栈的C++实现

    链式栈的C++实现。创建CStack类,实现栈的各项功能:压栈、出栈、遍历、清空等。

    数据结构栈的实现

    采用链式存储实现栈的初始化、入栈、出栈操作 CODE: #include template class link { public: T date; link&lt;T&gt; *next; link(const T info, link&lt;T&gt; *nextvalue=NULL) { date=info; next=nextvalue; } link...

    数据结构实验栈和队列详细实验报告

    (1) 熟悉栈的特点(先进后出)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现; (2) 熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的...

    数据结构实验报告2.docx

    1、定义栈可以是顺序存取结构或链式存储结构 2、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等) 3、定义一个函数用来实现上面问题: 十进制整数 X 和 R 作为形参 初始化栈 只要 X 不为 0 重复做下列动作...

    数据结构C语言实现栈和队列的基本操作

    用C语言实现了栈和队列的数据结构形式,其中包括栈和队列的初始化,压栈弹栈,进队出堆。和一些其他的基本操作!

    栈的链式存储:链栈的C语言实现

    链栈是特殊的链表,它限制只能在链表的一端进行插入删除操作,允许操作的一端称为栈顶,另一端称为栈底。本代码包含:创建一个...具体链栈实现的详细分析可参考文章《【数据结构】栈的链式存储:链栈的C语言实现》。

    数据结构实验报告 第一章 栈和队列

    总的来说,通过这两次的上机实验练习,我的收获比较多,基本上掌握了队和栈的基本知识,达到了实验要求的目的。

    数据结构 主要是栈 含有课件 练习

    1. 栈的基本概念 2. 栈的顺序存储表示表示和实现 (1)顺序栈动态分配存储空间方法 和对栈操作设计 (2)顺序栈静态分配存储空间方法 和对栈...3. 栈的链式存储结构——链栈 顺序栈静态分配存储空间方法 和对栈操作设计

    数据结构 栈的算法实现

    详细代码及讲解 (1)初始化栈 (2)入栈操作 (3)出栈操作 ……

    C++数据结构实验二:栈与队列的应用

    3.掌握栈和队列的逻辑结构特点、顺序存储结构、链式存储结构、顺序栈和链栈的结构体类型定义、循环队列和链队列的结构体类型定义、栈和队列在两种存储结构上的各种基本操作的实现算法。 4.将任意十进制数转换为三种...

    栈类的实现

    本资源是属于栈类的实现,包含了seqlist.h,是我总结了老师上课的内容 栈类的实现

    用栈解决表达式求值问题(数据结构)

    表达式求值问题,用的算法是数据结构(清华版)讲栈哪方面知识的时候书本上的一个算法,能实现功能。

    数据结构课程设计—火车票务系统

    一个用c编写的数据结构实验,实现火车票务系统基本功能代码。。希望给你些帮助。。。

    C语言实现链式栈的模板

    在C语言里面没有模板一说,这里通过用一些极为巧妙的方法来实现了类似于C++的模板功能,使得链式栈的数据可以通过实际需要的类型来决定

    数据结构:栈(包含线性表)

    在之前的线性表的基础上实现了栈的功能,包括顺序存储结构和链式存储结构,保留了之前的线性表的代码,现在是栈和线性表的功能二合一,类似MFC的CArray和CList

    数据结构顺序栈实验2

    编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作。【实验要求】 1、数据要求 顺序表中的数据是图书信息(书号、书名、价格)。 2、输入要求 输入n+1行,其中前n行是n本图书的信息(书号、书名、价格),每本...

    栈类模板的设计与实现

    进行栈类模板的设计并实现,栈采用链式存储结构,数据元素可以是char,int,float 等多种数据类型,包括以下功能: 实现初始化栈操作,建立一个空栈; (1)实现清空栈操作; (2)实现判断栈是否为空的操作; (3)实现求栈长度...

    c++数据结构-实验.zip

    2)设计一个线性表,分别用顺序存储结构和链式存储结构实现,完成线性表的构造、查找、插入、删除、输出等基本操作。 3)掌握两种存储结构的优缺点以及在实际应用中如何选择存储方式。 4)选作:约瑟夫环的顺序存储...

    王道数据结构+C语言版+超全笔记(图文)+个人整理版本

    (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 四、树与二叉树栈 (一)树的概念 (二)二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索...

    2022数据结构课设easyx实现顺序表,链式栈和无向图的算法的动态演示代码

    1、通过软件界面,能够指定进行可视化操作的数据结构类型,...6、针对每一种数据结构绘制的图形,实现相关的 2-3 个算法并执行,在交 互界面中显示执行的过程与最终的结果,如顺序表的插入删除、图的周游、最小生成树等

Global site tag (gtag.js) - Google Analytics