参考资料，以下内容来自C/C++/Python大佬们：
https://www.cnblogs.com/lanhaicode/p/10453602.html
https://blog.csdn.net/zichen_ziqi/article/details/80807989
https://zhuanlan.zhihu.com/p/112316768
... ...
定义1. 运算受限的线性存储结构，只能在一端进行插入和删除操作；
2. 允许操作的一端称为栈顶，不允许操作的一端称为栈底；
3. 栈遵循“先进后出”原则
实现方式 顺序栈用一段连续的存储空间来存储栈中的数据元素，比较常见的是用数组来实现顺序栈。
顺序存储结构：
1.元素所占的存储空间必须连续（这里的连续是指的逻辑连续，而不是物理连续）
2.元素在存储空间的位置是按逻辑顺序存放的。
程序实现C++标准库栈，需包含头文件: #include
s.empty(); // 如果栈为空则返回true, 否则返回false s.size(); // 返回栈中元素的个数 s.top(); // 返回栈顶元素, 但不删除该元素 s.pop(); // 弹出栈顶元素, 但不返回其值 s.push(); // 将元素压入栈顶
基于单链表的栈：
#include链栈 using namespace std; template class Stack { private: struct Node { T data; Node *next; }; Node *head; Node *p; int length; public: Stack() { head = NULL; length = 0; } void push(T n) // 入栈 { Node *q = new Node; q->data = n; if (head == NULL) { q->next = head; head = q; p = q; } else { q->next = p; p = q; } length++; } T pop() // 出栈并且将出栈的元素返回 { if (length <= 0) { abort(); } Node *q; T data; q = p; data = p->data; p = p->next; delete(q); length--; return data; } int size() // 返回元素个数 { return length; } T top() // 返回栈顶元素 { return p->data; } bool isEmpty() // 判断栈是不是空的 { if (length == 0) { return true; } else { return false; } } void clear() // 清空栈中的所有元素 { while (length > 0) { pop(); } } }; int main() { Stack s; s.push('a'); s.push('b'); s.push('c'); while (!s.isEmpty()) { cout << s.pop() << endl; } }
链式栈，将链表的头部作为栈顶，尾部作为栈底。避免在实现数据入栈出栈时做大量遍历链表的耗时操作。
入栈操作：将数据从链表的头部插入；
出栈操作：删除链表头部的首元结点。
程序实现#includePython栈 分类 using namespace std; template struct chainStackNode { T data; // 链式栈储存结点的数据 chainStackNode * next; // 链式栈指向下一结点的指针 }; template class chainStack { private: chainStackNode * top; // 将链式栈的头部指针封装为私有成员 public: chainStack(); // 链式栈的构造函数--初始化栈 ~chainStack(); // 析构函数 bool Push(T newData); // 栈的基本操作--进栈 bool Pop(T& x); // 出栈，以引用的方式返回出栈元素 bool getTop(T& x); // 以引用的方式返回栈顶元素 bool isEmpty(); // 判断栈是否为空 void printChainStackData(); // 打印链式栈的数据 }; template inline chainStack ::chainStack() { top = new chainStackNode ; // 创建一个新的结点 top->next = NULL; // 将top的next指针指向空 } template inline chainStack ::~chainStack() { delete[] top; // 释放top指针的空间，析构函数的作用-->回收空间 } template inline bool chainStack ::Push(T newData) { chainStackNode * newNode = new chainStackNode ; if (!newNode) { cout << "分配内存失败！" << endl; return false; } newNode->data = newData; // 修改指针，添加元素 newNode->next = top->next; top->next = newNode; return true; } template inline bool chainStack ::Pop(T& x) { chainStackNode * temporaryNode; // 创建一个临时指针指向删除结点 if (isEmpty() == true) { cout << "该栈为空！" << endl; return false; } else { temporaryNode = top->next; x = temporaryNode->data; // 以引用返回 top->next = temporaryNode->next; delete temporaryNode; // 释放空间 return true; } } template inline bool chainStack ::isEmpty() { if (top->next == NULL) { // top指针的下一结点是否为空，以此来判断是否为空 return true; } else { return false; } } template inline bool chainStack ::getTop(T& x) { if (isEmpty() == true) { return false; } else { x = top->next->data; return true; } } template inline void chainStack ::printChainStackData() { chainStackNode * pMove; pMove = top->next; while (pMove->next != NULL) { cout << "[" << pMove->data << "]->"; pMove = pMove->next; } cout << "[" << pMove->data << "]" << endl; }
Python有专门的模块定义了栈
from pythonds.basic.stack import Stack
| 方式 | 特点 |
|---|---|
| Stack() | 创建一个空的新栈。 不需要参数，返回一个空栈 |
| push(item) | 将一个新项添加到栈的顶部。需要 item 做参数，不返回任何内容 |
| pop() | 从栈中删除顶部项。不需要参数并返回 item 。栈被修改 |
| peek() | 从栈返回顶部项，不会删除它。不需要参数。 不修改栈 |
| isEmpty() | 测试栈是否为空。不需要参数，返回布尔值 |
| size() | 返回栈中的 item 数量。不需要参数，返回一个整数 |
class Stack: #初始化栈 def __init__(self): self.item = [] #入栈 def push(self,item): self.item.append(item) #出栈 def pop(self): return self.item.pop() #返回栈顶元素 def peek(self): return self.item[len(self.item)-1] #检查是否为空栈 def isEmpty(self): return self.item == [] #返回栈元素个数 def size(self): return len(self.item)LeetCode题目 42.接雨水
https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路双指针法：两个下标left、right，分别位于输入数组的两端，向中间移动，边移动边计算。 使用max_left作为“开始...left”的最大值，使用max_right作为“right...结尾”的最大值。
作者：腐烂的橘子
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/dong-tai-gui-hua-shuang-zhi-zhen-tu-jie-by-ml-zimi/
Python3方法# !/usr/bin/env python # coding: utf-8 import unittest from typing import List class Solution: def trap(self, height: List[int]) -> int: # 边界条件 if not height: return 0 n = len(height) left, right = 0, n - 1 # 分别位于输入数组的两端 max_left, max_right = height[0], height[n - 1] ans = 0 while left <= right: max_left = max(height[left], max_left) max_right = max(height[right], max_right) if max_left < max_right: ans += max_left - height[left] left += 1 else: ans += max_right - height[right] right -= 1 return ans class TestCase(unittest.TestCase): def test_01(self): height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] expected_results = 6 self.result = Solution() res = self.result.trap(height) self.assertEqual(res, expected_results) def test_02(self): height = [4, 2, 0, 3, 2, 5] expected_results = 9 self.result = Solution() res = self.result.trap(height) self.assertEqual(res, expected_results) if __name__ == '__main__': unittest.main()C++方法
#include735.行星碰撞#include #include using namespace std; class Solution { public: int Trap(vector & height) { int ans = 0; stack stk; int n = height.size(); for (int i = 0; i < n; ++i) { while (!stk.empty() && height[i] > height[stk.top()]) { int top = stk.top(); stk.pop(); if (stk.empty()) { break; } int left = stk.top(); int currWidth = i - left - 1; int currHeight = min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stk.push(i); } return ans; } }; int main() { Solution res; vector nums = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; cout << res.Trap(nums); }
https://leetcode-cn.com/problems/asteroid-collision/
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
解题思路直接入栈：栈为空；栈顶元素为负数；当前元素为正数。
判断入栈：栈顶元素大于abs当前元素；栈顶元素等于abs当前元素；栈顶元素小于abs当前元素。
作者：清风Python
链接：https://leetcode-cn.com/problems/asteroid-collision/solution/735xing-xing-peng-zhuang-ji-yu-zhan-qu-f-xpd1/
Python3方法# !/usr/bin/env python # coding: utf-8 import unittest from typing import List class Solution: def asteroid_collision(self, asteroids: List[int]) -> List[int]: s, p = [], 0 while p < len(asteroids): if not s or s[-1] < 0 or asteroids[p] > 0: s.append(asteroids[p]) elif s[-1] <= -asteroids[p]: if s.pop() < -asteroids[p]: continue p += 1 return s class TestCase(unittest.TestCase): def test_01(self): asteroids = [5, 10, -5] expected_results = [5, 10] self.result = Solution() res = self.result.asteroid_collision(asteroids) self.assertEqual(res, expected_results) def test_02(self): asteroids = [8, -8] expected_results = [] self.result = Solution() res = self.result.asteroid_collision(asteroids) self.assertEqual(res, expected_results) def test_03(self): asteroids = [10, 2, -5] expected_results = [10] self.result = Solution() res = self.result.asteroid_collision(asteroids) self.assertEqual(res, expected_results) def test_04(self): asteroids = [-2, -1, 1, 2] expected_results = [-2, -1, 1, 2] self.result = Solution() res = self.result.asteroid_collision(asteroids) self.assertEqual(res, expected_results) if __name__ == '__main__': unittest.main()C++方法
#include856.括号的分数#include using namespace std; class Solution { public: vector AsteroidCollision(vector & asteroids) { vector ans; // vector模拟栈 只做push_back、pop_back操作 int n = asteroids.size(); for (int i = 0; i < n; ++i) { if (ans.empty() || asteroids[i] > 0) { ans.push_back(asteroids[i]); } else { while (ans.size() && ans.back() > 0 && ans.back() < -asteroids[i]) { ans.pop_back(); // 发生碰撞 并且正数绝对值较小 删除这个正数 } if (ans.empty() || ans.back() < 0) { ans.push_back(asteroids[i]); } else if (ans.back() == -asteroids[i]) { ans.pop_back(); // 两者都删除 } } } return ans; } }; int main() { Solution res; vector asteroids = { 5, 10, -5 }; vector nums = res.AsteroidCollision(asteroids); cout << nums[0]; for (unsigned int i = 1; i < nums.size(); i++) { cout << " " << nums[i]; } }
https://leetcode-cn.com/problems/score-of-parentheses/
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分；
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串；
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
解题思路出栈给分，连续出栈第一次给分，重入栈再给分。
作者：Hypergeek
链接：https://leetcode-cn.com/problems/score-of-parentheses/solution/pythonzhan-by-louis-yuan-0whx/
Python3方法# !/usr/bin/env python
# coding: utf-8
import unittest
class Solution:
def score_of_parentheses(self, s: str) -> int:
stack = []
ans, flag = 0, False
for char in s:
if char == '(':
stack.append('#')
flag = True
else:
stack = stack[:-1]
if flag:
ans += int(2 ** len(stack))
flag = False
return ans
class TestCase(unittest.TestCase):
def test_01(self):
asteroids = '()'
expected_results = 1
self.result = Solution()
res = self.result.score_of_parentheses(asteroids)
self.assertEqual(res, expected_results)
def test_02(self):
asteroids = '(())'
expected_results = 2
self.result = Solution()
res = self.result.score_of_parentheses(asteroids)
self.assertEqual(res, expected_results)
def test_03(self):
asteroids = '()()'
expected_results = 2
self.result = Solution()
res = self.result.score_of_parentheses(asteroids)
self.assertEqual(res, expected_results)
def test_04(self):
asteroids = '(()(()))'
expected_results = 6
self.result = Solution()
res = self.result.score_of_parentheses(asteroids)
self.assertEqual(res, expected_results)
if __name__ == '__main__':
unittest.main()
C++方法
#include总结#include #include using namespace std; int ScoreOfParentheses(string s) { stack score; for (char c : s) { if (c == '(') { score.push(0); } else { if (score.top() == 0) { score.pop(); score.push(1); } else { int inScore = 0; while (score.top() != 0) { inScore += score.top(); score.pop(); } score.pop(); score.push(inScore * 2); } } } int res = 0; while (!score.empty()) { res += score.top(); score.pop(); } return res; } int main() { string str; while (cin >> str) { cout << ScoreOfParentheses(str) << endl; } }
十月的算法训练掐点完成了，算是承诺达成。
本次三道题为训练要求中“栈”的题目，首先整理了栈的知识点，同样从C++和Python两个方面展示代码实现方式。从三道leetcode题目练手，编码调试，再写测试用例，本地通过。
