数据结构算法学习-队列-栈

栏目: 数据库 · 发布时间: 5年前

内容简介:线性表抽象是存储具有先后顺序元素数据的结构,支持任意位置的插入,删除操作。队列和栈限制插入删除操作,队列只能从尾部插入,首部取出(删除),既先入先出;栈限制插入和取出操作只能在尾部进行,既先入后出。队列和栈同一般线性表相同,可用数组和链式结构体实现。由于限制了插入和取出的位置,没有频繁的中间元素操作,数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小,无法动态分配大小。

队列栈与一般线性表区别

线性表抽象是存储具有先后顺序元素数据的结构,支持任意位置的插入,删除操作。队列和栈限制插入删除操作,队列只能从尾部插入,首部取出(删除),既先入先出;栈限制插入和取出操作只能在尾部进行,既先入后出。

实现方式

队列和栈同一般线性表相同,可用数组和链式结构体实现。由于限制了插入和取出的位置,没有频繁的中间元素操作,数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小,无法动态分配大小。

代码实现

struct stack;
typedef struct stack sStack;
typedef sStack *pStack;

#define EmptyTOS -1;

struct stack {
    int capacity;
    int topOfStack;
    long long int *data;
};

pStack elrInitStackInt(int capaticy) {
    pStack s;

    s = malloc(sizeof(sStack));
    if (s == NULL) {
        printf("out of space!");
    }

    s->data = malloc(sizeof(long long int) * capaticy);
    if (s->data == NULL) {
        printf("out of space!");
    }

    s->capacity = capaticy;
    elrMakeStackEmpty(s);

    return s;
}

void elrFreeStackInt(pStack stack) {
    if (stack != NULL) {
        free(stack->data);
        free(stack);
    }
}

int elrIsStackEmpty(pStack stack) {
    return stack->topOfStack == EmptyTOS;
}

int elrIsStackFull(pStack stack) {
    return stack->topOfStack == (stack->capacity - 1);
}

void elrMakeStackEmpty(pStack stack) {
    stack->topOfStack = EmptyTOS;
}

void elrPushStackInt(pStack stack, long long int data) {
    if (elrIsStackFull(stack)) {
        printf("full stack");
    } else {
        stack->data[++stack->topOfStack] = data;
    }
}

long long int elrPopStackInt(pStack stack) {
    if (elrIsStackEmpty(stack)) {
        printf("empty stack");
    } else {
        return stack->data[--stack->topOfStack];
    }
}

队列

struct queue;
typedef struct queue sQueue;
typedef sQueue *pQueue;

struct queue {
    int capacity;
    int front;
    int rear;
    int size;
    long long int *data;
};

pQueue elrInitQueueInt(int capaticy) {
    pQueue s;

    s = malloc(sizeof(sQueue));
    if (s == NULL) {
        printf("out of space!");
    }

    s->data = malloc(sizeof(long long int) * capaticy);
    if (s->data == NULL) {
        printf("out of space!");
    }

    s->capacity = capaticy;
    elrMakeQueueEmpty(s);

    return s;
}

void elrFreeQueueInt(pQueue queue) {
    if (queue != NULL) {
        free(queue->data);
        free(queue);
    }
}

int elrIsQueueEmpty(pQueue queue) {
    return queue->size == 0;
}

int elrIsQueueFull(pQueue queue) {
    return queue->size == queue->capacity;
}

void elrMakeQueueEmpty(pQueue queue) {
    queue->size = 0;
    queue->front = 1;
    queue->rear = 0;
}

int succ(pQueue queue, int value) {
    if (++value == queue->capacity) {
        value = 0;
    }
    return value;
}

void elrEnqueuekInt(pQueue queue, long long int data) {
    if (elrIsQueueFull(queue)) {
        printf("full queue");
    } else {
        queue->size++;
        queue->rear = succ(queue, queue->rear);
        queue->data[queue->rear] = data;
    }
}

long long int elrDequeueInt(pQueue queue) {
    if (elrIsQueueEmpty(queue)) {
        printf("empty queue");
    } else {
        queue->size--;
        int data = queue->data[queue->front];
        queue->front = succ(queue, queue->front);
    }
}

以上所述就是小编给大家介绍的《数据结构算法学习-队列-栈》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

腾讯网UED体验设计之旅

腾讯网UED体验设计之旅

任婕 等 / 电子工业出版社 / 2015-4 / 99.00元

《腾讯网UED体验设计之旅》是腾讯网UED的十年精华输出,涵盖了丰富的案例、极富冲击力的图片,以及来自腾讯网的一手经验,通过还原一系列真实案例的幕后设计故事,从用户研究、创意剖析、绘制方法、项目管理等实体案例出发,带领读者经历一场体验设计之旅。、 全书核心内容涉及网媒用户分析与研究方法、门户网站未来体验设计、H5技术在移动端打开的触控世界、手绘原创设计、改版迭代方法、文字及信息图形化设计、媒......一起来看看 《腾讯网UED体验设计之旅》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

在线进制转换器
在线进制转换器

各进制数互转换器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具