三.基本数据结构-栈

以你之姓@ 2023-02-17 14:50 23阅读 0赞

原文链接:https://www.cnblogs.com/bobo-zhang/p/10524297.html

#  #

[ 3.基本数据结构-栈 ][3._-_]

</h1>
            <div class="clear"></div>
            <div class="postBody">

一.线性数据结构

- 我们从四个简单但重要的概念开始研究数据结构。栈，队列，deques（双向队列）, 列表是一类数据的容器，它们数据元素之间的顺序由添加或删除的顺序决定。一旦一个数据元素被添加，它相对于前后元素一直保持该位置不变。诸如此类的数据结构被称为线性数据结构。

- 线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除元素的方式，特别是添加和移除元素的位置。例如一些结构允许从一端添加元素，另一些允许从另一端移除元素。

二.栈

- 概念：栈（有时称为“后进先出栈”）是一个元素的有序集合，其中添加移除新元素总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。栈的底部很重要，因为在栈中靠近底部的元素是存储时间最长的。最近添加的元素是最先会被移除的。这种排序原则有时被称为 LIFO，后进先出。它基于在集合内的时间长度做排序。较新的项靠近顶部，较旧的项靠近底部。

- 案例：栈的例子很常见。几乎所有的自助餐厅都有一堆托盘或盘子，你从顶部拿一个，就会有一个新的托盘给下一个客人。想象桌上有一堆书, 只有顶部的那本书封面可见，要看到其他书的封面，只有先移除他们上面的书。下图展示了另一个栈，包含了很多 Python 对象。

![1489694-20190313145850790-560759892.png][]![1489694-20190313145820521-1078990921.png][]

- 栈的分析与应用：

- 分析：和栈相关的最有用的想法之一来自对它的观察。假设从一个干净的桌面开始，现在把书一本本叠起来，你在构造一个栈。考虑下移除一本书会发生什么。移除的顺序跟刚刚被放置的顺序相反。栈之所以重要是因为它能反转项的顺序。插入跟删除顺序相反。

- 应用：每个 web 浏览器都有一个返回按钮。当你浏览网页时，这些网页被放置在一个栈中（实际是网页的网址）。你现在查看的网页在顶部，你第一个查看的网页在底部。如果按‘返回’按钮，将按相反的顺序浏览刚才的页面。

三.Python实现栈

- 栈的抽象数据类型定义：栈的抽象数据类型应该由以下结构和操作定义。栈操作如下：

*   *  Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。
     *  push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
     *  pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
     *  peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
     *  isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
     *  size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

- 代码实现：Python 中的列表类提供了有序集合机制和一组方法。例如，如果我们有列表 \[2,5,3,6,7,4\]，我们只需要确定列表的哪一端将被认为是栈的顶部。一旦确定，可以使用诸如 append 和 pop 的列表方法来实现操作。

![复制代码][Image 1]

class Stack:
         def __init__(self):
             self.items = []
      </span><span style="color: #0000ff;">def</span><span style="color: #000000;"> isEmpty(self):
         </span><span style="color: #0000ff;">return</span> self.items ==<span style="color: #000000;"> []
    
     </span><span style="color: #0000ff;">def</span><span style="color: #000000;"> push(self, item):
         self.items.append(item)
    
     </span><span style="color: #0000ff;">def</span><span style="color: #000000;"> pop(self):
         </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> self.items.pop()
    
     </span><span style="color: #0000ff;">def</span><span style="color: #000000;"> peek(self):
         </span><span style="color: #0000ff;">return</span> self.items[len(self.items)-1<span style="color: #000000;">]
    
     </span><span style="color: #0000ff;">def</span><span style="color: #000000;"> size(self):
         </span><span style="color: #0000ff;">return</span> len(self.items)</pre>

![复制代码][Image 1]

- 应用：

![复制代码][Image 1]

from basic.stack import Stack

s=Stack()

print(s.isEmpty())  
s.push(4)  
s.push(‘dog’)  
print(s.peek())  
s.push(True)  
print(s.size())  
print(s.isEmpty())  
s.push(8.4)  
print(s.pop())  
print(s.pop())  
print(s.size())

![复制代码][Image 1]

分类: [数据结构+算法][Link 1]

好文要顶 关注我 收藏该文 ![icon_weibo_24.png][] ![wechat.png][]

[![20190729093950.png][]][20190729093950.png 1]

[波晓张][20190729093950.png 1]  
[关注 - 2][- 2]  
[粉丝 - 542][- 542]

\+加关注

<div class="clear"></div>
    <div id="post_next_prev">
    
    <a href="https://www.cnblogs.com/bobo-zhang/p/10521769.html" class="p_n_p_prefix">« </a> 上一篇：    <a href="https://www.cnblogs.com/bobo-zhang/p/10521769.html" title="发布于 2019-03-13 11:07">2.python数据结构的性能分析</a>
    <br>
    <a href="https://www.cnblogs.com/bobo-zhang/p/10524517.html" class="p_n_p_prefix">» </a> 下一篇：    <a href="https://www.cnblogs.com/bobo-zhang/p/10524517.html" title="发布于 2019-03-13 17:19">4.基本数据结构-队列</a>

posted @ 2019-03-13 16:55  [波晓张][Link 2]  阅读( 266)  评论( 0)  [编辑][Link 3]  收藏

</div>

刷新评论 刷新页面 返回顶部

注册用户登录后才能发表评论，请 登录 或 注册， [访问][Link 4] 网站首页。

[【推荐】了解你才能更懂你，博客园首发问卷调查，助力社区新升级][Link 5]  
[【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库][50_VC_ _CAD_GIS]  
[【推荐】独家下载！《Java开发手册》灵魂13问，深度剖析一线大厂开发思维][Java_13]

[3._-_]: https://www.cnblogs.com/bobo-zhang/p/10524297.html
[1489694-20190313145850790-560759892.png]: https://img2018.cnblogs.com/blog/1489694/201903/1489694-20190313145850790-560759892.png
[1489694-20190313145820521-1078990921.png]: https://img2018.cnblogs.com/blog/1489694/201903/1489694-20190313145820521-1078990921.png
[Image 1]: 
[Link 1]: https://www.cnblogs.com/bobo-zhang/category/1417180.html
[icon_weibo_24.png]: https://common.cnblogs.com/images/icon_weibo_24.png
[wechat.png]: https://common.cnblogs.com/images/wechat.png
[20190729093950.png]: https://pic.cnblogs.com/face/1489694/20190729093950.png
[20190729093950.png 1]: https://home.cnblogs.com/u/bobo-zhang/
[- 2]: https://home.cnblogs.com/u/bobo-zhang/followees/
[- 542]: https://home.cnblogs.com/u/bobo-zhang/followers/
[Link 2]: https://www.cnblogs.com/bobo-zhang/
[Link 3]: https://i.cnblogs.com/EditPosts.aspx?postid=10524297
[Link 4]: https://www.cnblogs.com/
[Link 5]: https://www.wenjuan.com/s/3uIjeq0/
[50_VC_ _CAD_GIS]: http://www.ucancode.com/index.htm
[Java_13]: https://developer.aliyun.com/article/758263?utm_content=g_1000133217