第3章之3.1-栈(操作受限线性表)的基本概念和常规操作(底层)

Stack Opera

一个非常有用的概念-栈(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运行逻辑,验证正确性、可行性:

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注


皖ICP备2021003932号
召唤伊斯特瓦尔