栈的基本操作

Love The Way You Lie 2024-03-16 19:55 55阅读 0赞

**问题**

在数据结构的学习中，栈是一个重要的部分，我们知道栈（stack）是一种线性表结构，只允许在表的一端进行插入和删除操作的线性表。简单来说，栈一种后进先出的线性表，简称为LIFO结构。那么它的基本操作有哪些，如何应用栈的知识呢？

**方法**

（1）首先栈是一个线性表。栈中允许插入和删除的一端成为栈顶（top）；另一段则成为栈底（bottom）。当表中没有任何元素时，称为空栈。

（2）基本操作：定义节点类；赋值；查找第i个结点；前插法；尾插法；第i个结点前插入；删除第i个结点；遍历。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>#定义结点类 class LinkNode: &nbsp; &nbsp;#self.data 类的成员变量 #(data,...) 形参 def __init__(self,data=-1,next=None): &nbsp; &nbsp; &nbsp; self.data = data &nbsp; &nbsp; &nbsp; self.next = next #第一步 n5 = LinkNode() n5.data = 5 n5.next = None n4 = LinkNode() n4.data = 4 n4.next = n5 n3 = LinkNode() n3.data = 3 n3.next = n4 n2 = LinkNode() n2.data = 2 n2.next = n3 n1 = LinkNode() n1.data = 1 n1.next = n2 head = LinkNode() head.data = -1 head.next = n1 #查找第i个结点 i = 3 p = head for k &nbsp;in range(i): &nbsp; &nbsp;p = p.next print(p.data) #前插法 for i in range(1,101): &nbsp; &nbsp;q = LinkNode() &nbsp; &nbsp;q.data = i &nbsp; &nbsp;q.next = None &nbsp; &nbsp;q.next = head.next head.next = q #尾插法 for i in range(1,101): &nbsp; &nbsp;q = LinkNode() &nbsp; &nbsp;q.data = i &nbsp; &nbsp;q.next = None &nbsp; &nbsp;p.next = q &nbsp; &nbsp;p = p.next #第十个结点前插入999 i = 9 p = head for k in range(i): &nbsp; &nbsp;p &nbsp;= p.next q = LinkNode() q.data = 999 q.next = p.next p.next = q #删除第10个结点 i = 9 p = head for k in range(i): &nbsp; &nbsp;p = p.next p.next = p.next.next #遍历 p = head while p.next!=None: &nbsp; &nbsp;p=p.next &nbsp; &nbsp;print(p.data)</td> 
 </tr> 
 </tbody> 
</table>

**结语**

针对栈的基本知识，以及如何运用栈的基本操作等问题，提出上述几个方面的知识和操作，通过亲自实验，证明该方法是有效的，本文使用这种方法解决了如何查找第i个结点，删除结点，遍历等问题，但方法并不简便，还有考虑不周的地方，未来可以继续研究更加简洁方便的代码进行处理。