栈 和 队列

1、栈和队列的概述

栈和队列主要用于计算过程中数据的临时保存。如果需要存储的数据项数不能够事先确定，就必须采用更复杂的存储机制和管理，这种存储机制称为缓冲存储或者缓存。栈和队列就是使用最多的缓冲存储结构

栈和队列也是最简单的缓存结构，他们只支持数据项的存储和访问。

栈和队列作为数据结构需要提供几个基本的操作，如：创建，检查空。检查满等

栈是保证元素的后进先出LIFO，队列是元素的先进先出FIFO，对于栈或队列，在任何时候，下一次访问或/和删除的元素都默认地唯一确定。只有新的存入或删除操作才会改变下一次默认访问的元素。

实现栈或队列最简单的技术就是用元素存储的顺序表示他们存储的时间

2、栈的描述及抽象数据类型

栈是一种容器，可存入数据元素、访问元素、删除元素。

栈的定义操作包括：栈的创建、判断栈是否为空、将栈元素亚茹栈中、从栈中弹出元素并将其返回、以及检查栈元素

采用顺序表实现栈时候的问题：1.是采用简单顺序表还是采用动态顺序表？2、如果采用简单的顺序表就会出现栈满的情况，而如果采用动态顺表存储区满时可以更换更大的存储区。单这时又会出现存储区置换策略的问题

为了更清晰的理解使用python的list构建一个栈

class mystock:

    def __init__(self):
        self._elem = []
    
    def is_empty(self):
        if not len(self._elem):
            return True
        else:
            return False
    
    def top(self):
        if not len(self._elem):
            raise Stockisempty
        return self._elem[-1]
    
    def pop(self):
        if not len(self._elem):
            raise Stockisempty
        return self._elem.pop()

    def push(self, elem):
        self._elem.append(elem)

View Code

栈 和 队列

原文：https://www.cnblogs.com/bianjing/p/10369624.html