王道数据结构栈实现

深碍√TFBOYSˉ_ 2022-10-03 00:43 120阅读 0赞

#include<cstdio>
    #define MaxSize 50
    typedef int ElemType;
    
    typedef struct { 
    	ElemType data[MaxSize];           //栈中存放元素
    	int top;						  //栈顶指针,初始赋为-1
    }SqStack;							  //
    
    /*栈初始化*/
    void InitStack(SqStack& S) { 
    	S.top = -1;             //初始化栈顶指针-1
    }
    
    /*判栈空*/
    bool StackEmpty(SqStack S) { 
    	return S.top == -1;
    }
    
    /*元素入栈*/
    bool Push(SqStack& S, ElemType x) { 
    	if (S.top == MaxSize - 1) {           //栈满，报错
    		return false;
    	}
    	S.data[++S.top] = x;                //指针先加1，再赋值
    	return true;
    }
    
    /*弹栈*/
    bool Pop(SqStack& S, ElemType& e) { 
    	if (StackEmpty(S)) {         //栈空，报错
    		return false;
    	}
    	e = S.data[S.top--];        //先出栈，指针再减一
    	return true;
    }
    
    /*读取栈顶元素*/
    bool GetTop(SqStack S, ElemType& e) { 
    	if (S.top == -1) {           //栈空，报错
    		return false;
    	}
    	e = S.data[S.top];          //获取栈顶元素
    	return true;
    }
    
    /*清空栈*/
    bool ClearStack(SqStack& S) { 
    	S.top = -1;
    	return true;
    }
    
    int main() { 
    	SqStack s;
    	ElemType e;
    	InitStack(s);
    
    	for (int i = 1; i < 10; i++) 
    		Push(s, i);
    
    	while (!StackEmpty(s)) { 
    		Pop(s, e);
    		printf("%d ", e);
    	}
    	return 0;
    }

上述代码为顺序栈的实现，比较简单。其中栈顶指针设为-1，也可以设置为0，两者在判空和入栈、弹栈操作时有细微变换，具体的代码也要根据具体的赋值而定。

此外，栈还有另一种结构，即链式存储结构。链栈的优点便于多个栈共享存储空间和提高其效率，且不存在顺序栈中存在的问题（栈上溢）。链栈采用单链表实现，并且所有的操作都是在单链表的表头操作完成。  
其链式存储结构可描述为如下：

typedef struct LinkNode{ 
    	ElemType data;         //数据域
    	struct LinkNode* next; //指针域
    }*LiStack;