栈的基本运算算法——C/C++

墨蓝 2024-04-17 05:31 83阅读 0赞

## 1、简介 ##

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

## 2、图示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 3、各个函数接口 ##

//初始化
    void InitStack(SqStack*& s) 
    //销毁栈 
    void DestroyStack(SqStack*& s) 
    //判断是否空
    bool StackEmpty(SqStack* s) 
    //进栈
    bool Push(SqStack*& s, int x) 
    //出栈 
    bool Pop(SqStack*& s, int& x) 
    //取栈顶元素
    bool GetTop(SqStack* s, int& x)

## 4、函数实现及解释 ##

用到的库基本库< iostream >、需要分配地址空间的库<malloc.h>

#include<iostream>
    #include<malloc.h> 
    
    #define maxsize 100							//最大空间 
    using namespace std;
    
    typedef struct Stack {
    	int data[maxsize];
    	int top;
    }SqStack;									//栈的类型

**4.1、初始化**  
创建一个空栈，由 s 指向它。实际上就是分配一个顺序栈空间，并将栈顶指针值为 -1。

//初始化
    void InitStack(SqStack*& s) {
    	s = (SqStack*)malloc(sizeof(SqStack));	//分配一个顺序栈空间，首地址存放在 s 中 
    	s->top = -1;							//栈顶指针置为 -1
    }

**4.2、销毁栈**  
释放顺序栈 s 占用的存储空间。

//销毁栈 
    void DestroyStack(SqStack*& s) {
    	free(s);
    }

**4.3、判断栈是否为空**  
判断条件 s->top == -1 是否成立。

//判断是否空
    bool StackEmpty(SqStack* s) {
    	return (s->top == -1) ? true : false;
    }

**4.4、进栈**  
在栈不满的条件下先将栈顶指针加 1，然后在该位置插入元素。

//进栈
    bool Push(SqStack*& s, int x) {
    	if (s->top == maxsize - 1) {			//栈满情况
    		return false;
    	}
    	else {
    		s->top++;							//栈顶指针加一
    		s->data[s->top] = x;				//元素 x 放在栈顶指针处
    		return true;
    	}
    }

**4.5、出栈**  
在栈不为空的条件下先将栈顶元素赋给 x，然后将栈顶指针减 1。

//出栈 
    bool Pop(SqStack*& s, int& x) {
    	if (s->top == -1) {						//栈空情况
    		return false;
    	}
    	else {
    		x = s->data[s->top];				//取栈顶元素
    		s->top--;							//栈顶指针减一
    		return true;
    	}
    }

**4.6、取栈顶元素**  
在栈不为空的条件下先将栈顶元素赋给 x。

//取栈顶元素
    bool GetTop(SqStack* s, int& x) {
    	if (s->top == -1) {						//栈空情况
    		return false;
    	}
    	else {
    		x = s->data[s->top];				//取栈顶元素
    		return true;
    	}
    }

## 5、结果展示 ##

**主函数**

int main() {
    	int i, n;
    	int x, y;
    	int a[maxsize];
    	SqStack* s;
    	InitStack(s);
    	cout << "输入个数: ";
    	cin >> n;
    	cout << "输入值: ";
    	for (i = 0; i < n; i++) {
    		cin >> a[i];
    		Push(s, a[i]);
    	}
    	cout << "栈顶元素: ";
    	GetTop(s, x);
    	cout << x << endl;
    	cout << "栈的输出: ";
    	while (!StackEmpty(s)) {
    		Pop(s, y);
    		cout << y << " ";
    	}
    	cout << endl;
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f1bc44b215be42708df3c2c353cd754b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f45bcea045e749c4bd5b150ffbe4cae2.png