【数据结构】-顺序栈(初始化栈顶指针为-1）

Love The Way You Lie 2023-02-28 04:20 64阅读 0赞

### 顺序栈-初始化栈顶指针为-1 ###

*  1.头文件及类型定义
 *  2.顺序栈类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化顺序栈
     *  4.2 判空
     *  4.3 入栈
     *  4.4 出栈
     *  4.5 读取栈顶元素
     *  4.6 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #define MaxSize 10			//定义顺序栈中元素的最大个数
    #define ElemType int

# 2.顺序栈类型定义 #

typedef struct {
        		
    	ElemType data[MaxSize];		//静态数组存放栈中元素
    	int top;					//栈顶指针,一般来说存放数组的下标
    }SeqStack;

# 3.函数声明 #

/*函数声明*/
    void InitStack(SeqStack& S);				//1.初始化顺序栈
    bool StackEmpty(SeqStack S);				//2.判空
    bool Push(SeqStack& S, ElemType x);			//3.入栈
    bool Pop(SeqStack& S, ElemType& x);			//4.出栈
    bool GetTop(SeqStack S, ElemType& x);		//5.读取栈顶元素

# 4.基本操作 #

## 4.1 初始化顺序栈 ##

//1.初始化栈
    void InitStack(SeqStack& S) {
        
    	S.top = -1;		//初始化栈顶指针为-1
    }

## 4.2 判空 ##

//2.判空
    bool StackEmpty(SeqStack S) {
        
    	return (S.top == -1);
    }

## 4.3 入栈 ##

//3.入栈操作：新元素入栈(先加再存)
    bool Push(SeqStack& S, ElemType x) {
        
    	if (S.top == MaxSize - 1)		//栈满，报错
    		return false;
    	S.top++;		//栈顶指针先加1
    	S.data[S.top] = x;	//新元素再入栈：在栈顶指针所指位置放入x
    	/*
    		以上两句与此句等价：S.data[++S.top] = x;
    		请注意是++S.top,而不是S.top++
    	*/
    	return true;
    }

## 4.4 出栈 ##

//4.出栈操作：栈顶元素出栈(先取再减)-栈顶元素只是逻辑上被删除了，实际上还残留在内存中
    bool Pop(SeqStack& S, ElemType &x) {
        
    	if (S.top == -1)		//栈空，报错
    		return false;
    	x = S.data[S.top];		//栈顶元素先出栈：返回栈顶元素的值x
    	S.top--;				//指针指针再减1
    	/*
    		以上两句与此句等价：x = S.data[S.top--];
    		请注意是S.top--,而不是--S.top,注意与上面的入栈操作对比
    	*/
    	return true;
    }

## 4.5 读取栈顶元素 ##

//5.读取栈顶元素操作
    bool GetTop(SeqStack S, ElemType &x) {
        
    	if (S.top == -1)		//栈空，报错
    		return false;
    	x = S.data[S.top];		//与出栈操作唯一的区别：仅返回栈顶元素，栈顶指针并不减1
    	return true;
    }

## 4.6 main函数 ##

int main() {
        
    	SeqStack S;		//声明一个顺序栈(分配内存空间)
    
    	/*1、初始化栈*/
    	InitStack(S);	
    
    	/*2、判空*/
    	if (StackEmpty(S))
    		printf("当前栈空！\n");
    	else
    		printf("当前栈非空！\n");
    
    	/*3、入栈操作*/
    	ElemType e1;
    	printf("请输入入栈元素的值：");
    	scanf("%d", &e1);
    	if (Push(S, e1))
    		printf("新元素入栈成功！\n");
    	else
    		printf("栈已满,新元素入栈失败！\n");
    
    	/*4、读取栈顶元素*/
    	ElemType e2 = -1;
    	if (GetTop(S, e2))
    		printf("读取栈顶元素成功，当前栈顶元素值为：%d\n", e2);
    	else
    		printf("栈已空，读取栈顶元素失败！\n");
    
    	/*5、出栈操作*/
    	ElemType e3 = -1;
    	if (Pop(S, e3))
    		printf("栈顶元素出栈成功，出栈元素值为：%d\n", e3);
    	else
    		printf("栈已空，栈顶元素出栈失败！\n");
    
    	/*6、读取栈顶元素*/
    	ElemType e4 = -1;
    	if (GetTop(S, e4))
    		printf("读取栈顶元素成功，当前栈顶元素值为：%d\n", e4);
    	else
    		printf("栈已空，读取栈顶元素失败！\n");
    
    	return 0;
    }

# 5.小结 #

1.  **栈的定义及操作特性**  
    （1）栈的本质仍然为线性表，只不过是一种操作受限的线性表，只允许在一端进行插入或者删除操作。同线性表类似，它也有两种存储方式：顺序存储和链式存储，将在接下来的文章中继续讨论。  
    （2）栈的操作特性为后进先出(LIFO,Last In First Out)
2.  **栈的基本操作**  
    因为操作受限，所以栈的操作相比于线性表来说也少一点，常用如下：  
    (1)初始化  
    (2)判空  
    (3)入栈  
    (4)出栈  
    (5)获取栈顶元素
3.  **说明**  
    本文先介绍栈的顺序存储，即顺序栈。由于顺序栈是由数组实现的，所以在操作时要注意数组下标和和栈顶指针的关系，。另外，注意i++（先用再加）和++i（先加再用）的区别。