Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
..
Failed to load latest commit information.
150_EvaluateReversePolishNotation.py
155_MinStack.cpp
155_MinStack.py
20_ValidParentheses.py
224_BasicCalculator.py
225_ImplementStackusingQueues.cpp
225_ImplementStackusingQueues.py
227_BasicCalculatorII.py
232_ImplementQueueUsingStacks.cpp
232_ImplementQueueUsingStacks.py
316_RemoveDuplicateLetters.py
32_LongestValidParentheses.cpp
32_LongestValidParentheses.py
341_FlattenNestedListIterator.cpp
341_FlattenNestedListIterator.py
71_SimplifyPath.py
84_LargestRectangleInHistogram.py
85_MaximalRectangle.py
94_BinaryTreeInorderTraversal.py
README.md

README.md

栈是一种最基本、最常用的数据结构,一个词来总结栈的特点就是后进先出。我们可以将栈看作是一个数据仓库,向栈内增加数据的操作叫入栈(push)操作,从栈内取出数据的操作叫出栈(pop)操作。不过不像一般的仓库一样,可以随意取出任何位置的物品,从一个栈取出的数据必须是最后一次增加的数据。换句话就是说,最后一个进入栈的数据,会被第一个取出来。

一个简单的入栈、出栈过程如下图:

生活中有很多场景包含有后进先出的思想,比如刷盘子这个过程,我们将已经洗好的盘子叠在一起,每次洗好一个盘子就将堆在顶部,而我们需要用一个盘子时也是从最上面取走。

栈的起源

那么计算机学科中,是怎么出现栈这个数据结构呢。

栈的实现

典型应用场景

  1. 函数调用

  2. 表达式计算

  3. 表达式转换

    • 中缀转前缀
    • 中缀转后缀
    • 前缀转中缀
    • 后缀转中缀
  4. 模拟递归

题目

155. Min Stack

设计一个栈数据结构,支持 push, pop, top, getMin 操作,且时间复杂度均为 O(1)。

用一个栈来实现正常的站操作,同时用一个辅助栈来保存每次的最小元素。push 数据时,如果当前数据小于等于最小元素,则同时push到数据栈和辅助栈,保证辅助栈顶部是最小元素。pop 时,如果数据栈顶部等于辅助栈顶,则同时pop,否则只用 pop 数据栈。

当然,用一个栈也是可以的,栈里面内容为当前数据和当前最小值之间的距离,具体可以参考 Share my Java solution with ONLY ONE stack

具体实现