【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】

简介: 本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​相关知识初始化栈销毁栈判断栈是否为空进栈出栈取栈顶元素初始化栈概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。示例(顺序栈):以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大

目录😋

任务描述

相关知识

1. 初始化栈

2. 销毁栈

3. 判断栈是否为空

4. 进栈(Push)

5. 出栈(Pop)

6. 取栈顶元素

测试说明

通关代码

测试结果


任务描述

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

相关知识

为了完成本关任务,你需要掌握:

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

1. 初始化栈

  • 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。
  • 示例(顺序栈)
    以下是一个简单的顺序栈初始化示例,假设用 C 语言实现,栈中存储整数,最大容量为MAX_SIZE
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = - 1;
  • image.gif 这里top初始化为 - 1,表示栈为空。当top - 1时,栈中没有元素。
  • 示例(链式栈)
    定义链式栈的节点结构:
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;
StackNode *top = NULL;
  • image.gif 这里将栈顶指针top初始化为NULL,表示栈为空。当topNULL时,没有节点在栈中。

2. 销毁栈

  • 概念:销毁栈是释放栈占用的内存资源。对于顺序栈,如果栈是通过数组实现的,且数组是在栈的生命周期内自动分配的(如在函数内部定义的局部数组),一般不需要手动释放内存;但如果是动态分配的数组,需要使用free等函数释放。对于链式栈,需要逐个释放栈中的节点,避免内存泄漏。
  • 示例(顺序栈 - 动态分配情况)
    假设栈是通过动态分配的数组实现的,以下是销毁栈的示例:
void destroyStack() {
    // 释放动态分配的数组内存
    free(stack);
}
  • image.gif
  • 示例(链式栈)
    以下是链式栈销毁的过程,需要遍历栈中的节点并释放它们:
void destroyStack() {
    StackNode *current = top;
    StackNode *next;
    while (current!= NULL) {
        next = current - > next;
        free(current);
        current = next;
    }
    top = NULL;
}
  • image.gif

3. 判断栈是否为空

  • 概念:判断栈中是否有元素。对于顺序栈,通过检查栈顶指针(如top)是否为初始值来判断;对于链式栈,检查栈顶指针是否为NULL
  • 示例(顺序栈)
    可以通过以下方式判断顺序栈是否为空:
int isEmpty() {
    return top == - 1;
}
  • image.gif
  • 示例(链式栈)
    对于链式栈,判断是否为空的函数如下:
int isEmpty() {
    return top == NULL;
}
  • image.gif

4. 进栈(Push)

  • 概念:将元素添加到栈顶。对于顺序栈,需要先检查栈是否已满,然后将元素存入栈顶位置,并更新栈顶指针;对于链式栈,创建新节点,将元素存入新节点,然后将新节点插入到栈顶位置,更新栈顶指针。
  • 示例(顺序栈)
    以下是顺序栈进栈的操作示例:
int push(int value) {
    if (top == MAX_SIZE - 1) {
        // 栈已满
        return 0;
    }
    top++;
    stack[top] = value;
    return 1;
}
  • image.gif
  • 示例(链式栈)
    链式栈进栈操作如下:
int push(int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        // 内存分配失败
        return 0;
    }
    newNode - > data = value;
    newNode - > next = top;
    top = newNode;
    return 1;
}
  • image.gif

5. 出栈(Pop)

  • 概念:从栈顶移除元素。对于顺序栈,需要先检查栈是否为空,然后取出栈顶元素,更新栈顶指针;对于链式栈,取出栈顶节点的数据,释放栈顶节点,更新栈顶指针。
  • 示例(顺序栈)
    顺序栈出栈操作如下:
int pop() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    int value = stack[top];
    top--;
    return value;
}
  • image.gif
  • 示例(链式栈)
    链式栈出栈操作如下:
int pop() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    StackNode *temp = top;
    int value = top - > data;
    top = top - > next;
    free(temp);
    return value;
}
  • image.gif

6. 取栈顶元素

  • 概念:获取栈顶的元素,但不将其从栈中移除。对于顺序栈和链式栈,都需要先检查栈是否为空,然后返回栈顶元素的值。
  • 示例(顺序栈)
    顺序栈取栈顶元素操作如下:
int peek() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    return stack[top];
}
  • image.gif
  • 示例(链式栈)
    链式栈取栈顶元素操作如下:
int peek() {
    if (isEmpty()) {
        // 栈为空
        return - 1;
    }
    return top - > data;
}
  • image.gif

测试说明

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

测试输入:

abcde
image.gif

预期输出:

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

测试输入:

xyz
image.gif

预期输出:

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

开始你的任务吧,祝你成功!


通关代码

// 请在Begin-End之间添加你的代码,
//实现链栈的如下基本运算,假设链栈的元素类型为char//
//(1)初始化栈s//
//(2)判断栈s是否非空,输出判断结果//
//(3)依次进栈元素,注:进栈元素由用户输入//
//(4)判断栈s是否非空,输出判断结果//
//(5)输出出栈序列//
//(6)判断栈s是否非空,输出判断结果//
//(7)释放栈//
/********** Begin *********/
#include <iostream>
using namespace std;
struct Node{
    char data;
    Node *next;
    Node(char x): data(x),next(NULL){}
};
class Stack{
    private:
    Node *top;
    public:
    Stack() : top(NULL){}
    ~Stack(){
        while(top != NULL){
            Node *temp = top;
            top = top -> next;
            delete temp;
        }
    }
    bool isEmpty(){return top == NULL;}
    void push(char x){
        Node *newNode = new Node(x);
        newNode->next = top;
        top = newNode;
    }
    char pop(){
        if(isEmpty()){
            throw "Stack is empty";
        }
        char x = top->data;
        Node *temp = top;
        top  =top->next;
        delete temp;
        return x;
    }
    char peek(){
        if(isEmpty()){
            throw "Stack is empty";
        }
        return top->data;
    }
};
int main(){
    string input;
    cin>>input;
    Stack s;
    cout <<"(1)初始化栈s"<<endl;
    if(s.isEmpty()){
        cout<<"(2)栈为空"<<endl;
    }
    cout <<"(3)依次进栈元素:";
    for(char c : input){
        s.push(c);
        cout <<c<<" ";
    }
    cout <<endl;
    if(!s.isEmpty()){
        cout <<"(4)栈为非空"<<endl;
    }
    cout <<"(5)出栈序列:";
    while (!s.isEmpty()){
        cout <<s.pop()<<" ";
    }
    cout <<endl;
    if(s.isEmpty()){
        cout<<"(6)栈为空"<<endl;
    }
    cout << "(7)释放栈"<<endl;
    return 0;
}
/********** End **********/

image.gif


测试结果

image.gif

image.gif

目录
相关文章
|
30天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
139 77
|
30天前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
67 19
|
30天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
42 10
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
318 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
50 1
|
30天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
42 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
30天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
36 7
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
94 5
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
115 21
|
3月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。