栈——用顺序表实现栈操作

飞熊 • 2023年3月5日上午10:33 • Python • 阅读 78

一、线性表特点

线性表：由0个或者多个数据元素组成的有限序列
除了第一个节点（头节点），都有前驱节点
除了最后一个节点（尾节点），都有后继节点
线性表主要由顺序存储结构或者链式存储结构

一般线性表：可以自由的操作节点，例如顺序表，链表
受限制性表：对节点的操作受到限制，例如栈和队列

二、栈引入

栈特点：
1、只能对栈顶进行添加或者弹出
2、后进先出

三、栈要实现的操作

1、创建一个空栈
class Stack:
	def __init__(self):
		self.__data=[]
2、push(item)添加一个元素item到栈顶
def push(self,item):
	self.__data.append(item)
3、pop()弹出栈顶元素
def  pop(self):
	if self.is_empty():
		raise ValueError('栈为空')
	else:
		self.__data.pop()
	return self.__data
4、返回栈顶元素
def top(self):
	if self.empty():
		raise ValueError('栈为空')
	else:
		self.__data[-1]
5、判断栈是否为空
def is_empty(self):
	return self.__data==[]
6、返回栈的元素个数
def size(self):
	return len(self.__data)

四、代码块

class Stack:
    def __init__(self):
        # 把列表的最后一个元素作为栈顶
        self.__data = []

    def push(self, item):
        # 添加一个元素到栈顶
        # append insert
        self.__data.append(item)

    def pop(self):
        # 要判断栈是否为空
        if self.is_empty():
            raise ValueError('栈为空')
        return self.__data.pop()

    def top(self):
        # 要判断栈是否为空
        if self.is_empty():
            raise ValueError('栈为空')
        return self.__data[-1]

    def is_empty(self):
        return self.__data == []

    def size(self):
        return len(self.__data)


if __name__ == '__main__':
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())