【数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】

【数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】

任务描述

本关任务：编写一个程序实现顺序栈的基本运算。

相关知识

为了完成本关任务，你需要掌握：

1. 初始化栈
2. 销毁栈
3. 判断栈是否为空
4. 进栈
5. 出栈
6. 取栈顶元素

1. 初始化栈

概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。

示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用 C 语言实现，栈中存储整数，最大容量为MAX_SIZE。

代码语言：javascript代码运行次数：0运行复制

#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = - 1; 

这里top初始化为 - 1，表示栈为空。当top为 - 1时，栈中没有元素。

示例（链式栈）： 定义链式栈的节点结构：

代码语言：javascript代码运行次数：0运行复制

typedef struct Stackode {
    int data;
    struct Stackode *next;
} Stackode;
Stackode *top = ULL; 

这里将栈顶指针top初始化为ULL，表示栈为空。当top为ULL时，没有节点在栈中。

2. 销毁栈

概念：销毁栈是释放栈占用的内存资源。对于顺序栈，如果栈是通过数组实现的，且数组是在栈的生命周期内自动分配的（如在函数内部定义的局部数组），一般不需要手动释放内存；但如果是动态分配的数组，需要使用free等函数释放。对于链式栈，需要逐个释放栈中的节点，避免内存泄漏。

示例（顺序栈 - 动态分配情况）： 假设栈是通过动态分配的数组实现的，以下是销毁栈的示例：

代码语言：javascript代码运行次数：0运行复制

void destroyStack() {
    // 释放动态分配的数组内存
    free(stack);
}

示例（链式栈）： 以下是链式栈销毁的过程，需要遍历栈中的节点并释放它们：

代码语言：javascript代码运行次数：0运行复制

void destroyStack() {
    Stackode *current = top;
    Stackode *next;
    while (current!= ULL) {
        next = current - > next;
        free(current);
        current = next;
    }
    top = ULL;
}

. 判断栈是否为空

概念：判断栈中是否有元素。对于顺序栈，通过检查栈顶指针（如top）是否为初始值来判断；对于链式栈，检查栈顶指针是否为ULL。

示例（顺序栈）： 可以通过以下方式判断顺序栈是否为空：

代码语言：javascript代码运行次数：0运行复制

int isEmpty() {
    return top == - 1;
}

示例（链式栈）： 对于链式栈，判断是否为空的函数如下：

代码语言：javascript代码运行次数：0运行复制

int isEmpty() {
    return top == ULL;
}

4. 进栈（Push）

概念：将元素添加到栈顶。对于顺序栈，需要先检查栈是否已满，然后将元素存入栈顶位置，并更新栈顶指针；对于链式栈，创建新节点，将元素存入新节点，然后将新节点插入到栈顶位置，更新栈顶指针。

示例（顺序栈）： 以下是顺序栈进栈的操作示例：

代码语言：javascript代码运行次数：0运行复制

int push(int value) {
    if (top == MAX_SIZE - 1) {
        // 栈已满
        return 0;
    }
    top++;
    stack[top] = value;
    return 1;
}

示例（链式栈）： 链式栈进栈操作如下：

代码语言：javascript代码运行次数：0运行复制

int push(int value) {
    Stackode *newode = (Stackode *)malloc(sizeof(Stackode));
    if (newode == ULL) {
        // 内存分配失败
        return 0;
    }
    newode - > data = value;
    newode - > next = top;
    top = newode;
    return 1;
}

5. 出栈（Pop）

概念：从栈顶移除元素。对于顺序栈，需要先检查栈是否为空，然后取出栈顶元素，更新栈顶指针；对于链式栈，取出栈顶节点的数据，释放栈顶节点，更新栈顶指针。

示例（顺序栈）： 顺序栈出栈操作如下：

代码语言：javascript代码运行次数：0运行复制

int pop() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    int value = stack[top];
    top--;
    return value;
}

示例（链式栈）： 链式栈出栈操作如下：

代码语言：javascript代码运行次数：0运行复制

int pop() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    Stackode *temp = top;
    int value = top - > data;
    top = top - > next;
    free(temp);
    return value;
}

6. 取栈顶元素

概念：获取栈顶的元素，但不将其从栈中移除。对于顺序栈和链式栈，都需要先检查栈是否为空，然后返回栈顶元素的值。

示例（顺序栈）： 顺序栈取栈顶元素操作如下：

代码语言：javascript代码运行次数：0运行复制

int peek() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    return stack[top];
}

示例（链式栈）： 链式栈取栈顶元素操作如下：

代码语言：javascript代码运行次数：0运行复制

int peek() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    return top - > data;
}

---

测试说明

平台会对你编写的代码进行测试：

测试输入：

代码语言：javascript代码运行次数：0运行复制

abcde

预期输出：

代码语言：javascript代码运行次数：0运行复制

(1)初始化栈s
(2)栈为空
()依次进栈元素:a b c d e
(4)栈为非空
(5)出栈序列:e d c b a
(6)栈为空
(7)释放栈

测试输入：

代码语言：javascript代码运行次数：0运行复制

xyz

预期输出：

代码语言：javascript代码运行次数：0运行复制

(1)初始化栈s
(2)栈为空
()依次进栈元素:x y z
(4)栈为非空
(5)出栈序列:z y x
(6)栈为空
(7)释放栈

开始你的任务吧，祝你成功！

---

通关代码

代码语言：javascript代码运行次数：0运行复制

// 请在Begin-End之间添加你的代码，
//实现顺序栈的如下基本运算，假设顺序栈的元素类型为char//
//(1)初始化栈s//
//(2)判断栈s是否非空，输出判断结果//
//()依次进栈元素，注：进栈元素由用户输入//
//(4)判断栈s是否非空，输出判断结果//
//(5)输出出栈序列//
//(6)判断栈s是否非空，输出判断结果//
//(7)释放栈//
/********** Begin *********/
#include <cstring>
#include<iostream>

using namespace std;
ct int MAX_SIZE = 100;

class Stack{
    private:
    char arr[MAX_SIZE];
    int top;

public:
Stack(){
    top = -1;
}

bool isEmpty(){
    return top == -1;
}

void push(char value){
    if (top < MAX_SIZE - 1){
        arr[++top] = value;
    }
}
 char pop(){
     if (!isEmpty()){
         return arr[top--];
     }
     return '\0';
 }

 void printStack(){
     cout <<"()依次进栈元素:";
     for(int i = 0;i <=top;i++){
         cout<< arr[i] <<" ";
         }
         cout <<endl;
     }
void release(){
         top = -1;
         cout <<"(7)释放栈"<<endl;
     }
 };

 int main(){
     Stack s;
     string input;
     getline(cin,input);
     cout << "(1)初始化栈s"<<endl;
     for(char c : input){
         s.push(c);
     }
     cout << "(2)栈为空"<<endl;
     s.printStack();

     if(!s.isEmpty()){
         cout << "(4)栈为非空"<<endl;
     }
     cout <<"(5)出栈序列:";
     while (!s.isEmpty()){
         cout <<s.pop()<<" ";
     }
     cout << endl;

     cout << "(6)栈为空" <<endl;

     s.release();

     return 0;
 }
/********** End **********/

---

测试结果

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-24，如有侵权请联系 cloudcommunity@tencent 删除前往查看数组指针数据结构队列实践