技术笔试面试

玩转“栈”-相关结构和系列函数

要想编和“栈”相关的程序,就要准备好和“栈”有关的各种工具,包括定义各种栈的结构,定义各种操作栈的函数。

什么是栈?

栈,英文叫stack,是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义,称为栈顶(top),表头端称为栈底(bottom)。不含元素的空表称为空栈。

栈是后进先出的线性表(LIFO:Last in First out)。

需要准备的结构有哪些?

首先要定义两个常量:

1 存储空间初始分配量:STACK_INIT_SIZE

2 存储空间分配增量:STACK_INCREMENT

然后还要定义一个栈的结构,如下:

typedef struct{

int *base;//栈底指针,它始终指向栈底的位置,若base为NULL,则表示栈根本不存在

int *top;//栈顶指针,当top==base时表示栈空。每当插入新元素,指针top就增1.非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

int stacksize;//表示栈的当前可使用的最大容量。请注意此值代表“可使用”的容量,而并非“已使用”。

}mystack;

我们定义指针为int型,是假设栈中元素为整型,你当然可以修改这个类型为你的栈元素的类型:)

需要定义哪些操作栈的函数?

1 初始化一个空栈:init_stack(mystack &S);

2 销毁一个栈:destroy_stack(mystack &S);

3 把栈置空:clear_stack(mystack &S);

4 判断栈是否为空:is_empty_stack(mystack S); 若为空,则返回1,否则返回0

5 返回栈的元素个数,即栈的长度:length_stack(mystack S);

6 返回栈顶元素到变量e:gettop_stack(mystack S, int &e); 若栈为空则返回ERROR

7 将元素e入栈:push_stack(mystack &S, int e);

8 将元素e出栈:pop_stack(mystack &S, int &e); 若栈不空,则删除S的栈顶元素,并返回此栈顶元素到e

9 对栈中每个元素调用visit函数:traverse_stack(mystack S, void (*visit)());

over~

发表您的评论

请您放心,您的信息会被严格保密。必填项已标识 *