堆栈

有一堆书,一本叠一本地放入箱子里,最后放入的,一定是在最上面,对不对。取书的时候,规定只能从上面一本一本地取,如果要拿最先放入箱子里的那本书,也就是最下面的那本书,只能先把上面的拿出来。

p001301_stack

什么是堆栈(Stack)

上面说的就是我们今天要讲的堆栈,也可以简单叫做栈。堆栈是很常用很基础的数据结构。堆栈涉及到的概念如果下。

栈顶,就是最上面的一个元素。

压栈(Push),就是将一个元素放入栈中。

弹出(Pop),就是将栈顶的元素从堆栈中拿出来。

就像上面往箱子里放书一样,最先放入堆栈的元素,在最下面,最后放入的元素,在最上面,而取元素,只能从上面一个一个取,不能从中间抽取元素。

堆栈有什么用呢

那栈有什么用呢,举几个简单的例子。我们用的很多软件,都有撤销功能对不对,其实,那个就可以用堆栈来实现。将每一步操作时的状态,保存到堆栈中,当用户要撤销时,就从堆栈中拿出最近的一个状态进行恢复,也就是最后放入堆栈中 (栈顶) 的状态数据。是不是很熟悉?

后面要学到的树的遍历,深度优先搜索,也是用堆栈来实现的。

总之呢,记住一句话,先进后出(Fist in last out) 或者 后进先出(Last in first out) 就可以完美诠释堆栈这种数据结构。

自己动手实现一下

很多编程语言已经实现了堆栈(Stack)结构,但是呢,我们这里自己实现一下,加深理解。代码使用 C#,以链表的形式来实现。(C# 语言本身已经拥有了Stack,在实际使用中,不需要自己实现)

class Node {
public int data;
public Node next;

public Node(int data){
this.data = data;
}
}

class Stack {
public Node topNode = null;

// 将一个数据压入堆栈中
public void Push(int data){
Node newNode = new Node(data);
newNode.next = topNode;
topNode = newNode;
}

// 将一个栈顶数据从堆栈中弹出
public int Pop() {
if (!IsEmpty()){
Node top = topNode;
topNode = topNode.next;
return top.data;
}
return -1;
}

// 窥探栈顶元素,但不弹出
public int Peek() {
if(!IsEmpty()){
return topNode.data;
}
return -1;
}

// 判断堆栈是否为空
public bool IsEmpty() {
return topNode == null;
}

}

好啦,今天的文章到此结束,是不是很简单? 有问题记得在下面留言噢。嘻嘻(*^__^*) 晚安~

Author: Moeif Studio

Permalink: http://blog.moeif.com/2019/12/12/data-structure-03-stack/

任何技术问题,可加微信交流,微信: ifloop

搜索并关注微信公众号 [ 萌一小栈 ] 可及时订阅最新技术文章

Comments