数据结构03-栈

• 2022 年 5 月 2 日
• 筆記
• 数据结构

顺序栈

1、基本概念

栈是限定仅在表尾进行插入或删除操作的线性表，表末端为栈顶(Top)，表头称为栈顶(Bottom),不含元 素称为空战 (用顺序表存储的栈更常见) 因此栈又称为后进先出(Last in First out, LIFO)的线性表。

2、数据类型定义

//顺序栈ADT
typedef struct SequenceStack
{
    // 栈底
    int *base;
    // 栈顶
    int *top;
}SequenceStack;

3、功能实现

bool InitStack(SequenceStack &S){
    S.base=new int[Maxsize];       //为顺序栈分配一个最大容量为Maxsize的空间
	if(!S.base)                    //空间分配失败
		return false;
	S.top=S.base;                 //top初始为base，空栈
	return true;
}

bool Push(SequenceStack &S,int e){
    if(S.top-S.base==Maxsize)      //栈满
		return false;
	*(S.top++)=e;                 //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
	return true;
}

bool Pop(SequenceStack &S,int e){
    if(S.top == S.base)      //栈空
		return false;
	e = *(--S.top);                 //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
	return true;
}

int GetTop(SequenceStack S){          //取栈顶 
	if(S.top!=S.base)          //栈非空
		return *(S.top-1);     //返回栈顶元素的值，栈顶指针不变
    else
        return -1;
}

3、测试代码

int main(){
   int n,x;
	SequenceStack S;
	InitStack(S);//初始化一个顺序栈S
	cout<<"请输入元素个数n："<<endl;
	cin>>n;
	cout<<"请依次输入n个元素，依次入栈："<<endl;
	while(n--){
		cin>>x; //输入元素
		Push(S,x);
	}
	cout<<"元素依次出栈："<<endl;
	while(S.top!=S.base){//如果栈不空，则依次出栈
        cout<<GetTop(S)<<"\t";//输出栈顶元素
        Pop(S,x);   //栈顶元素出栈
    }
	return 0;
}