数据结构与算法中顺序栈中入栈和出栈怎么写？

顺序栈是一种基于数组实现的栈结构，入栈和出栈操作可以通过数组的操作来实现。

入栈操作：

1. 判断栈是否已满，如果已满则抛出栈满异常或者扩容栈；
2. 将元素插入到栈顶，即数组的末尾；
3. 栈顶指针加一。

代码实现：

void push(int data) {
    if (top == MAX_SIZE - 1) {
        // 抛出栈满异常或者扩容栈
        return;
    }
    stack[++top] = data;
}

出栈操作：

1. 判断栈是否为空，如果为空则抛出栈空异常；
2. 取出栈顶元素，即数组的最后一个元素；
3. 栈顶指针减一。

代码实现：

int pop() {
    if (top == -1) {
        // 抛出栈空异常
        return -1;
    }
    int data = stack[top--];
    return data;
}

相关问题

你是一个学习数据结构的大二学生现在需要你结合课上知识完成结课实验报告，以下是实验要求：使用C++编写，（1）建立顺序栈，实现入栈、出栈、获取栈顶元素操作； （2）利用顺序栈实现表达式的求解。

好的，以下是结课实验报告内容，希望对你有所帮助。

一、实验目的

1. 掌握顺序栈的基本操作，包括入栈、出栈、获取栈顶元素等；
2. 利用顺序栈实现表达式的求解。

二、实验原理

1. 顺序栈的定义

顺序栈是一种基于数组的栈，它的元素在内存中是连续存储的。栈有两个指针：栈顶指针和栈底指针。栈顶指针指向栈顶元素，栈底指针指向栈底元素。当栈为空时，栈顶指针和栈底指针重合。

2. 顺序栈的操作

（1）初始化：创建一个空的顺序栈，即将栈顶指针和栈底指针重合。

（2）入栈：将元素压入栈顶，即将栈顶指针加一，并将元素存入栈顶位置。

（3）出栈：将栈顶元素弹出，即先取出栈顶元素，再将栈顶指针减一。

（4）获取栈顶元素：返回栈顶元素的值，但不改变栈的状态。

（5）判断是否为空栈：当栈顶指针和栈底指针重合时，栈为空。

3. 表达式求解

利用顺序栈可以实现对表达式的求解。具体步骤如下：

（1）将表达式中的数字和符号分别压入栈中。

（2）当遇到运算符时，弹出栈顶的两个数字，进行运算，并将运算结果压入栈中。

（3）重复步骤（2），直到遍历完整个表达式，最终栈中只剩下一个元素，即为表达式的计算结果。

三、实验过程

1. 建立顺序栈

定义一个结构体来表示顺序栈，包括栈的容量、栈顶指针和存储元素的数组。

const int MAXSIZE = 100;
struct stack {
    int capacity; // 栈的容量
    int top; // 栈顶指针
    double data[MAXSIZE]; // 存储元素的数组
};

实现顺序栈的初始化、入栈、出栈、获取栈顶元素和判断是否为空栈的操作。

// 初始化栈
void init_stack(stack& s) {
    s.capacity = MAXSIZE;
    s.top = -1;
}

// 判断是否为空栈
bool is_empty(stack& s) {
    return s.top == -1;
}

// 入栈
bool push(stack& s, double val) {
    if (s.top == s.capacity - 1) {
        return false; // 栈满，入栈失败
    }
    s.data[++s.top] = val;
    return true;
}

// 出栈
bool pop(stack& s, double& val) {
    if (is_empty(s)) {
        return false; // 栈空，出栈失败
    }
    val = s.data[s.top--];
    return true;
}

// 获取栈顶元素
bool get_top(stack& s, double& val) {
    if (is_empty(s)) {
        return false; // 栈空，获取栈顶元素失败
    }
    val = s.data[s.top];
    return true;
}

2. 表达式求解

利用顺序栈实现表达式的求解。首先定义一个字符串来存储中缀表达式，然后将其转换为后缀表达式，并计算后缀表达式的值。

（1）将中缀表达式转换为后缀表达式

定义一个辅助函数 `priority` 来判断运算符的优先级。对于每个运算符，设置一个优先级，数字越大，优先级越高。

// 判断运算符优先级
int priority(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

利用顺序栈实现将中缀表达式转换为后缀表达式的算法如下：

// 将中缀表达式转换为后缀表达式
void infix_to_postfix(string infix, string& postfix) {
    postfix = ""; // 初始化后缀表达式
    stack s;
    init_stack(s);
    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];
        if (isdigit(c)) { // 遇到数字，直接输出
            postfix += c;
        }
        else if (c == '(') { // 遇到左括号，入栈
            push(s, c);
        }
        else if (c == ')') { // 遇到右括号，弹出栈中左括号前的所有运算符
            char op;
            while (get_top(s, op) && op != '(') {
                postfix += op;
                pop(s, op);
            }
            pop(s, op); // 弹出左括号
        }
        else { // 遇到运算符，弹出栈中优先级较高的运算符
            char op;
            while (get_top(s, op) && op != '(' && priority(op) >= priority(c)) {
                postfix += op;
                pop(s, op);
            }
            push(s, c); // 当前运算符入栈
        }
    }
    // 将栈中剩余的运算符弹出
    char op;
    while (pop(s, op)) {
        postfix += op;
    }
}

（2）计算后缀表达式的值

定义一个函数 `calculate` 来计算后缀表达式的值。利用顺序栈存储数字，当遇到运算符时，弹出栈顶的两个数字，进行运算，并将运算结果压入栈中。

// 计算后缀表达式的值
double calculate(string postfix) {
    stack s;
    init_stack(s);
    for (int i = 0; i < postfix.length(); i++) {
        char c = postfix[i];
        if (isdigit(c)) { // 遇到数字，入栈
            push(s, c - '0'); // 将字符转换为数字
        }
        else { // 遇到运算符，弹出栈顶的两个数字，进行运算
            double num1, num2;
            pop(s, num2);
            pop(s, num1);
            switch (c) {
            case '+':
                push(s, num1 + num2);
                break;
            case '-':
                push(s, num1 - num2);
                break;
            case '*':
                push(s, num1 * num2);
                break;
            case '/':
                push(s, num1 / num2);
                break;
            }
        }
    }
    double result;
    get_top(s, result); // 栈中最后剩下的元素即为表达式的计算结果
    return result;
}

三、实验结果

输入中缀表达式 `2+3*(4-1)-5/2`，经过转换为后缀表达式 `2341-*+52/-`，计算后得到结果为 `9.5`。

四、实验总结

通过本次实验，我掌握了顺序栈的基本操作，并且利用顺序栈实现了表达式求解的功能。在实现过程中，我发现顺序栈的操作比较简单，但是需要注意边界条件，特别是在栈满和栈空的情况下需要进行判断。此外，将中缀表达式转换为后缀表达式的算法也需要仔细理解，才能正确实现。

数据结构与算法：将栈顶元素出栈，并在屏幕上显示当前顺序栈的数据元素

假设顺序栈已经实现，那么可以先通过栈顶指针获取栈顶元素，再将栈顶指针向下移动一位，即出栈操作。

代码如下：

#include <stdio.h>
#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];  // 存储数据元素
    int top;            // 栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack *S) {
    S->top = -1;
}

// 判断栈是否为空
int StackEmpty(SqStack S) {
    return S.top == -1;
}

// 入栈操作
int Push(SqStack *S, int x) {
    if (S->top == MAXSIZE - 1) {
        return 0;  // 栈满，入栈失败
    } else {
        S->data[++S->top] = x;  // 栈顶指针先加1，再入栈
        return 1;  // 入栈成功
    }
}

// 出栈操作
int Pop(SqStack *S, int *x) {
    if (S->top == -1) {
        return 0;  // 栈空，出栈失败
    } else {
        *x = S->data[S->top--];  // 先出栈，再将栈顶指针减1
        return 1;  // 出栈成功
    }
}

// 打印顺序栈中的数据元素
void PrintStack(SqStack S) {
    int i;
    printf("Stack: ");
    for (i = S.top; i >= 0; i--) {
        printf("%d ", S.data[i]);
    }
    printf("\n");
}

int main() {
    SqStack S;
    InitStack(&S);
    Push(&S, 1);
    Push(&S, 2);
    Push(&S, 3);
    PrintStack(S);  // 输出: Stack: 3 2 1
    int x;
    Pop(&S, &x);
    PrintStack(S);  // 输出: Stack: 2 1
    return 0;
}

运行结果：

Stack: 3 2 1
Stack: 2 1