【数据结构】栈(stack)栈链（动图解、c++、java）

以下是本篇文章正文内容&＃xff0c;下面案例可供参考。

栈链概述&＃xff08;图解&＃xff09;

栈可以用顺序存储&＃xff0c;也可以用链式存储&＃xff0c;分别称为顺序栈和链栈。

顺序栈是分配一段连续的空间&＃xff0c;需要两个指针&＃xff0c;base指向栈底&＃xff0c;top指向栈顶。

链栈每个节点的地址是不连续的&＃xff0c;只需要一个栈顶指针即可。

从图中可以看出&＃xff0c;链栈的每个节点都包含两个域&＃xff1a;数据域和指针域。

链栈的基本操作

可以把链栈看作一个不带头节点的单链表&＃xff0c;但只能在头部进行插入、删除。取值等操作&＃xff0c;不可以在中间和尾部操作。因此&＃xff0c;可以按单链表的方法定义链栈的节点。

首先定义一个结构体&＃xff08;内部类&＃xff09;&＃xff0c;包含一个数据域和一个指针域。

c&＃43;&＃43;代码如下&＃xff08;示例&＃xff09;&＃xff1a;

typedef struct SNode{int data;//数据域SNode *next;//指针域
}*LinkStack;


java代码如下&＃xff08;示例&＃xff09;&＃xff1a;

public class SNode{int data;SNode next;
}


1.初始化

初始化一个空的链栈是不需要头结点的&＃xff0c;因此只需要让栈顶指针为空即可。

c&＃43;&＃43;代码如下&＃xff08;示例&＃xff09;&＃xff1a;

void Init(LinkStack &S){S &＃61; NULL;
}


java代码如下&＃xff08;示例&＃xff09;&＃xff1a;

F(){//直接用构造器初始化了&＃xff0c;累了&＃xff0c;毁灭吧s &＃61; null;
}


2.入栈

入栈是将新元素节点压入栈顶。因为链栈中第一个节点为栈顶&＃xff0c;因此将新元素插入到第一个节点的前面&＃xff0c;然后修改栈顶指针指向新节点即可。

c&＃43;&＃43;代码如下&＃xff08;示例&＃xff09;&＃xff1a;

void Push(LinkStack &S,int e){LinkStack p &＃61; new SNode;p->data &＃61; e;p->next &＃61; S;//新元素的下个地址是老的栈顶S &＃61; p;//栈顶上移
}


java代码如下&＃xff08;示例&＃xff09;&＃xff1a;

public void push(int e){SNode p &＃61; new SNode();p.data &＃61; e;p.next &＃61; s;s &＃61; p;
}


3.出栈

出栈就是把栈顶元素删除&＃xff0c;让栈顶指针指向下一个节点&＃xff0c;然后释放该节点空间&＃xff08;c&＃43;&＃43;&＃xff09;。

c&＃43;&＃43;代码如下&＃xff08;示例&＃xff09;&＃xff1a;

bool Pop(LinkStack &S,int &e){if(S &＃61;&＃61; NULL){//栈空return false;}LinkStack p &＃61; S;//临时节点S &＃61; p->next;//栈顶下移e &＃61; p->data;//记录出栈元素delete p;//释放空间return true;
}


java代码如下&＃xff08;示例&＃xff09;&＃xff1a;

public int pop(){if(s &＃61;&＃61; null){return -1;}SNode p &＃61; s;s &＃61; s.next;return p.data;
}


4.取栈顶

取栈顶和出栈不同。

取栈顶元素只是吧栈顶元素复制一份&＃xff0c;栈顶指针未移动&＃xff0c;栈内元素个数未变。

c&＃43;&＃43;代码如下&＃xff08;示例&＃xff09;&＃xff1a;

int GetTop(LinkStack S){if(S &＃61;&＃61; NULL){return -1;}return S->data;
}


java代码如下&＃xff08;示例&＃xff09;&＃xff1a;

public int getTop(){if(s &＃61;&＃61; null){return -1;}return s.data;
}


9.完整代码

c&＃43;&＃43;代码如下&＃xff08;示例&＃xff09;&＃xff1a;

#include
using namespace std;typedef struct SNode{int data;SNode *next;
}*LinkStack;void Init(LinkStack &S){S &＃61; NULL;
}void Push(LinkStack &S,int e){LinkStack p &＃61; new SNode;p->data &＃61; e;p->next &＃61; S;S &＃61; p;
}bool Pop(LinkStack &S,int &e){if(S &＃61;&＃61; NULL){return false;}LinkStack p &＃61; S;S &＃61; p->next;e &＃61; p->data;delete p;return true;
}int GetTop(LinkStack S){if(S &＃61;&＃61; NULL){return -1;}return S->data;
}int main(){LinkStack S;int n,e;Init(S);cout<<"链栈初始化成功"<<endl;cout<<"输入元素个数&＃xff1a;"<<endl;cin>>n;cout<<"输入元素&＃xff0c;依次入栈"<<endl;while(n--){cin>>e;Push(S,e);}cout<<"元素依次出栈&＃xff01;"<<endl;while(S!&＃61;NULL){cout<<GetTop(S)<<" ";Pop(S,e);}cout<<endl;
}


java代码如下&＃xff08;示例&＃xff09;&＃xff1a;

public class F {private SNode s;public class SNode{int data;SNode next;}F(){s &＃61; null;}public void push(int e){SNode p &＃61; new SNode();p.data &＃61; e;p.next &＃61; s;s &＃61; p;}public int pop(){if(s &＃61;&＃61; null){return -1;}SNode p &＃61; s;s &＃61; s.next;return p.data;}public int getTop(){if(s &＃61;&＃61; null){return -1;}return s.data;}public static void main(String[] args) {F f &＃61; new F();System.out.println("链栈初始化成功&＃xff01;");f.push(5);f.push(4);f.push(3);f.push(2);f.push(1);System.out.println("创建成功");System.out.println("元素依次出栈");while(f.s!&＃61;null){System.out.print(f.getTop()&＃43;" ");f.pop();}System.out.println();}
}


总结

1. 顺序栈和链栈的基本操作都只需要常数时间&＃xff0c;所以在时间效率上难分伯仲。
2. 在空间效率方面&＃xff0c;顺序栈需要预先分配固定长度的空间&＃xff0c;有可能造成空间的浪费或溢出
3. 链栈每次只分配一个节点&＃xff0c;除非没有内存&＃xff0c;否则不会出现溢出&＃xff0c;但是每个节点需要一个指针域&＃xff0c;结构性开销增加。

因此&＃xff0c;如果元素个数变化较大&＃xff0c;可以采用链栈&＃xff1b;反之&＃xff0c;可以采用顺序栈。

在实际应用中&＃xff0c;顺序栈比链栈应用更广泛。

下期预告&＃xff1a; 循环队列