数据结构与算法—栈详解(看完面试考试再也不怕了)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法—栈详解(看完面试考试再也不怕了)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5696字，纯文字阅读大概需要9分钟。

内容图文

什么是栈

百度百科上，栈是这么定义的：

• 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

稍微介绍一下关键名词：

• 运算受限：也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端就行插入和删除。同样，队列也是运算受限，只能在两天操作。

• 线性表：栈也是一种线性表，前面详细介绍过线性表，它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分数组和链表实现，他们的物理存储结构不同。但是逻辑结构(实现的目的)相同。

• 栈顶栈底： 这个描述是偏向于逻辑上的内容，因为大家知道数组在末尾插入删除更容易，而单链表通常在头插入删除更容易。所以数组可以用末尾做栈顶，而链表可以头做栈顶。

栈的应用：

• 栈的应用广泛，比如你的程序执行查看调用堆栈、加减运算、甚至在搜索算法中dfs，替代递归等等。所以栈也是必须掌握的一门数据结构。很多规范也是栈，比如上图放书拿书一样！

设计与介绍

这里我们介绍数组实现的栈和链表实现的栈。

数组实现

结构设计

• 对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data数组和一个top(int)表示栈顶位置。

• 那么初始化以及构造的函数代码为：

private T data[];private int top;public seqStack() {  data=(T[]) new Object[10];  top=-1;}public seqStack(int maxsize){  data=(T[]) new Object[maxsize];  top=-1;}

push插入

栈的核心操作之一push：入栈操作。

• 如果top<数组长度-1。入栈。top++;a[top]=value;

• 如果top==数组长度-1；栈满。
  

pop弹出并返回首位

• 如果top>=0,栈不为空，可以弹出。return data[top--];

• 如下图，本来栈为1，2，3，4（栈顶），执行pop操作。top变为3的位置并且返回4；
  

其他操作

• 其他例如peek操作时返回栈顶不弹出.所以只需满足题意时候return data[top]即可。

链表实现

有数组实现，链表当然也能实现。对于栈的运算。大致可以分为两种思路：

• 像数组那样在尾部插入删除。大家都知道链表效率低在查询。而查询到尾部效率很低。而我们就算用了尾指针，可以解决尾部插入效率。但是依然无法解决删除效率(删除需要找到前节点).还需要双向链表。前面虽然详细介绍过双向链表，但是这样未免太复杂！

• 所以我们采用带头节点的单链表在头部插入删除，把头部当中栈顶，这样精了很多。插入直接在头节点后插入。而删除也直接删除头节点后第一个元素即可。

结构设计

长话短说，短话不说。直接上代码就懂。
链表的节点：

static class node<T>{  T data;  node next;  public node() {      }  public node(T value){    this.data=value;  }}

基本结构：

public class lisStack <T>{  int length;    node<T> head;//头节点    public lisStack() {    head=new node<>();    length=0;  }  //其他方法}

push插入

与单链表头插入一致，如果不太了解请先看笔者队线性表介绍的。

和数组形成的栈有个区别。就是理论上栈没有大小限制(不突破内存系统限制)。不需要考虑是否越界。

• 节点team入栈

• 空链表入栈head.next=team;

• 非空入栈team.next=head.next;head.next=team;
  

pop弹出

与单链表头删除一致，如果不太了解请先看笔者队线性表介绍的。

和数组同样需要判断是否为空。

• 节点team出栈

• head指向team后驱节点。不需要考虑链表是否为1个节点。如果为1个节点，team.next=null.执行完毕head.next=null。变为空，满足条件。
  

其他操作

• 其他例如peek操作时返回栈顶不弹出.所以只需判空满足题意时候return head.next.data即可。而length你可以遍历链表返回长度，也可以动态设置(本文采取)跟随栈长变化。其他操作直接看api。

实现代码

数组实现

package 队栈;
public class seqStack<T> {  ?private T data[]; ?private int top; ?public seqStack() { ? ?data=(T[]) new Object[10]; ? ?top=-1; ?} ?public seqStack(int maxsize){ ? ?data=(T[]) new Object[maxsize]; ? ?top=-1; ?} ?boolean isEmpty(){ ? ?return top==-1; ?} ?int length(){ ? ?return top+1; ?}  ?boolean push(T value) throws Exception//压入栈{ ? ?if(top+1>data.length-1) ? ?{ ? ? ?throw new Exception("栈已满"); ? ?} ? ?else { ? ? ?data[++top]=value; ? ? ?return true; ? ?} ?} ?T peek() throws Exception//返回栈顶元素不移除{ ? ?if(!isEmpty()) ? ?{ ? ? ?return data[top]; ? ?} ? ?else { ? ? ?throw new Exception("栈为空"); ? ?} ?} ?T pop() throws Exception{ ? ?if(isEmpty()) ? ?{ ? ? ?throw new Exception("栈为空"); ? ?} ? ?else { ? ? ? return data[top--]; ? ?} ?} ?public String toString(){ ? ?if(top==-1) ? ?{ ? ? ?return ""; ? ?} ? ?else { ? ? ?String va=""; ? ? ?for(int i=top;i>=0;i--) ? ? ?{ ? ? ? ?va+=data[i]+" ?"; ? ? ?} ? ? ?return va; ? ?} ?}}

链表实现

package 队栈;
public class lisStack <T>{ ?static class node<T>{ ? ?T data; ? ?node next; ? ?public node() { ? ? ? ?} ? ?public node(T value){ ? ? ?this.data=value; ? ?} ?} ?int length; ? ?node<T> head;//头节点 ? ?public lisStack() { ? ?head=new node<>(); ? ?length=0; ?} ? ?boolean isEmpty(){ ? ?return head.next==null; ?} ?int length(){ ? ?return length; ?} ? ?public void push(T value) {//近栈 ? ? ? node<T> team=new node<T>(value); ? ? ? if(length==0) ? ? ? { ? ? ? ? head.next=team; ? ? ? } ? ? ? else { ? ?team.next=head.next; ? ?head.next=team;} ? ? ? length++; ? ?} ? ?public T peek() throws Exception { ? ? ? ?if(length==0) {throw new Exception("链表为空");} ? ? ? ?else {//删除 ? ? ?return (T) head.next.data; ? ?} ?} ? ?public T pop() throws Exception {//出栈 ? ? ? ? ?if(length==0) {throw new Exception("链表为空");} ? ? ? ? ?else {//删除 ? ? ? ? ?T value=(T) head.next.data; ? ? ?head.next=head.next.next;//va.next ? ? ?length--; ? ? ?return value;   ? ?} ? ?} ? ?public String toString(){ ? ? ?if(length==0) {return "";} ? ? ?else { ? ? ?String va=""; ? ? ? ?node team=head.next; ? ? ? ?while(team!=null) ? ? ? ?{ ? ? ? ? ?va+=team.data+" "; ? ? ? ? ?team=team.next; ? ? ? ?} ? ? ? ?return va; ? ?}  ? ?}}

测试

总结

• 栈的逻辑比较简单。很容易理解，实现起来也相对容易。但是要注意数组情况的界限问题。

• 后面将介绍队列，相比栈，队列内容更丰富一些。难度也稍大一些。

• 如果有不好需要改进还请指出！

• 最后，喜欢的话可以关注公众号：bigsai 持续分享(回复 数据结构 获得精心准备资料一份！)

内容总结

以上是互联网集市为您收集整理的数据结构与算法—栈详解(看完面试考试再也不怕了)全部内容，希望文章能够帮你解决数据结构与算法—栈详解(看完面试考试再也不怕了)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---