欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  科技

数据结构实验三——栈和队列的基本操作

程序员文章站 2022-05-24 15:45:19
**一、实验内容**1. 实验目的编程实现顺序栈和链栈的基本操作：建栈，取栈顶元素，入栈，出栈；编程实现循环队列和链队列的基本操作：建队列，取队头元素，入队，出队。2. 基本要求掌握栈的顺序存储结构、链式存储结构及其基本操作；掌握队列的顺序存储结构、链式存储结构及其基本操作。4. 支撑的课程目标本实验项目可以支撑“目标1. 理解数据结构的基本概念、计算机内部数据对象的表示和特性。掌握线性表、树、图等数据逻辑结构、存储结构及其差异以及各种操作的实现。”、和“目标2能够针对实际问题选...

栈和队列

一、实验内容

1.实验目的

  1. 编程实现顺序栈和链栈的基本操作：建栈，取栈顶元素，入栈，出栈；
  2. 编程实现循环队列和链队列的基本操作：建队列，取队头元素，入队，出队。

2. 基本要求

  1. 掌握栈的顺序存储结构、链式存储结构及其基本操作；
  2. 掌握队列的顺序存储结构、链式存储结构及其基本操作。

3. 支撑的课程目标

本实验项目可以支撑“目标1. 理解数据结构的基本概念、计算机内部数据对象的表示和特性。掌握线性表、树、图等数据逻辑结构、存储结构及其差异以及各种操作的实现。”、和“目标2能够针对实际问题选择合适的数据结构和方法设计出结构清晰、正确易读、复杂性较优的算法，同时掌握对算法进行时间、空间复杂度分析的基本技能。”。
本实验通过验证方式引导学生掌握顺序栈和链栈的基本操作，循环队列和链队列的基本 操作，为后续学习打下基础，以便更好地达成后续更高层次的课程目标。

二、实验过程

1. 顺序栈的建栈、入栈、出栈、取栈顶元素

/*
*title:顺序栈的基本操作
*writer:weiyuexin
*data:2020-10-11
*/

#include<iostream>

using namespace std;

#define SElemType int

typedef struct{
    SElemType *base;    //定义栈底指针
    SElemType *top;     //定义栈顶指针
    int stacksize;
}SqStack;

void InitStack(SqStack &S,int maxsize){    //初始化栈
    S.base = new SElemType[maxsize];
    if(!S.base){
        cout<<"创建栈失败!"<<endl;
    }
    S.top = S.base;     //top初始化为base,是空栈
    S.stacksize = maxsize;
    cout<<"成功创建了一个最大容量为"<<S.stacksize<<"的顺序栈!"<<endl;
}

void Display(SqStack S){     //打印顺序栈
    cout<<"该顺序栈为:"<<endl;
    cout<<"栈底=>";
    for(int i=0;i<S.stacksize;i++){
        cout<<*S.base++<<" ";
        if(!*S.base || S.top == S.base){
            break;
        }
    }
    cout<<"<=栈顶"<<endl;
}

void Push(SqStack &S,SElemType e){    //入栈
    if(S.top - S.base == S.stacksize){
        cout<<"栈已满，无法插入!"<<endl;
        return;
    }
    *S.top++=e;
}

SElemType Pop(SqStack &S){    //出栈
    if(S.top == S.base){
        cout<<"栈空!"<<endl;
    }
    SElemType e;
    e = *--S.top;
    cout<<e<<" ";
}

SElemType GetTop(SqStack S){
    if(S.top != S.base){
        return *(S.top-1);
    }
}

int main(){
    SqStack S;
    int maxsize;
    cout<<"实验3_1-------------------顺序栈的基本操作"<<endl<<endl;
    cout<<"请输入对应数字选择操作："<<endl;
    cout<<"1------------------建栈"<<endl;
    cout<<"2------------------入栈"<<endl;
    cout<<"3------------------出栈"<<endl;
    cout<<"4------------------打印顺序栈"<<endl;
    cout<<"5------------------取栈顶元素"<<endl;
    cout<<"0------------------结束程序运行"<<endl;
    int operation;
    while(cin>>operation){

        switch(operation){
        case 0 :
            cout<<"程序运行结束!"<<endl;
            return 0;
            break;
        case 1 :
            cout<<"请输入栈的最大容量:"<<endl;
            cin>>maxsize;
            InitStack(S,maxsize);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 2 :
            cout<<"请输入数据元素,当输入-1时结束:"<<endl;
            int e;
            while(cin>>e){
                if(e == -1){
                    break;
                }
                Push(S,e);
            }
            cout<<"入栈成功!"<<endl;
            Display(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 3 :
            cout<<"请输入出栈元素的个数:"<<endl;
            int m;
            cin>>m;
            cout<<"出栈的元素为:"<<endl;
            for(int i= 0;i<m;i++){
                Pop(S);
            }
            cout<<"(先出->后出)"<<endl;
            Display(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 4 :
            Display(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 5 :
            cout<<"栈顶元素为: "<<GetTop(S)<<endl;
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        default :
            cout<<"您选择的操作不存在，请重新选择:"<<endl;
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        }
    }
    return 0;
}

1. 链栈的建栈、入栈、出栈、及取栈顶元素

/*
*title:链栈的基本操作
*writer:weiyuexin
*data:2020-10-11
*/

#include<iostream>

using namespace std;

#define ElemType int

typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

void InitStack(LinkStack &S){     //初始化链栈
    S = NULL;
    cout<<"栈S初始化成功!"<<endl;
}

void Display(LinkStack S){
    LinkStack p = S;
    cout<<"该链栈为:"<<endl;
    cout<<"栈顶=> ";
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<" <=栈底"<<endl;
}

ElemType Pop(LinkStack &S,ElemType ee){
    if(S == NULL){
        cout<<"栈已空，无法在进行删除操作!"<<endl;
        return 0;
    }
    StackNode *p = new StackNode();
    ee = S->data;
    p = S;
    S = S->next;
    delete p;
    return ee;
}

void Push(LinkStack &S,ElemType e){     //入栈
    StackNode *p = new StackNode();
    p ->data = e;
    p ->next = S;
    S = p;
}

int main(){
    LinkStack S;

    cout<<"实验3_2-------------------链栈的基本操作"<<endl<<endl;
    cout<<"请输入对应数字选择操作："<<endl;
    cout<<"1------------------初始化链栈"<<endl;
    cout<<"2------------------入栈"<<endl;
    cout<<"3------------------出栈"<<endl;
    cout<<"4------------------打印链栈"<<endl;
    cout<<"5------------------取栈顶元素"<<endl;
    cout<<"0------------------结束程序运行"<<endl;
    int operation;
    while(cin>>operation){

        switch(operation){
        case 0 :
            cout<<"程序运行结束!"<<endl;
            return 0;
            break;
        case 1 :
            InitStack(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 2 :
            cout<<"请输入数据元素,当输入-1时结束:"<<endl;
            ElemType e;
            while(cin>>e){
                if(e == -1){
                    break;
                }
                Push(S,e);
            }
            cout<<"入栈成功!"<<endl;
            Display(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 3 :
            cout<<"请输入出栈元素的个数:"<<endl;
            int n;
            cin>>n;
            cout<<"出栈的元素依次为: ";
            for(int i=0;i<n;i++){
                ElemType ee;
                cout<<Pop(S,ee)<<" ";
            }
            cout<<endl;
            Display(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 4 :
            Display(S);
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        case 5 :
            cout<<"栈顶元素为:"<<S->data<<endl;
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        default :
            cout<<"您选择的操作不存在，请重新选择:"<<endl;
            cout<<"请输入对应数字选择操作："<<endl;
            break;
        }
    }
    return 0;
}

3.循环队列的建立、入队、出队及取队头元素

/*
*title: 循环队列的基本操作
*writer:weiyuexin
*data:2020-10-11
*/

#include<iostream>

using namespace std;

#define MAXSIZE 100
#define QElemType int

typedef struct{
    QElemType *base;     //存储空间基地址
    int front;    //头指针
    int rear;     //尾指针
}SqQueue;

void InitQueue(SqQueue &Q){        //初始化循环队列
    Q.base = new QElemType[MAXSIZE];
    if(!Q.base){
        cout<<"队列初始化失败!"<<endl;
        return;
    }
    Q.front = Q.rear = 0;
    cout<<"循环队列初始化成功!"<<endl;
}

void EnQueue(SqQueue &Q,QElemType e){    //入队
    if((Q.rear + 1)%MAXSIZE == Q.front){
        cout<<"该队列已满无法插入!"<<endl;
        return;
    }
    Q.base[Q.rear] = e;    //新元素插入对尾
    Q.rear = (Q.rear + 1)%MAXSIZE;      //队尾指针加一
}

QElemType DeQueue(SqQueue &Q,QElemType &ee){
    if(Q.front == Q.rear){
        cout<<"该循环队列已空!"<<endl;
        return 0;
    }
    ee = Q.base[Q.front];   //保存队首指针
    Q.front = (Q.front + 1)%MAXSIZE;    //队首指针加一
    return ee;
}

void Display(SqQueue Q){     //打印循环队列
    cout<<"该循环队列为: "<<endl;
    cout<<"队首=>";
    for(int i=Q.front;i<MAXSIZE;i++){
        if(!Q.base[i]){
            break;
        }
        cout<<Q.base[i]<<" ";
    }
    cout<<"<=队尾"<<endl;
}

QElemType GetHead(SqQueue Q){   //去队首元素
    if(Q.front != Q.rear){   //队列非空
        return Q.base[Q.front];
    }else{
        cout<<"队列中没有元素!"<<endl;
        return 0;
    }
}

int QueueLength(SqQueue Q){   //求队列的长度
    return (Q.rear - Q.front +MAXSIZE)%MAXSIZE;
}


int main(){
    SqQueue Q;
    cout<<"实验3_3---------------------循环队列的基本操作"<<endl<<endl;
    cout<<"请输入对应数字选择您想要的操作:"<<endl;
    cout<<"1----------------建立循环队列"<<endl;
    cout<<"2----------------入队"<<endl;
    cout<<"3----------------出队"<<endl;
    cout<<"4----------------取队头元素"<<endl;
    cout<<"5----------------打印循环队列"<<endl;
    cout<<"6----------------求队列长度"<<endl;
    cout<<"0----------------结束程序"<<endl;

    int operation;
    while(cin>>operation){
        switch(operation){
        case 0 :
            cout<<"程序运行结束!"<<endl;
            return 0;
            break;
        case 1 :
            InitQueue(Q);   //初始化队列
            cout<<"请输入对应数字选择您想要的操作:"<<endl;
            break;
        case 2 :
            int e;
            cout<<"请输入想要入队的元素，以-1为截止符:"<<endl;
            while(cin>>e){
                if(e == -1){
                    break;
                }
                EnQueue(Q,e);
            }
            cout<<"入队成功!"<<endl;
            Display(Q);
            cout<<"请输入对应数字选择您想要的操作:"<<endl;
            break;
        case 3 :
            cout<<"请输入想要出队的元素个数:"<<endl;
            int n;
            cin>>n;
            cout<<"出队的元素依次为: ";
            for(int i=0;i<n;i++){
                QElemType ee;
                cout<<DeQueue(Q,ee)<<" ";
            }
            cout<<endl;
            Display(Q);
            cout<<"请输入对应数字选择您想要的操作:"<<endl;
            break;
        case 4 :
            cout<<"队首元素为:"<<GetHead(Q)<<endl;
            cout<<"请输入对应数字选择您想要的操作:"<<endl;
            break;
        case 5 :
            Display(Q);
            cout<<"请输入对应数字选择您想要的操作:"<<endl;
            break;
        case 6 :
            cout<<"该循环链表的长度为:"<<QueueLength(Q)<<endl;    //求队列长度
            cout<<"请输入对应数字选择您想要的操作:"<<endl;
            break;
        default :
            cout<<"您选择的操作不存在，请重新选择:"<<endl;
            break;
        }
    }
    return 0;
}

**

4.链队的创建、入队、出队及取队头元素

**

/*
*title:链队的基本操作
*writer:weiyuexin
*data:2020-10-11
*/

#include<iostream>

using namespace std;

#define QElemType int

typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
    QueuePtr front;     //队头指针
    QueuePtr rear;     //队尾指针
}LinkQueue;

void InitQueue(LinkQueue &Q){     //初始化链队
    Q.front = Q.rear = new QNode;        //生成新结点作为头结点，队头和队尾指针指向此节点
    Q.front->next = NULL;     //头结点的指针域置空
    cout<<"链队初始化成功!"<<endl;
}

void EnQueue(LinkQueue &Q,QElemType e){     //入队
    QNode *p = new QNode();
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}

QElemType DeQueue(LinkQueue &Q){      //出队
    if(Q.front == Q.rear){
        cout<<"该链队已空!"<<endl;
         return 0;
    }
    QElemType e;
    QNode *p = new QNode();
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p){
        Q.rear = Q.front;
    }
    delete p;
    return e;
}

QElemType GetHead(LinkQueue Q){        //取队首值
    if(Q.front != Q.rear){     //队列非空
        return Q.front->next->data;     //返回队首值
    }else{
       cout<<"该链队为空！"<<endl;
       return 0;
    }
}

void Display(LinkQueue Q){      //打印链队元素
    QNode *p = new QNode();
    p = Q.front->next;
    cout<<"该链队为: 队首=> ";
    while(p != NULL){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<"<=队尾"<<endl;
}

int main(){
    LinkQueue Q;
    cout<<"实验3_4---------------------链队列的基本操作"<<endl<<endl;
    cout<<"请输入对应数字选择您想要的操作:"<<endl;
    cout<<"1----------------建立链队列"<<endl;
    cout<<"2----------------入队"<<endl;
    cout<<"3----------------出队"<<endl;
    cout<<"4----------------取队头元素"<<endl;
    cout<<"5----------------打印链队列"<<endl;
    cout<<"0----------------结束程序"<<endl;
    int operation;
    cout<<"请输入对应的数字选择你想要进行的操作:"<<endl;
    while(cin>>operation){
        switch(operation){
        case 0 :
            cout<<"程序运行结束!"<<endl;
            return 0;
        case 1 :
            InitQueue(Q);
            cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
            break;
        case 2 :
            cout<<"请输入要入队的元素个数；"<<endl;
            int n;
            cin>>n;
            cout<<"请输入要入队的元素:"<<endl;
            for(int i=0;i<n;i++){
                QElemType e;
                cin>>e;
                EnQueue(Q,e);
            }
            cout<<n<<"个元素入队成功!"<<endl;
            Display(Q);
            cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
            break;
        case 3 :
            cout<<"请输入要出栈的元素的个数:"<<endl;
            int m;
            cin>>m;
            cout<<"出栈的元素依次为: ";
            for(int i=0;i<m;i++){
                cout<<DeQueue(Q)<<" ";
            }
            cout<<endl;
            Display(Q);
            cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
            break;
        case 4 :
            cout<<"该链队队首值为: "<<GetHead(Q)<<endl;
            cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
            break;
        case 5 :
            Display(Q);
            cout<<"请输入对应的数字选择您想要进行的操作:"<<endl;
            break;
        default :
            cout<<"您选择的操作不存在，请重新选择:"<<endl;
            break;
        }
    }
    return 0;
}

本文地址：https://blog.csdn.net/weixin_46353366/article/details/109016587

相关标签： 数据结构 算法 队列 栈

上一篇： 这个识别软件不简单 让摄像头也可选择性记忆

下一篇： 让苹果回家生产的川普会对VR业产生什么影响？

推荐阅读