链表是基本的数据结构，在C语言中的基本结构如下：
struct List {
int data;//数据
struct List *next ;// 指向下一个表的指针
} list, *listP;
谈谈我所知道的堆栈
首先堆和栈是两个不同的概念。
堆栈的特点是先进后出，在X86汇编栈用如下指令：
push ax
push bx
push cx
push dx
...
pop dx
pop cx
pop bx
pop ax
C语言运行不可缺少堆栈，在UEFI BIOS里，在SEC阶段有个功能是cache as stack，意思是在cache里拿出部分空间建立栈环境，由于之前的是汇编，建立栈后才有C语言。
这个为什么呢？举个列子：
//一个简单函数
int add(int data1, int data2){
int data;
data = data1 + data2;
return data;
}
当add函数被调用时，使用栈。传进2个形参data1，data2，C语言还得通过编译器转换为汇编指令，用汇编指令表示为：
push data2
push data1
注意：形参从右到左依次压入栈,另外add函数里的局部变量data也是在栈中建立。
堆：全局变量和程序员手动分配内存如使用malloc函数申请内存，C++使用new方法得到的数据均在堆中。
队列的特点是先进先出，是稍复杂点的数据结构，C语言中用数组这样表示：
struct Queue{
int Array[10];
int head;
int tail;
int length;
};
好了，现在讨论在Java中怎么实现上述两种数据结构.
先探讨堆栈,实现代码如下：
class ListStack{
public static void main(String[] args){
ListStack ls = new ListStack();
ls.push(1);
ls.push(2);
ls.push(3);
ls.push(4);
ls.displayStack();
ls.pop();
ls.pop();
ls.pop();
//ls.pop();
ls.displayStack();
}
//链表是先进后出，在一端进行插入或删除操作
public Link first;
public boolean isEmptyLink(){
if( first == null){
return true;
}
else{
return false;
}
}
public ListStack(){
first = null;
}
//从一端插入操作
public void push(int i){
Link newLink = new Link(i);
//newLink.Link(i);
newLink.next = first;//原来first被新插入的链表占用
first = newLink;//更新first链接点
}
public void pop(){
//判断链表是否为空
if(isEmptyLink()){
System.out.println("stack is empty");
}
else{
first = first.next;
}
}
public void displayStack(){
//判断stack是否为空
if(isEmptyLink()){
System.out.println("stack is empty");
}
else{
//遍历整个堆栈,然后打印数据
Link currentList = new Link();//重新定义一个current
currentList = first;
//Link currentList = first;
while(null != currentList){
currentList.displayLink();//打印值
currentList = currentList.next;
}
}
}
//创建链表结构
class Link{
public int data;
public Link next;//指向下一个链接点
//构造函数 不要指定类型
public Link(){
//System.out.println("无参数的构造函数");
}
public Link(int idata){
//System.out.println("有参数的构造函数");
this.data = idata;
}
public void displayLink(){
System.out.println("[" + data + "]");
}
}
}
接下来是队列的实现,代码如下:
class ListQueue{
public static void main(String[] args){
ListQueue lq = new ListQueue();
lq.insertToQueue("zhangSan", 19);
lq.insertToQueue("liSi", 20);
lq.insertToQueue("wangWu", 21);
//查询
lq.visitQueue("zhangSan");
lq.displayQueue();
lq.removeFromQueue();
System.out.println("remove from queue");
lq.visitQueue("zhangSan");
lq.displayQueue();
}
public Link head;
public Link rear;
public boolean isEmptyQueue(){
return head == null;
}
public ListQueue(){
head = rear = null;
}
//从尾部插入
public void insertToQueue(String name, int age){
Link newLink = new Link(name, age);
//第一次的链接点为head端
if(isEmptyQueue()){
head = newLink;
}
else{
rear.next = newLink;
}
rear = newLink;
}
//从头部删除
public void removeFromQueue(){
if(isEmptyQueue())
{
System.out.println("Queue is empty");
}
else{
if(null == head.next){
rear = null;
}
head = head.next;
}
}
public void displayQueue(){
Link currentLink = head;
while(null != currentLink){
currentLink.displayLink();
currentLink = currentLink.next;
}
}
public void visitQueue(String name){
/*Link visitLink = head;
while(null != visitLink){
if(visitLink.age != age){
visitLink = visitLink.next;
}
else{
System.out.println("have visited the queue element");
break;
}
}
System.out.println("have visited the queue element");*/
for(Link visitLink = head ; visitLink != null ; visitLink = visitLink.next){
if(visitLink.name == name){
System.out.println("can visit the queue element");
return ;
}
}
System.out.println("can not visit the queue element");
return ;
}
class Link{
public String name;
public int age;
public Link next;
public Link(){
//System.out.println("无参数的构造函数");
}
public Link(String name, int age){
//System.out.println("有参数的构造函数");
this.name = name;
this.age = age;
}
public void displayLink(){
System.out.println("name is " + name + "age is " + age);
}
}
}
堆栈类包括插入，删除，遍历操作；队列类包括插入，删除，遍历，查找操作。
比较下,发现两者有不同:
1.在堆栈中申请一个Link first , 对一端进行插入或删除操作。
2.在队列中申请两个Link，Link head和Link tail，head端删除，tail端插入操作。
这是根据两者特点不同采取不同的算法。