数据结构(2)—— 栈与队列

写在前面

为了考研,需要复习数据结构。而对于数据结构这门学科来说,写代码是非常必要的。用代码把一些常见的数据结构与算法实现一遍,非常有利于对于数据结构的理解。

关于第一篇:数据结构(1)—— 线性表

这一篇主要是栈与队列的实现。栈与队列都是操作受限的线性表,栈只能从一端进出,队列只能一端出一端进。这两种数据结构在我们的实际开发中应用的十分多,因此对这部分不管是出于考研还是工作都要掌握。

顺序栈

注意点

关于顺序栈的实现,要注意的地方其实并不多。最核心的就是top指针的初始化情况了。这里我把top指针设在了-1,也可以设在0,不过设置为0时判空和进出栈的条件就不大一样了,需要注意。

代码

/*
 * @Description: 顺序栈的实现
 * @version: 1.0
 * @Author: Liuge
 * @Date: 2021-07-09 20:25:53
 */

#include<bits/stdc++.h>
#define maxSize 50

// 顺序栈的存储结构
typedef struct{
    int data[maxSize];
    // 栈顶指针
    int top;
}SqStack;

// 初始化栈
void initStack(SqStack &S){
    // 这里把栈顶指针设为-1,也可以设为0
    S.top = -1;
}

// 判空
bool isStackEmpty(SqStack S){
    return S.top == -1;
}

// 进栈
bool push(SqStack &S, int e){
    // 栈满
    if(S.top == maxSize -1){
        return false;
    }
    S.data[++S.top] = e;
    return false;
}

// 出栈
bool pop(SqStack &S,int &e){
    // 栈空
    if(S.top == -1){
        return false;
    }
    e = S.data[S.top--];
    return true;
}

// 读栈顶元素
bool getTop(SqStack &S,int &e){
    if(S.top == -1){
        return false;
    }
    e = S.data[S.top];
    return true;
}

// 遍历栈
void printStack(SqStack S){
    printf("栈中的元素为:\n");
    while(!isStackEmpty(S)){
        int topElem;
        getTop(S,topElem);
        printf("%d ",topElem);
        S.top--;
    }
    printf("\n");
}

// 主函数测试
int main(){
    SqStack S;
    // 创建一个栈
    initStack(S);
    printStack(S);
    // 放几个元素试试
    push(S,3);
    push(S,4);
    push(S,5);
    // 输出应该是5 4 3
    printStack(S);
    // 出一个
    int popElem;
    pop(S,popElem);
    printf("\n出栈的元素为 -> %d\n",popElem);
    printStack(S);
    // 读一个
    int topElem;
    getTop(S,topElem);
    printf("\n栈顶的元素为 -> %d\n",topElem);
    return 0;
}

循环队列

注意点

由于队列的特殊性,顺序队列实现的价值并不高。这里直接实现循环队列。循环队列最核心的地方便在于判断当前队列是否为满,这里我的代码使用的是牺牲一个内存单元来区分队满和队空,当然你也可以采用别的方式,如王道书上提到的增设一个size变量,或增加一个tag标记,都可以实现对于队满的判断,这里不再赘述。

代码

/*
 * @Description: 循环队列的实现——牺牲一个内存单元来区分队满和队空
 * @version: 1.0
 * @Author: Liuge
 * @Date: 2021-07-10 19:13:15
 */

#include<bits/stdc++.h>
#define maxSize 50

// 定义循环队列的结构
typedef struct{
    int data[maxSize];
    // 队头指针
    int front;
    // 队尾指针
    int rear;
}SqQueue;

// 初始化队列
void initQueue(SqQueue &Q){
    // 将队首和队尾指针都指向0
    Q.rear = Q.front = 0;
}

// 判队空 rear==front
bool isEmpty(SqQueue Q){
    return Q.rear==Q.front;
}

// 求当前队列长度
int getQueueLength(SqQueue Q){
    return (Q.rear + maxSize - Q.front) % maxSize;
}

// 入队
bool enQueue(SqQueue &Q,int x){
    // 判队满,rear + 1 % maxSize = front
    if((Q.rear + 1) % maxSize == Q.front){
        return false;
    }
    Q.data[Q.rear] = x;
    // 队尾指针+1取模,起到循环效果
    Q.rear = (Q.rear + 1) % maxSize;
    return true;
}

// 出队
bool deQueue(SqQueue &Q,int &x){
    // 判队空
    if(isEmpty(Q)){
        return false;
    }
    x = Q.data[Q.front];
    // front+1取模
    Q.front = (Q.front + 1) % maxSize;
    return true;
}

// 打印
// 这里可以这么写,是因为Q里的是数组
// 这样这里就是一个新的数组了,不会影响原本的数组,顺序栈那里同理
void printQueue(SqQueue Q){
    printf("队列中的元素为:\n");
    while(!isEmpty(Q)){
        int deQueueElem;
        deQueue(Q,deQueueElem);
        printf("%d ",deQueueElem);
    }
    printf("\n");
}
// 主函数测试

int main(){
    SqQueue Q;
    // 初始化队列
    initQueue(Q);
    printQueue(Q);
    // 入队几个元素
    enQueue(Q,3);
    enQueue(Q,4);
    enQueue(Q,5);
    // 打印应该为 3 4 5
    printQueue(Q);
    // 出队几个试试
    int deElem;
    deQueue(Q,deElem);
    printf("出队元素为 -> %d\n",deElem);
    printf("当前队列长度为 -> %d\n",getQueueLength(Q));
    printQueue(Q);
}

链式队列

注意点

链式队列的实现,需要注意队头的设置。这里我把队头设置在了链表的头部,那么队尾就是链表的尾部了。我实现的是带有头结点的链式队列,这样的比较好实现,读者也可以自己试试如何实现不带头结点的。

代码

/*
 * @Description: 链式队列的实现
 * @version: 1.0
 * @Author: Liuge
 * @Date: 2021-07-10 20:45:24
 */
#include<bits/stdc++.h>

// 定义结点的结构
typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;
// 定义链式队列的结构
typedef struct{
    LinkNode *front;
    LinkNode *rear;
}LinkQueue;

// 初始化
void initQueue(LinkQueue &Q){
    // 建立头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

// 判队空
bool isEmpty(LinkQueue Q){
    return Q.front == Q.rear;
}

// 入队
void enQueue(LinkQueue &Q,int x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    // 队尾指针移动到新的尾部
    Q.rear = s;
}

// 出队
bool deQueue(LinkQueue &Q,int &x){
    if(isEmpty(Q)){
        return false;
    }
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    // 如果原队列只有一个结点,删除后变空
    if(Q.rear == p){
        Q.rear = Q.front;
    }
    free(p);
    return true;
}

// 打印 
// 注释掉的写法中,虽然这里的Q和main里的Q不是同一个
// 但后续连接的结点都是同一个(即同一块内存空间)
// 如果调用了deQueue函数,会把结点free掉,导致main里接下来的deQueue无法使用,报segement fault异常(内存无法访问,因为已经被释放了)
// 正确的做法应该是拿另一个指针去遍历这个链表
void printQueue(LinkQueue Q){
    printf("队列中的元素为:\n");
    // while(!isEmpty(Q)){
    //     int deElem;
    //     deQueue(Q,deElem);
    //     printf("%d ",deElem);
    // }
    LinkNode *p = Q.front->next;
    while (p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 主函数测试
int main(){
    LinkQueue Q;
    // 初始化
    initQueue(Q);
    printQueue(Q);
    // 放几个元素
    enQueue(Q,1);
    enQueue(Q,3);
    enQueue(Q,5);
    // 应该输出:1 3 5
    printQueue(Q);
    // 出队一个元素
    int deElem;
    deQueue(Q,deElem);
    printQueue(Q);
    return 0;
}

栈的应用——表达式求值

算法简述

这个算法,称得上是一个非常经典的算法了。这里我先用常规的语言描述一下这个算法:

  1. 初始化两个栈,操作数栈与运算符栈。
  2. 若扫描到操作数,压入操作数栈。
  3. 若扫描到运算符或界限符(这里主要指的就是()),那么就比对运算符栈顶与扫描到的运算符或界限符的优先级,如果栈顶符号的优先级大于等于扫描到的,那么就弹出运算符栈,操作数栈弹出两个值,按照弹出的运算符进行运算后再次压入到操作数栈。
  4. 扫描到字符串结尾,将操作数栈的栈顶元素弹出就是结果。

这个算法具体的演示与操作步骤,大家可以百度搜一下。

而我这里实现的这个算法,实现了多位数的求值,如100*100+100这种的,主要是使用了一个counter变量来判断是否为多位数。具体逻辑直接看代码吧。

代码

/*
 * @Description: 表达式求值
 * @version: 1.0
 * @Author: Liuge
 * @Date: 2021-07-12 19:30:34
 */
#include <bits/stdc++.h>
using namespace std;

// 运算符栈
stack<char> opter;   
// 操作数栈
stack<double> opval; 

// 获取theta所对应的索引
int getIndex(char theta)
{
    int index = 0;
    switch (theta)
    {
    case ‘+‘:
        index = 0;
        break;
    case ‘-‘:
        index = 1;
        break;
    case ‘*‘:
        index = 2;
        break;
    case ‘/‘:
        index = 3;
        break;
    case ‘(‘:
        index = 4;
        break;
    case ‘)‘:
        index = 5;
        break;
    case ‘#‘:
        index = 6;
    default:
        break;
    }
    return index;
}

// 获取theta1与theta2之间的优先级
char getPriority(char theta1, char theta2)
{
    // 算符间的优先级关系
    const char priority[][7] = 
        {
            {‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘},
            {‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘},
            {‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘>‘, ‘>‘},
            {‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘>‘, ‘>‘},
            {‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘=‘, ‘0‘},
            {‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘0‘, ‘>‘, ‘>‘},
            {‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘0‘, ‘=‘},
        };

    int index1 = getIndex(theta1);
    int index2 = getIndex(theta2);
    return priority[index1][index2];
}

// 计算a theta b
double calculate(double a, char theta, double b)
{
    switch (theta)
    {
    case ‘+‘:
        return a + b;
    case ‘-‘:
        return a - b;
    case ‘*‘:
        return a * b;
    case ‘/‘:
        return a / b;
    default:
        return 0;
    }
}

// 表达式求值
double getAnswer() 
{
    // 首先将‘#‘入栈opter
    opter.push(‘#‘); 
    // 添加变量counter表示有多少个数字相继入栈,实现多位数的四则运算
    int counter = 0; 
    char c = getchar();
    // 终止条件
    while (c != ‘#‘ || opter.top() != ‘#‘) 
    {
        // 如果c在‘0‘~‘9‘之间 使用isdigit函数用来判断字符型变量是否是数字
        if (isdigit(c)) 
        {
            // counter==1表示上一字符也是数字,所以要合并,比如12*12,要算12,而不是单独的1和2
            if (counter == 1) 
            {
                double t = opval.top();
                opval.pop();
                opval.push(t * 10 + (c - ‘0‘));
                counter = 1;
            }
            else
            {
                // 将c对应的数值入栈opval
                opval.push(c - ‘0‘); 
                counter++;
            }
            c = getchar();
        }
        else
        {
            // counter置零
            counter = 0;                        
            // 获取运算符栈opter栈顶元素与c之间的优先级,用‘>‘,‘<‘,‘=‘表示 
            switch (getPriority(opter.top(), c)) 
            {
            // <则将c入栈opter
            case ‘<‘: 
                opter.push(c);
                c = getchar();
                break;
            // =将opter栈顶元素弹出,用于括号的处理
            case ‘=‘: 
                opter.pop();
                c = getchar();
                break;
            // >则计算
            case ‘>‘: 
                char theta = opter.top();
                opter.pop();
                double a = opval.top();
                opval.pop();
                double b = opval.top();
                opval.pop();
                opval.push(calculate(b, theta, a));
            }
        }
    }
    // 返回opval栈顶元素的值
    return opval.top(); 
}

int main()
{
    cout << "请输入算数运算式(以#结尾)" << endl;
    while (!opter.empty())
        opter.pop();
    while (!opval.empty())
        opval.pop();
    double ans = getAnswer();
    cout << ans << endl;
    return 0;
}

总结

总的来说,这块一定要好好掌握。参考书籍依然是王道的数据结构辅导书。参考代码来自网络。

数据结构(2)—— 栈与队列

上一篇:JZOJ 3423.Vani和Cl2捉迷藏 & [CTSC2008]祭祀


下一篇:Class 类的理解