栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说,栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出(FILO)的线性表。在栈中进行插入和删除操作的一端称为栈顶(top),相应地,另一端称为栈底(bottom)。不含数据元素的栈称为空栈。

  1. 初始化栈InitStack(S):创建一个空栈S。
  2. 判断空栈StackEmpty(S):当栈为空栈时返回“真”,否则返回“假”。
  3. 入栈Push(S,X)将元素x加入栈顶,并更新栈顶指针。
  4. 出栈Pop(S):将栈顶的元素从栈中删除,并且更新栈顶指针。
  5. 读栈顶元素Top(S):返回栈顶元素的值,但不修改栈顶的指针。

(1)栈的顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下,需要预先定义或申请栈的存储空间,也就是说栈空间的容量是有限的。因此在顺序栈中,当一个元素入栈时,需要判断是否栈满(即栈空间中没有空闲单元),若栈满,则元素入栈会发生上溢现象。

(2)栈的链式存储。为了克服顺序存储的栈可以存在上溢的不足,可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行,因此不必另外设置头指针,链表的头指针就是栈顶指针。

import random


class node:
    def __init__(self, pointer=None, data=None):
        self.next = pointer
        self.data = data

#  链栈
class stack:
    def __init__(self):
        self.head = node()
        self.tail = self.head
        self.length = 0

    def stackEmpty(self):
        if self.head == self.tail:
            return True
        return False

    def push(self, data):
        new_node = node(data=data)
        self.tail.next = new_node
        self.tail = new_node
        self.length += 1

    def pop(self):
        tmp_pointer = self.head
        for i in range(self.length - 1):
            tmp_pointer = tmp_pointer.next
        data = self.tail.data
        self.tail = tmp_pointer
        self.tail.next = None
        self.length -= 1
        return data

    def top(self):
        return self.tail.data


if __name__ == '__main__':
    s = stack()
    a = [random.randint(1, 400) for i in range(20)]
    for i in range(len(a)):
        print(a[i], end=' ')
        s.push(a[i])
    print()
    print(s.stackEmpty())
    print(s.length)
    print(s.tail.data)
    print(s.top())
    for i in range(len(a)):
        print(s.pop(), end=' ')
    print()
    print(s.stackEmpty())

声明:Hello World|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 -


我的朋友,理论是灰色的,而生活之树是常青的!