数据结构实验1.4：栈和队列

实验内容 ：

1．采用链式存储实现栈的初始化、入栈、出栈操作。
2．采用顺序存储实现栈的初始化、入栈、出栈操作。
3．采用链式存储实现队列的初始化、入队、出队操作。
4．采用顺序存储实现循环队列的初始化、入队、出队操作。
5．在主函数中设计一个简单菜单，调用上述算法。

实验说明 :

1．顺序栈类型定义

const  int  MAX=20 ;   // 栈的最大值 
typedef  struct  
 {
ElemType  *base； 
int  top； 
} SqStack；  

2. 顺序队列类型定义

const  int  MAX=20 ;   // 队列的最大长度 
typedef  struct  
 {
ElemType  *base； 
int  front，rear； 
} SqQueue； 

源代码:

#include <iostream>
#include <stdlib.h>
using namespace std;

typedef int  ElemType;
const  int  MAX = 20;

typedef  struct         //顺序栈和队列类型定义
{
    ElemType  *base;
    int  top;
} SqStack;
typedef  struct
{
    ElemType  *base;
    int  front, rear;
} SqQueue;

typedef  struct Snode      //链式栈和队列类型定义
{
    ElemType data;
    Snode *next;
}*Stack;

struct  Qnode
{
    ElemType  data;
    Qnode *next;
};
struct QUEUE
{
    Qnode *front;
    Qnode *rear;
};

void Create_Stack(SqStack  &S)     //顺序栈相关操作
{
    S.base = new ElemType[MAX];
    S.top = -1;
}
bool S_Empty(SqStack S)  //栈是否为空
{
    if (S.top < 0)
        return true;
    else
        return false;
}
ElemType S_Top(SqStack &S) //栈顶元素
{
    if (S_Empty(S))
        return NULL;
    else
        return (S.base[S.top]);
}
void S_Pop(SqStack &S)  //出栈
{
    if (S_Empty(S))
    {
        cout << "栈为空！" << endl;
        return;
    }
    else
        S.top = S.top - 1;
}
void S_Push(SqStack &S, ElemType elem) //进栈
{
    if (S.top == MAX - 1)
    {
        cout << "栈满！" << endl;
        return;
    }
    else
    {
        S.top = S.top + 1;
        S.base[S.top] = elem;
    }
}
void Create_Queue(SqQueue &Q)      //顺序队列相关操作
{
    Q.base = new ElemType[MAX];
    Q.front = 0;
    Q.rear = MAX - 1;
}
int addone(int i)
{
    return ((i + 1) % MAX);
}
bool Q_Empty(SqQueue &Q)
{
    if (Q.front == addone(Q.rear))
        return true;
    else
        return false;
}
ElemType Q_Front(SqQueue Q)
{
    if (Q_Empty(Q))
        return NULL;
    else
        return Q.base[Q.front];
}
void Q_EnQueue(SqQueue &Q, ElemType elem)
{
    if (addone(addone(Q.rear)) == Q.front)
    {
        cout << "队列已满！" << endl;
        return;
    }
    else
    {
        Q.rear = addone(Q.rear);
        Q.base[Q.rear] = elem;
    }
}
void Q_DeQueue(SqQueue &Q)
{
    if (Q_Empty(Q))
    {
        cout << "队列为空！" << endl;
        return;
    }
    else
        Q.front = addone(Q.front);
}
Stack LinkStack_Init()      //链式栈的相关操作
{
    Stack S;
    S = new Snode;
    if (S == NULL)
    {
        cout << "链式栈创建不成功！" << endl;
        exit(0);
    }
    S->next = NULL;
    return S;
}
bool LinkS_Empty(Stack S)
{
    if (S->next)
        return false;
    else
        return true;
}
void LinkS_Push(ElemType elem, Stack S)
{
    Stack stk;
    stk = new Snode;
    stk->data = elem;
    stk->next = S->next;
    S->next = stk;
}
void LinkS_Pop(Stack S)
{
    Stack stk;
    if (S->next)
    {
        stk = S->next;
        S->next = stk->next;
        delete stk;
    }
}
ElemType LinkS_Top(Stack S)
{
    if (S->next)
        return S->next->data;
    else
        return NULL;
}
void LinkS_Free(Stack S)
{
    Stack stk;
    while (S)
    {
        stk = S;
        S = S->next;
        delete stk;
    }
}
void LinkQueue_Init(QUEUE &Q)   //链式队列的相关操作
{
    Q.front = new Qnode;
    Q.front->next = NULL;
    Q.rear = Q.front;
}
bool LinkQ_Empty(QUEUE Q)
{
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}
void LinkQ_EnQueue(ElemType elem, QUEUE &Q)
{
    Q.rear->next = new Qnode;
    Q.rear = Q.rear->next;
    Q.rear->data = elem;
    Q.rear->next = NULL;
}
void LinkQ_DeQueue(QUEUE &Q)
{
    Qnode *tmp;
    if (LinkQ_Empty(Q))
    {
        cout << "队列为空！" << endl;
        return;
    }
    else
    {
        tmp = Q.front->next;
        Q.front->next = tmp->next;
        delete tmp;
        if (Q.front->next == NULL)
            Q.rear = Q.front;
    }
}
ElemType LinkQ_Front(QUEUE Q)
{
    if (LinkQ_Empty(Q))
        return NULL;
    else
        return Q.front->next->data;
}
void LinkQ_Free(QUEUE Q)
{
    Qnode *tmp, *p;
    tmp = Q.front;
    while (tmp)
    {
        p = tmp;
        tmp = tmp->next;
        delete p;
    }
    Q.front = NULL;
    Q.rear = NULL;
}
int main()
{
    int  num;
    cout << "1:顺序存储实现<栈>的初始化、入栈、出栈操作" << endl;
    cout << "2:链式存储实现<栈>的初始化、入栈、出栈操作" << endl;
    cout << "3:顺序存储实现<循环队列>的初始化、入队、出队操作" << endl;
    cout << "4:链式存储实现<队列>的初始化、入队、出队操作" << endl;
    cout << "5:退出" << endl;
    while (true)
    {
        cout << "请输入一个数字选项:";
        cin >> num;
        switch (num)
        {
        case 1:
        {
            SqStack S;
            int n;
            ElemType elem;
            Create_Stack(S);
            cout << "输入需要进栈的元素个数（1~20）：" ;
            cin >> n;
            if (n < 0 || n>20)
            {
                cout << "输入错误！" << endl;
                return 0;
            }
            cout << "依次输入进栈的元素：";
            for (int i = 0; i < n; i++)
            {
                cin >> elem;
                S_Push(S, elem);
            }
            cout << "栈顶元素：" << S_Top(S) << endl;
            cout << "出栈一个元素" << endl;
            S_Pop(S);
            cout << "栈顶元素变为：" << S_Top(S) << endl;
            delete[] S.base;
            cout << endl;
        }break;
        case 2:
        {
            Stack S;
            int n;
            ElemType elem;
            S = LinkStack_Init();
            cout << "输入需要进栈的元素个数：" ;
            cin >> n;
            cout << "依次输入进栈的元素：";
            for (int i = 0; i < n; i++)
            {
                cin >> elem;
                LinkS_Push(elem, S);
            }
            cout << "栈顶元素：" << LinkS_Top(S) << endl;
            cout << "出栈一个元素" << endl;
            LinkS_Pop(S);
            cout << "栈顶元素变为：" << LinkS_Top(S) << endl;
            LinkS_Free(S);
            cout << endl;
        }break;
        case 3:
        {
            SqQueue Q;
            int n;
            ElemType elem;
            Create_Queue(Q);
            cout << "输入需要进队的元素个数（1~20）：";
            cin >> n;
            if (n < 0 || n>20)
            {
                cout << "输入错误！" << endl;
                return 0;
            }
            cout << "依次输入进对的元素：";
            for (int i = 0; i < n; i++)
            {
                cin >> elem;
                Q_EnQueue(Q, elem);
            }
            cout << "队头元素：" << Q_Front(Q) << endl;
            cout << "出队一个元素" << endl;
            Q_DeQueue(Q);
            cout << "队头元素变为：" << Q_Front(Q) << endl;
            delete[] Q.base;
            cout << endl;
        }break;
        
        case 4:
        {
            QUEUE Q;
            int n;
            ElemType elem;
            LinkQueue_Init(Q);
            cout << "输入需要进队的元素个数：" ;
            cin >> n;
            cout << "依次输入进对的元素：";
            for (int i = 0; i < n; i++)
            {
                cin >> elem;
                LinkQ_EnQueue(elem, Q);
            }
            cout << "队头元素：" << LinkQ_Front(Q) << endl;
            cout << "出队一个元素" << endl;
            LinkQ_DeQueue(Q);
            cout << "队头元素变为：" << LinkQ_Front(Q) << endl;
            LinkQ_Free(Q);
            cout << endl;
        }break;
        case 5:
        {
            return 0;
        }break;
        default:
            cout << "输入错误！请重新输入！" << endl;
        }
    }
    return 0;
}

运行截图：

image