数据结构之栈(python)

^~^前行者~~~ 2024-10-23 13:35:01 阅读 98

栈(顺序栈与链栈)

1.栈存储结构1.1栈的基本介绍1.2进栈和出栈1.3栈的具体实现1.4栈的应用例一例二例三

2.顺序栈及基本操作(包含入栈和出栈)2.1顺序栈的基础介绍2.2顺序栈元素`入栈`2.3顺序栈元素`出栈`2.4顺序栈的表示和实现

3.链栈及基本操作(包含入栈和出栈)3.1链栈的基本介绍3.2链栈元素入栈3.3链栈元素出栈3.4链栈的表示和实现

4.栈的应用4.1括号匹配问题4.2十进制转二进制4.3十进制转N进制

1.栈存储结构

<code>栈和队列,严格意义上来说,也属于线性表,因为它们也都用于存储逻辑关系为 一对一 的数据。使用栈结构存储数据,讲究“先进后出”,即最先进栈的数据,最后出栈;使用队列存储数据,讲究 “先进先出”,即最先进队列的数据,也最先出队列。既然栈和队列都属于线性表,根据线性表分为顺序表链表的特点,也可分为顺序栈链栈队列也分为顺序队列链队列

1.1栈的基本介绍

顺序表链表一样,也是用来存储逻辑关系为 “一对一” 数据的线性存储结构,如图1所示:

在这里插入图片描述

<code>栈只能从表的一端存取数据另一端封闭的在中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图1来说,从图中数据的存储状态可判断出,元素 1最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3元素 2 从栈中取出,然后才能成功取出元素 1我们可以给下一个定义,即是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构通常开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指的就是距离栈顶最近的元素,拿图2 来说,栈顶元素元素 4;同理,栈底元素指的是位于栈最底部的元素图2 中的栈底元素元素 1

在这里插入图片描述

1.2进栈和出栈

向<code>栈中添加元素,此过程被称为"进栈"(入栈压栈)从提取指定元素,此过程被称为"出栈"(或弹栈

1.3栈的具体实现

顺序栈:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构链栈:采用链式存储结构实现栈结构

两种实现方式的区别,仅限于数据元素实际物理空间上存放的相对位置顺序栈底层采用的是数组链栈底层采用的是链表

1.4栈的应用

例一

我们经常使用浏览器各种网站上查找信息。假设先浏览页面 A,然后关闭了页面 A 跳转到页面 B,随后又关闭页面 B 跳转到了页面 C。而此时,我们如果想重新回到页面 A,有两个选择:

重新搜索找到页面 A;使用浏览器的"回退"功能。浏览器会先回退页面 B,而后再回退到页面 A

浏览器 “回退” 功能的实现底层使用的就是栈存储结构。当你关闭页面 A 时,浏览器会将页面 A入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是中数据依次出栈的效果。

例二

不仅如此,栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号小括号、中括号和大括号),括号错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构

例三

同时,栈结构还可以实现数值进制转换功能。例如,编写程序实现从十进制数自动转换成二进制数,就可以使用栈存储结构来实现。

2.顺序栈及基本操作(包含入栈和出栈)

2.1顺序栈的基础介绍

如果你仔细观察顺序表底层实现是数组)和栈结构就会发现,它们存储数据的方式高度相似,只不过对数据的存取过程有特殊的限制,而顺序表没有。

在这里插入图片描述

这里给出使用<code>顺序表模拟栈存储结构常用的实现思路,即在顺序表中设定一个实时指向栈顶元素变量(一般命名为 top),top 初始值为 -1,表示中没有存储任何数据元素,及栈是"空栈"。一旦有数据元素,则 top 就做 +1 操作;反之,如果数据元素出栈top 就做 -1 操作。

2.2顺序栈元素入栈

模拟栈存储 {1,2,3,4}过程。最初,是"空栈",即数组的,top 值为初始值 -1,如图 3 所示:

在这里插入图片描述

首先向<code>栈中添加元素 1,我们默认数组下标为 0 一端表示栈底,因此,元素 1 被存储在数组 a[1] 处,同时 top+1,如图 4 所示:

在这里插入图片描述

采用以上的方式,依次存储<code>元素 2、3 和 4,最终,top 值变为 3,如图 5 所示:

在这里插入图片描述

2.3顺序栈元素<code>出栈

其实,top 变量设置对模拟数据的 “入栈” 操作没有实际的帮助,它是为实现数据的 “出栈” 操作做准备的

在这里插入图片描述

<code>注意,图 6 数组中元素的消失仅是为了方便初学者学习,其实,这里只需要对 top 值做 -1 操作即可,因为 top本身就表示栈的栈顶位置,因此 top - 1等同于栈顶元素出栈。并且后期添加元素时,新元素会存储在类似元素 4 这样的旧元素位置上,将旧元素覆盖

2.4顺序栈的表示和实现

实现的基本功能:

初始化空栈判断是否为返回栈顶元素返回栈的长度进栈出栈清空栈

代码实现

class sqStack:

# 初始化栈

def __init__(self, MAXSIZE):

self.MAXSIZE = MAXSIZE

self.data = [None] * self.MAXSIZE

self.top = -1

# 判断当前栈是否为空

def is_empty(self):

return self.top == -1

# 返回栈顶元素

def gettop(self):

if self.is_empty():

print("当前顺序栈为空")

return None

else:

return self.data[self.top]

# 入栈

def Push(self,item):

# 判断栈是否满

if self.top == self.MAXSIZE - 1:

return "sqStack is full"

self.data[self.top + 1] = item

self.top += 1

# 列表入栈

def ListPush(self,lst):

# 判断栈是否满

if self.top == self.MAXSIZE - 1:

return "sqStack is full"

for i in range(len(lst)):

self.Push(lst[i])

# 出栈

def Pop(self):

# 判断栈是否为空

if self.is_empty():

return "sqStack is empty"

rs = self.data[self.top]

self.top -= 1

return rs

# 计算栈的长度

def size(self):

return self.top + 1

# 输出栈内元素

def display(self):

# 判断栈是否为空

if self.is_empty():

print("当前顺序栈为空", end=" ")code>

else:

print("当前链表元素为:", end="")code>

for i in range(self.top + 1):

print(self.data[i], end=" ")code>

print()

# 清空栈

def clear(self):

self.data = [None] * self.MAXSIZE

self.top = -1

# 初始化一个长度为20的顺序栈

s = sqStack(20)

print("初始化:", s)

print("----------------------")

# 判断当前栈是否为空

print("当前栈是否为空:", s.is_empty())

print("----------------------")

# 输出栈的元素

s.display()

print("----------------------")

print("入栈前栈内元素:",end="")code>

s.display()

# 入栈

s.Push(1)

s.Push(10)

s.Push(100)

# 输出当前栈内的元素

print("入栈后栈内元素:", end="")code>

s.display()

print("----------------------")

print("当前栈的长度为:", s.size())

print("----------------------")

print("队列入栈前栈内元素:", end="")code>

s.display()

s.ListPush([1,2,3,4])

print("队列入栈后栈内元素:", end="")code>

s.display()

print("----------------------")

print("当前栈顶元素为:",s.gettop())

print("----------------------")

# 顶端元素出栈

print("出栈前栈内元素:",end="")code>

s.display()

print("出栈元素为:", s.Pop())

print("出栈后栈内元素:", end="")code>

s.display()

print("----------------------")

#输出当前栈内的元素

s.display()

print("----------------------")

s.clear()

s.display()

print("----------------------")

初始化: <__main__.sqStack object at 0x000002A011B38460>

----------------------

当前栈是否为空: True

----------------------

当前顺序栈为空

----------------------

入栈前栈内元素:当前顺序栈为空

入栈后栈内元素:当前链表元素为:1 10 100

----------------------

当前栈的长度为: 3

----------------------

队列入栈前栈内元素:当前链表元素为:1 10 100

队列入栈后栈内元素:当前链表元素为:1 10 100 1 2 3 4

----------------------

当前栈顶元素为: 4

----------------------

出栈前栈内元素:当前链表元素为:1 10 100 1 2 3 4

出栈元素为: 4

出栈后栈内元素:当前链表元素为:1 10 100 1 2 3

----------------------

当前链表元素为:1 10 100 1 2 3

----------------------

当前顺序栈为空

----------------------

3.链栈及基本操作(包含入栈和出栈)

3.1链栈的基本介绍

通常我们将链表头部作为栈顶尾部作为栈底

在这里插入图片描述

将<code>链表头部作为栈顶一端,可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作

链表的头部作为栈顶,意味着:

在实现数据"入栈"操作时,需要将数据链表头部插入在实现数据"出栈"操作时,需要删除链表头部首元节点

因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表

3.2链栈元素入栈

例如,将元素 1、2、3、4 依次入栈等价于各元素采用头插法依次添加链表中,每个数据元素的添加过程如图 2 所示:

在这里插入图片描述

3.3链栈元素出栈

例如,<code>图2 所示的链栈中,若要将元素 3 出栈,根据"先进后出"的原则,要先将元素 4 出栈,也就是从链表摘除,然后元素 3 才能出栈,整个操作过程如图 3 所示:

在这里插入图片描述

3.4链栈的表示和实现

实现基本功能:

初始化<code>空栈判断是否为返回栈顶元素进栈出栈清空栈

代码实现

# 定义链栈节点

class Node:

# 初始化链栈

def __init__(self, data):

self.data = data

self.next = None

class linkstack:

# 初始化链栈

def __init__(self):

self.top = None

# 判断链栈是否为空

def is_empty(self):

return self.top == None

# 清空链栈

def clear(self):

self.top = None

# 返回当前栈的长度

def size(self):

i = 0

tempnode = self.top

while tempnode is not None: # 从头开始遍历

tempnode = tempnode.next

i += 1

return i

# 元素入栈

def push(self, item):

node = Node(item)

node.next = self.top

self.top = node

# 栈顶元素出栈

def pop(self):

x = self.top.data

self.top = self.top.next

return x

# 获取栈顶元素

def gettop(self):

return self.top.data

# 输出当前栈内元素

def display(self):

if self.top == None:

print("当前栈内元素为空", end="")code>

else:

print("当前栈内元素为:", end="")code>

tempnode = self.top

while tempnode is not None:

print(tempnode.data, end=" ")code>

tempnode = tempnode.next

print()

s1 = linkstack()

print("初始化的栈为:", s1)

print("------------------------")

print("入栈前的链栈元素为:", end="")code>

s1.display()

s1.push(1)

s1.push(2)

s1.push(3)

s1.push(4)

s1.push(5)

s1.push(6)

print("入栈后的链栈元素为:", end="")code>

s1.display()

print("------------------------")

print("当前栈顶元素为:",s1.gettop())

print("------------------------")

print("当前链栈的长度为:", s1.size())

print("------------------------")

print("出栈前的链栈元素为:", end="")code>

s1.display()

print("出栈元素为:", s1.pop())

print("出栈后的链栈元素为:", end="")code>

s1.display()

print("------------------------")

print("清空前的链栈元素为:", end="")code>

s1.display()

s1.clear()

print("清空后的链栈元素为:", end="")code>

s1.display()

print("------------------------")

print("当前链栈是否为空:", s1.is_empty())

print("------------------------")

初始化的栈为: <__main__.linkstack object at 0x0000023734D08460>

------------------------

入栈前的链栈元素为:当前栈内元素为空

入栈后的链栈元素为:当前栈内元素为:6 5 4 3 2 1

------------------------

当前栈顶元素为: 6

------------------------

当前链栈的长度为: 6

------------------------

出栈前的链栈元素为:当前栈内元素为:6 5 4 3 2 1

出栈元素为: 6

出栈后的链栈元素为:当前栈内元素为:5 4 3 2 1

------------------------

清空前的链栈元素为:当前栈内元素为:5 4 3 2 1

清空后的链栈元素为:当前栈内元素为空

------------------------

当前链栈是否为空: True

------------------------

4.栈的应用

4.1括号匹配问题

括号匹配问题:给一个字符串,其中包含小括号、中括号、大括号,求该字符串中的括号是否匹配

思路

如果遇到左括号,都进栈;遇到右括号,查看栈顶是否为对应左括号,如果是对应左括号则该对应左括号出栈,如果是空栈false,如果是不对应左括号false。等遍历整个字符串后,查看是否为,如果为括号匹配成功,如果不为空括号匹配失败

# 定义顺序栈

class sqStack:

# 初始化栈

def __init__(self, MAXSIZE):

self.MAXSIZE = MAXSIZE

self.data = [None] * self.MAXSIZE

self.top = -1

# 判断当前栈是否为空

def is_empty(self):

return self.top == -1

def gettop(self):

if self.is_empty():

print("当前顺序栈为空")

return None

else:

return self.data[self.top]

# 入栈

def Push(self, item):

# 判断栈是否已满

if self.top == self.MAXSIZE - 1:

return "sqStack is full."

self.data[self.top + 1] = item

self.top += 1

# 列表入栈

def ListPush(self, x):

# 判断栈是否已满

if self.top == self.MAXSIZE - 1:

return "sqStack is full."

for i in range((len(x))):

self.Push(x[i])

# 出栈

def Pop(self):

# 判断栈是否为空

if self.is_empty():

return "sqStack is empty"

rs = self.data[self.top]

self.top -= 1

return rs

# 输出栈的长度

def size(self):

return self.top + 1

# 输出栈内元素

def display(self):

# 判断栈是否为空

if self.is_empty():

print("当前顺序栈为空", end=" ")code>

else:

print("当前链表元素为:", end="")code>

for i in range(self.top + 1):

print(self.data[i], end=" ")code>

print()

# 清空栈

def clear(self):

self.data = [None] * self.MAXSIZE

self.top = -1

def matching(strings): # 输入是一串字符

bktStack = sqStack(60) # 创建类实例

flag = 1

opens = "{[("

closes = "}])"

# 对于每个输入字符

for i in strings:

# 遇到左括号,就将其压栈

if i in opens:

bktStack.Push(i)

# 遇到右括号

elif i in closes:

# 若已没左括号与之匹配

if bktStack.is_empty():

# 不匹配,结束

return False

# 左括号按什么顺序入,右括号应按相反顺序消掉。

# 如果匹配,右括号消的始终是栈顶括号。

# 弹栈bktStack.pop(),判断栈顶左括号与当前右括号是否匹配

if closes.index(i) != opens.index(bktStack.Pop()):

# 不匹配,结束

return False

# 若一直没有return而是遍历了一遍,且没有多余左括号留在栈中,则说明匹配。反之不匹配。

return bktStack.is_empty()

# 判断返回的是True还是False

def check(strings):

if matching(strings):

print("%s 匹配正确!" % strings)

else:

print("%s 匹配错误!" % strings)

if __name__ == "__main__":

# 测试函数

for i in range(4):

stringa = input()

check(stringa)

{ -- -->{ ([][])}()}

{ { ([][])}()} 匹配正确!

[[{ { (())}}]]

[[{ { (())}}]] 匹配正确!

[[(()(()))])]{ }

[[(()(()))])]{ } 匹配错误!

4.2十进制转二进制

当将一个十进制整数M转换为二进制数时,在计算过程中,把M与2求余得到的二进制数的各位依次进栈,计算完毕后中的二进制数依次出栈输出,输出结果就是待求得的二进制数

测试案例:

[200, 254, 153, 29, 108, 631, 892]

运行结果

在这里插入图片描述

代码实现:

<code>class sqStack:

# 初始化栈

def __init__(self, MAXSIZE):

self.MAXSIZE = MAXSIZE

self.data = [None] * MAXSIZE

self.top = -1

# 判断当前栈是否为空

def is_empty(self):

return self.top == -1

# 返回栈顶元素

def gettop(self):

if self.is_empty():

print("当前顺序栈为空")

return None

else:

return self.data[self.top]

# 入栈

def Push(self, item):

# 判断栈是否已满

if self.top == self.MAXSIZE - 1:

return "sqStack is full"

self.data[self.top + 1] = item

self.top += 1

# 列表入栈

def ListPush(self, x):

# 判断栈是否已满

if self.top == self.MAXSIZE - 1:

return "sqStack is full"

for i in range(len(x)):

self.Push(x[i])

# 出栈

def Pop(self):

# 判断栈是否为空

if self.is_empty():

return "sqStack is empty"

rs = self.data[self.top]

self.top -= 1

return rs

# 输出栈的长度

def size(self):

return self.top + 1

# 输出栈内元素

def display(self):

# 判断栈是否为空

if self.is_empty():

print("当前顺序栈为空", end=" ")code>

else:

print("当前链表元素为:", end="")code>

for i in range(self.top + 1):

print(self.data[i], end=" ")code>

print()

# 清空栈

def clear(self):

self.data = [None] * self.MAXSIZE

self.top = -1

s = sqStack(20)

data = int(input("请输入十进制数:"))

while data != 0:

ys = data % 2

s.Push(ys)

data = data // 2

while s.top != -1:

print(s.Pop(), end="")code>

请输入十进制数:200

11001000

请输入十进制数:254

11111110

请输入十进制数:153

10011001

请输入十进制数:29

11101

请输入十进制数:108

1101100

请输入十进制数:631

1001110111

请输入十进制数:892

1101111100

4.3十进制转N进制

当将一个十进制整数M转换为N进制数时,在计算过程中,把M与N求余得到的N进制数的各位依次进栈,计算完毕后将栈中N进制数依次出栈输出,输出结果就是待求得的N进制数

测试案例:

测试数:[200, 254, 153, 29, 108, 631, 892]进制:[4, 8, 16]

自由搭配即可,这里我主要使用了random.choice()来对测试数要转换的进制随机取数

代码实现:

class sqStack:

# 初始化栈

def __init__(self, MAXSIZE):

self.MAXSIZE = MAXSIZE

self.data = [None] * MAXSIZE

self.top = -1

# 判断当前栈是否为空

def is_empty(self):

return self.top == -1

# 返回栈顶元素

def gettop(self):

if self.is_empty():

print("当前顺序栈为空")

return None

else:

return self.data[self.top]

# 入栈

def Push(self, item):

# 判断栈是否已满

if self.top == self.MAXSIZE - 1:

return "sqStack is full"

self.data[self.top + 1] = item

self.top += 1

# 列表入栈

def ListPush(self, x):

# 判断栈是否已满

if self.top == self.MAXSIZE - 1:

return "sqStack is full"

for i in range(len(x)):

self.Push(x[i])

# 出栈

def Pop(self):

# 判断栈是否为空

if self.is_empty():

return "sqStack is empty"

rs = self.data[self.top]

self.top -= 1

return rs

# 输出栈的长度

def size(self):

return self.top + 1

# 输出栈内元素

def display(self):

# 判断栈是否为空

if self.is_empty():

print("当前顺序栈为空", end=" ")code>

else:

print("当前链表元素为:", end="")code>

for i in range(self.top + 1):

print(self.data[i], end=" ")code>

print()

# 清空栈

def clear(self):

self.data = [None] * self.MAXSIZE

self.top = -1

def divideByN(number, base):

digits = "0123456789ABCDEF"

remstack = sqStack(100)

while number > 0:

rem = number % base

remstack.Push(rem)

number = number // base

newString = ""

while not remstack.is_empty():

newString = newString + digits[remstack.Pop()]

return newString

import random

numbers = [200,254,153,29,108,631,892]

bases = [4,8,16]

for number in numbers:

base = random.choice(bases)

print(f"{number} 的 {base}进制数为:{divideByN(number, base)}")

200 的 16进制数为:C8

254 的 4进制数为:3332

153 的 4进制数为:2121

29 的 4进制数为:131

108 的 16进制数为:6C

631 的 8进制数为:1167

892 的 8进制数为:1574



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。