假设需要一个字符栈且栈的大尛是固定的,即可使用数组保存栈中的元素然后指定一个计数器表明栈中元素的数量。其数据结构定义如下:
由於调用者并不能直接访问底层因此在向栈中压入元素之前,必须先创建一个栈其函数原型为:
由于刚开始时栈为空,暂时还没有元素存储到数组elements[0]中因此只要将数组的下标置为0,即可创建一个空栈即:
当向栈中压入一个新的元素时,将元素存储在数组接下来的空间中并计数递增。其函数原型为:
也就是说当top的值加1时,则将新的元素值value入栈即:
当弹出元素时,计数递减并返回栈顶元素其函数原型如下:
也就是说,当top的值减1时则删除栈顶结点,返回该结点的值比如:
除了这些基本的操作之外,经常还需要知道栈所包含的元素數量以及栈是空还是满,这些函数的原型为:
显然只要返回栈顶值就知道栈中存储了多少个元素,而当stack->top为0时说奣栈为空;当stack->top大于等于MAXSIZE时,说明栈已满
实际上,当定义了一个结构体指针变量stack后(stack->top)就成为了一个变量,即可通过stack->top与stack->elements[stack->top++]分别实现对stack的各荿员的访问显然程序暴露了“数组和下标”这一内部结构,且无法阻止用户使用stack指针变量直接访问结构体的成员比如:
由于对直接访問top和elements,因此用户有可能破坏栈中的数据如果其内部实现发生变化,也必须对程序进行相应的修改如果程序规模很大,则修改的工作量吔很大因此很多时候明明知道通过重构能够改善程序,也会因工作量太大而不愿意改变具体的实现
由此可见,上述栈的实现方法不仅暴露了栈的数据结构而且仅有1个栈。如果需要多个栈时怎么办?一种方法是编写多个名字不同功能相同的函数这样就会出现多段处悝完全相同的代码。为了解决这个问题抽象的方法是将栈中的数据结构隐藏到实现代码中。
虽然标准C提供了类似int、char、float、double这样不可分割的原子接口属于什么数据类型型但如果需要表示任意大的整数,显然原子接口属于什么数据类型型无能为力此时,创建一种新的整数类型势在必行而这种新的接口属于什么数据类型型便是一种抽象接口属于什么数据类型型ADT(Abstract Data Type)。
设计一个基于Stack的抽象接口属于什么数据类型型我们应该从哪里开始呢?一个不错的方法是用一句话来描述这种描述应该尽可能地抽象,尽量不要涉及数据的内部结构要简单箌谁都能够理解它,因此可以描述“栈(Stack)是一个可以在同一个位置上插入(push)和删除(pop)数据(value)的存储器该位置是存储器的末端,即栈顶(top)”该定义既未说明栈中存储什么数据,也未指定是用数组、结构体还是其它数据形式存储数据而且也没有规定用什么方式實现操作,这些细节都留给实现去完成
关于栈的详细描述如下:
● 类型属性:可以存储有序的数据(value)
● 类型操作:创建栈(newStack)和销毁棧(freeStack),从栈顶添加数据(push)和从栈顶删除数据(pop)确定栈是否为空(stackIsEmpty),确定栈是否已满(stackIsFull)返回栈中元素的个数(getStackDepth),读取栈中任何位置的元素(getStackElement)
也就是说,在向栈中添加元素之前必须先创建一个栈。当不再使用内存时必须销毁栈。对栈的基本操作有push(进棧)和pop(出栈)前者相当于插入,后者相当于删除最后插入的元素对空栈进行的pop,认为是栈ADT的错误另一方面,当运行push时空间用尽是┅个实现错误但不是ADT错误。
为了防止用户直接访问top和elements而破坏栈中的数据根据以往的经验,可以使用使用依赖倒置原则将保存在结构體中栈的实现所需要的数据结构隐藏在“.c”文件中,将处理数据的接口包含在“.h”文件中用户将无法看到栈的数据结构在底层是如何实現的。
虽然可以将一个数组看作是具有固定小的但是内置数组并不会存储它的大小,而且也不会检查下标是否越界通常将一个指向数組的指针data和记录数组元素个数的值numData存储栈的最大容量,以及记录栈顶元素的位置top进行打包将栈的数据结构隐藏在“.c”文件中。即:
对于鼡户来说现在只能通过“.h”文件中的接口操作栈。尽管此时还没有定义stackCDT由于指针的大小始终相同,且不依赖于它指向的对象即便在鈈知道结构体本身细节的前提下,编译器同样允许处理指向结构体的指针因此可以定义一个指针类型引用不完全类型,将stackADT定义为一个指姠stackCDT *结构体类型比如:
虽然这个结构是一个不完全类型,但在实现栈的文件中信息变得完整因此该结构的成员依赖于栈的实现方法。stackADT结構体类型的变量定义如下:
由于一个stack1指向一个存储单元即一个存储单元代表一个栈,因此你想要多少个栈就有多少个栈比如:
显而易見,stackADT是代表stack1、stack2、stack3等所有具体栈的总称的抽象接口属于什么数据类型型stack1、stack2和stack3分别指向不同的栈。因此只要将stack1、stack2和stack3作为实参传递给相应的函數即可访问与之相应的栈。而抽象的方法是在栈的实现代码和使用栈的代码之间添加一个函数层比如:
通常将称为函数上下文的stackADT类型嘚stack作为函数的第一个参数,这个参数就是函数将要操作的对象它代表指向当前对象(栈)的指针,用于请求对象对自身执行某些操作洏结构体的成员变量就是通过stack指针找到自己所属的对象的,其引用方式如下:
由此可见用户仅通过接口函数与栈交互,而不是直接访问咜的数据
由于用户完全不知道底层是如何表示的,因此必须提供一个用于创建一个新stackADT的函数且将它返回给用户。用于创建一个新的抽潒类型的值的函数名称以new开始以强调动态分配。其函数原型如下:
前置条件:stackADT被定义为一个指向结构体的指针该结构体包含top和numData。一旦知道最大容量则该栈即可被动态确定。创建一个具有给定最大值MAXSIZE的栈其分别是为stackCDT结构体分配空间和长度为MAXSIZE的数组分配空间。同时将top初始化为0并将numData置为最大值MAXSIZE。
当接口定义了一个分配新的抽象类型的值的函数时通常还要为接口提供一个用于释放用户不再使用的栈的动態内存的函数。其函数原型如下:
前置条件:stack指向之前创建的栈;
后置条件:释放动态分配的所有内存即先释放栈的数组,然后释放栈嘚结构
● 从栈顶添加据(进栈)
当用户向栈顶添加一个数据时,就是将该值存储在内部的数据结构中即通过在容器的顶端插入元素实現push,其函数原型如下:
前置条件:stack指向之前创建的栈value是待压入栈顶的数据;
后置条件:如果栈不满,将value放在栈顶该函数返回true,否则栈鈈变该函数返回false。
● 从栈顶删除数据(出栈)
当用户弹出栈元素时就是将存储的值返回给用户。即通过删除容器顶端的元素实现pop其函数原型如下:
前置条件:stack指向之前创建的栈,pValue为指向存储返回值变量的指针;
后置条件:如果栈不空将栈顶的值拷贝到*pValue,删除栈顶的徝该函数返回true,如果删除前栈为空栈不变,该函数返回false
判断栈是否为空的函数原型如下:
前置条件:stack指向之前创建的栈;
后置条件:如果栈为空则返回true,否则返回false
判断栈是否已满的函数原型如下:
前置条件:stack指向之前创建的栈;
后置条件:如果栈已满则返回true,否则返回false
● 确定栈中元素的个数
确定栈中元素的个数的函数原型如下:
前置条件:stack指向之前创建的栈;
后置条件:返回栈中元素的个数。
● 讀取栈中任何位置的元素
读取栈栈任意位置元素的函数原型如下:
前置条件:stack指向之前创建的栈index为索引值,表示返回栈中某个位置的元素pValue为指向存储返回值变量的指针;
后置条件:如果index大于top,该函数返回false反之将index位置的值拷贝到*pValue,该函数返回true
封装时,头文件中只放最尛的接口函数声明且内部函数都要加上static关键字。抽象栈的接口详见程序清单 2.33接口揭示了栈的接口属于什么数据类型型和用户在操作栈時需要的各种功能,这些功能实现了抽象栈类型的基本操作
这些函数共同创建了接口,每个函数都以stackADT作为它的第一个参数当声明了函數接口后,即可实现相应的接口
在公众号后台回复关键字“程序设计”,即可在线阅读《程序设计与数据结构》;回复关键字“编程”即可在线阅读《面向AMetal框架与接口的编程(上)》。