重学数据结构之栈

一、前言简介

  数据结构课程是一门重要的计算机基础课程,而我本人在上学期间真是没学好这门课, 听课总是听得云里雾里的,写起代码来也不知道如何编写和运用这些数据结构,以致于后来考试也只能是低分飘过,所以现在就需要花时间重新学习一下数据结构了!

  为了能够更好地学习和掌握数据结构,除了学习和理解相应的概念,我还会找几个题目并用所学的数据结构来解决问题,相应的问题和代码也会一并记录在博客中。

 

二、栈的概念

1.基本概念

  栈(stack)又被称为堆栈,是一种保存数据元素的容器。栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表,允许进行插入和删除操作的一端叫做栈顶(top),另一端则叫做栈底(bottom),插入元素一般称为进栈(PUSH),删除元素一般称为出栈(POP)。

  栈按照后进先出的原则(LIFO, Last In First Out)存储数据,后存入的元素会先被取出来使用。存入栈中的元素相互之间并没有任何具体的关系,只有存入的时间先后顺序,而没有元素的前后顺序或者元素的位置等概念。

2.抽象数据类型

  栈的基本操作一个封闭的数据集合,在一个栈里需要实现将元素压入栈中即进栈、从栈中弹出元素即出栈、返回最后一个插入栈中的元素、获取栈中元素的数量等方法,下面就是一个栈的抽象数据类型描述:

ADT Stack:

  Stack(self)  # 创建一个空栈

  empty(self)  # 判断栈是否为空

  push(self, x)  # 将元素压入栈中

  pop(self)  # 从栈中弹出元素

  peek(self)  # 返回最后一个插入的元素

  size(sellf)  # 获取栈中元素的数量

3.用 Python 实现

  在 Python 中没有栈这种数据结构,但我们可以借助 list 来实现,用 list 来存放数据,并实现一个栈所需要的各种方法,具体代码如下:

 1 # 自定义栈
 2 class MyStack:
 3     def __init__(self):
 4         self.data = []
 5 
 6     def push(self, x):
 7         """
 8         将数据压入栈中
 9         :param x: 需要插入的元素
10         :return: 
11         """
12         self.data.append(x)
13 
14     def pop(self):
15         """
16         从栈中弹出元素
17         :return: 弹出的元素
18         """
19         if not self.empty():
20             ret, self.data = self.data[-1], self.data[:-1]
21             return ret
22         return None
23 
24     def empty(self):
25         """
26         判断栈是否为空
27         :return: 栈空--True,非空--False
28         """
29         return len(self.data) == 0
30 
31     def size(self):
32         """
33         获取栈中元素的数量
34         :return: 
35         """
36         return len(self.data)
37 
38     def peek(self):
39         """
40         返回最后一个插入的元素
41         :return: 最后一个插入的元素
42         """
43         if not self.empty():
44             return self.data[-1]
45         return None

 

三、栈的应用

1.进制转换

1)问题描述

  输入一个任意的十进制正整数,将其转化成相应的二进制、八进制和十六进制的数。

2)解决思路

  这里首先需要介绍一个公式:

N = (N div d) * d + N mod d

  其中 div 表示整除,mod 表示求余。例如当输入的正整数 N 为777,输出的进制是八进制时,计算过程如下:

N      N div 8    N mod 8

777   97       1

97     12       1

12    1     4

1      0     1  

  在进行进制转换的时候,我们就可以将每次求余的结果保存在栈中,最后将栈中的数依次取出,就是转换后的结果了,例如十进制的777转换成八进制就是1411。

3)代码实现

  如何用代码来解决这个问题?一个思路就是将每次求余的结果保存在栈中,而整除的结果则用来进行下一步的计算,直到这个整除的结果为0,表明计算结束,再出栈中依次取出元素,得到的结果就是转换成相应进制后的数。具体代码如下:

 1 def solution(n: int, scale: int):
 2     """
 3     进制转换
 4     :param n: 正整数
 5     :param scale: 进制
 6     :return:
 7     """
 8     stack = MyStack()
 9     # 循环计算
10     while n // scale >= 0 and n > 0:
11         stack.push(n % scale)
12         n = n // scale
13     # 输出
14     while not stack.empty():
15         print(stack.pop(), end="")

2.括号匹配

1)问题描述

  输入一个字符串,里面可能有“()”、“[]”和“{}”三种括号,编写程序检查该字符串中的括号是否成对出现。

2)解决思路

  遍历这个字符串,用栈来存放每次遍历的元素,如果遍历的元素和栈顶的括号是配对的,则进行出栈操作将栈顶元素弹出,反之若不配对,则进行入栈操作将该元素插入到栈中。等遍历结束后,若栈为空,则表明该字符串中的括号都是成对出现的,若栈不为空,则表明有括号不匹配。

3)代码实现

 1 def solution(input_string: str):
 2     """
 3     判断输入的字符中的括号是否成对出现
 4     :param input_string: 输入字符串
 5     :return:
 6     """
 7     def match(c1: str, c2: str):
 8         """
 9         判断两个括号是否匹配
10         :param c1: 
11         :param c2: 
12         :return: 
13         """
14         if c1 == "(" and c2 == ")":
15             return True
16         elif c1 == "[" and c2 == "]":
17             return True
18         elif c1 == "{" and c2 == "}":
19             return True
20         else:
21             return False
22 
23     stack = MyStack()
24     for i in range(len(input_string)):
25         if stack.empty():
26             # 栈空直接入栈
27             stack.push(input_string[i])
28         else:
29             # 栈非空时进行比较
30             if match(stack.peek(), input_string[i]):
31                 stack.pop()
32             else:
33                 stack.push(input_string[i])
34     print("匹配!") if stack.empty() else print("不匹配!")
© 版权声明
THE END
喜欢就支持一下吧!
点赞0
分享