本文转自:疯狂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.javapackage 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]
分享到:
相关推荐
在给定的文件列表中,"StackLink.cpp"很可能包含了栈链式存储结构的C++实现代码。通常,`.cpp`文件是用来编写C++源代码的。在这个文件中,可能定义了一个栈类,该类使用链表作为底层数据结构,包含push(入栈)、pop...
本实验报告详细介绍了线性表的链式存储结构,通过编程实践深入理解了链表的逻辑结构、基本操作以及链表算法的实现过程。 线性表作为一种常见的数据结构,其特点是元素之间存在一对一的线性关系。线性表中数据元素...
在本主题中,我们将深入探讨线性表的两种主要存储结构:顺序存储结构和链式存储结构,以及在这两种结构上实现的基本操作。同时,我们还会涉及栈这种特殊类型的线性表及其顺序和链式存储结构。 一、线性表的顺序存储...
在这个主题中,我们将专注于两种重要的数据结构实现:栈的顺序存储和链式存储。栈是一种特殊的数据结构,被称为“后进先出”(LIFO)结构,这意味着最后进入的元素将首先被取出。这种特性使得栈在许多算法和程序设计...
链式存储结构是栈的一种实现方式,相比数组实现,它具有更大的灵活性,特别是在动态调整容量时。 本篇将详细介绍如何使用C语言通过单链表来实现栈的功能。首先,我们需要定义一个链表节点结构体,它包含一个数据域...
栈是一种特殊的线性数据结构,它的特点是“后进先出”(Last In First Out,简称LIFO)。在计算机科学中,栈广泛应用于各种算法和数据处理中,如递归、表达式求值、内存管理等。链式存储是实现栈的一种有效方式,...
这些文件可能包含了用C++语言编写的栈的顺序存储结构实现。`StackLink`可能代表链式栈的实现,而`stack`可能是基于数组的顺序栈实现。`.dsp`和`.dsw`文件是旧版的Microsoft Visual Studio项目文件,`.ncb`是Visual ...
总结起来,栈的链式存储是一种高效且灵活的数据结构实现方式,它允许动态扩展,具有较高的空间效率,并能快速执行基本操作。在编程实践中,掌握链式栈的原理和实现对于解决复杂问题有着重要的作用。
### 数据结构栈的实现 #### 实验目的 本次实验旨在帮助学生掌握栈的基本概念与实现方法,具体目标如下: 1. **理解栈的概念及其在内存中的存储方式**:熟悉栈的基本特性和工作原理,了解栈如何通过两种主要的存储...
在本实验中,线性表采用链式存储结构实现,即每个元素(节点)包含一个数据域和一个指向下一个元素的指针。 链式存储结构相比于顺序存储结构(如数组),在插入和删除操作上有更高的灵活性,因为它们不需要考虑元素...
链式存储是数据结构的一种重要实现方式,相对于顺序存储(如数组),链式存储在处理动态数据集合时展现出更大的灵活性。在这个“2010数据结构链式存储”主题中,我们将深入探讨链表的原理、操作以及其在实际应用中的...
本章主要探讨的是两种常用且基础的数据结构——栈(Stack)和队列(Queue),以及它们的两种基本存储方式:顺序存储结构(Sequential Storage Structure)和链式存储结构(Linked Storage Structure)。我们将深入...
链式栈是栈的一种实现方式,它使用链表作为存储结构。与数组实现的顺序栈相比,链式栈在内存分配上更加灵活,无需预分配固定大小的空间。本文将详细介绍如何在VS2010环境下使用C++实现链式栈,并通过具体的代码示例...
### 数据结构栈和队列知识点解析 #### 一、栈的基本概念与操作 **栈**是一种特殊的线性表,只允许在一端进行插入和删除操作,这一端被称为栈顶,另一端被称为栈底。栈遵循先进后出(First In Last Out, FILO)的...
链式栈是一种采用链表作为存储结构的栈,其主要特点是不需要预分配存储空间,因此在处理大规模数据时更加灵活。链式栈的基本操作包括:创建空栈、入栈、出栈等。 #### 二、链式栈的基本概念 1. **节点定义**: - ...
本文主要讨论了栈数据结构的两种实现方式:顺序存储结构和链式存储结构,并提供了具体的代码实现。 #### 描述解析 该描述表明文章提供的代码已经通过了相关的测试(即已AC),可以放心下载使用。 #### C++知识点及...
本章将深入探讨两种重要的数据结构——栈和队列,以及它们的两种常见存储方式:顺序存储结构和链式存储结构。 栈(Stack)被称为“后进先出”(Last In, First Out,简称LIFO)的数据结构。栈的操作主要围绕两个...
链式栈是一种特殊的数据结构,它属于线性数据结构,并且利用链表来实现栈的操作。本节将详细介绍如何用C++来实现链式栈。 首先,我们需要了解栈的基本概念。栈是一种后进先出(LIFO)的数据结构,常用于临时存储和...