一个非常有用的概念-栈(Stack),也很好理解,关键是,能够经常用得到,虽然之前写代码很少用(Data_Structure早忘光了)
1.抽象数据类型-“栈”
PS:限定在表尾插入或删除的线性表
S = (a1,a2,a3,…,an),通常S包含的主要数据结构有,指针和容量,即栈底指针base,栈顶指针top,容量stacksize
typedef struct {
SElemType* base;
SElemType* top;
int stack_size;
}SqStack;
数据类型SElemType可自己指定,上述结构对象面向“栈定义”,这里采用最基本的数据类型int作为代换量
typedef int SElemType;
2.建“栈”问题
“栈”操作实际上归结于指针top和base,这二者加上stacksize即可完成基本的operation,需要明白的是:
- 初始化以内存容量(base)
- 初始化top
- 赋值stack-size
- 运动top完成入、出、取、定位、遍历等诸多操作
S.top = S.base;
S.stack_size = STACK_INIT_SIZE;
PS:栈顶指针top始终位于栈顶元素的下一个位置,因此:
Current_size = S.top-S.base
if(S.top-S.base>=STACK_INIT_SIZE)return OVERFLOW;
入栈、出栈、遍历、提取、扩容等,注意栈顶指针top位置,必须准确!
3.实际操作(顺序栈)
上为初始化“栈”空间,Init_Space_Stack,下述分别为取栈顶元素、出栈、遍历
取栈顶元素+出栈:
Status Pop(SqStack& S, SElemType& e)
{
if (S.top==S.base)
{
return ERROR;
}
e = *(S.top-1);
S.top--;
return OK;
}
出栈操作有两方面,一是下移top指针位置(注意数据类型),二是提取出栈元素(同数据类型:SElemType),借助“引用操作”很容易实现”
遍历问题:
number = S.top-S.base
SElemType* p;
入栈操作(important):
栈-是不能随便入的,主要是考虑几个问题:
- 容量是否已达极限
- 如何扩容
- 扩容后栈顶指针top需及时更改
- 扩容后注意更改stack-size
S.top-S.base>=STACK_INIT_SIZE
S.base = (SElemType*)realloc(S.base,(S.stack_size + STACKINCREMENT) * sizeof(SElemType));
关于“realloc”?
S.top = S.base + S.stack_size;
S.stack_size += STACK-INCREMENT;
Vs运行逻辑,验证正确性、可行性: