C/C++知识点之数据结构之队列和栈-职坐标

C/C++知识点之数据结构之队列和栈

小标 2019-02-19 来源：阅读 1254 评论 0

摘要：本文主要向大家介绍了 C/C++知识点之数据结构之队列和栈，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍了 C/C++知识点之数据结构之队列和栈，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

C/C++知识点之数据结构之队列和栈

No.1 抽象数据类型栈的定义

栈是限定在队尾进行操作的线性表，因此对于栈来说，队尾有特殊意义，称为栈顶，表头端成为栈底，没有任何元素的栈称为空栈

特点：

它是线性表

这个线性表只能在栈顶操作

No.2 栈的表示

栈的先进后出原则

使用栈存储数据元素，对数据元素的存和取有严格的限定，数据按照一定的顺序存储到栈中，当需要调取栈中的数据元素时，需要将该数据元素之后进栈的数据进行弹栈，该数据元素才能从栈中取出来

栈操作数据元素的方法

入栈数据元素用栈的数据结构存储起来，也叫压栈

出栈将数据元素从栈中取出来，也叫弹栈

栈的两种表示方式

栈既然是一种特殊的线性表，那么它同样有线性表的两种表现形式，顺序栈和链栈

栈的上溢和下溢

当栈中已经没有元素位置了，再向栈中存储数据会产生上溢，链栈不会产生上溢

当栈已经是一个空栈，再继续从栈中取数据会产生下溢

No.3 实现栈

顺序栈

#include <stdio.h>

//元素elem进栈
int push(int *stack, int top, int elem) {
    stack[++top] = elem;
    return top;
}

//数据元素出栈
int pop(int *stack, int top) {
    if (top == 0) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n", stack[top]);
    top--;
    return top;
}

int main() {
    int stack[100];
    int top = 0;
    top = push(stack, top, 1);
    top = push(stack, top, 2);
    top = push(stack, top, 3);
    top = push(stack, top, 4);
    top = pop(stack, top);
    top = pop(stack, top);
    top = pop(stack, top);
    top = pop(stack, top);
    top = pop(stack, top);
    return 0;
}

链栈

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct LineStack{
    char data;
    struct LineStack * next;
}LineStack;

LineStack* push(LineStack * stack,char e){
    LineStack * line=(LineStack*)malloc(sizeof(LineStack));
    line->data=e;
    line->next=stack;
    stack=line;
    return stack;
}
LineStack * pop(LineStack * stack){
    if (stack) {
        LineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素：%c ",p->data);
        if (stack) {
            printf("栈顶元素：%c\n",stack->data);
        }else{
            printf("栈已空！\n");
        }
        free(p);
    }else{
        printf("栈内没有元素！\n");
        return stack;
    }
    return stack;
}
int main() {
    LineStack * stack=NULL;
    stack=push(stack, 'k');
    stack=push(stack, 'e');
    stack=push(stack, 'r');
    stack=push(stack, 'n');
    stack=push(stack, 'e');
    stack=push(stack, 'l');
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

No.4 抽象的数据类型队列的定义

先进先出队列和栈相反，队列是一种先进先出的线性表，它允许再表的一端插入数据，在另一端取出数据，这和我们日常生活中的排队打饭是一致的，最早排队的先吃到

双端队列双端队列是限定插入和删除操作在表的的两端进行的线性表，在实际应用场景中，还可以具体分为输出受限和输入受限双端队列

输出受限，就是一端允许插入和删除，另一个端点允许插入

输入受限就是一端允许插入和删除，另一个端点允许删除

No.5 链队列

和线性表类似，队列也有两种表示形式，用链表表示的队列成为链队列，一个链队列需要两个分别只是对头和队尾的指针

#include <stdio.h>
#include <malloc.h>
#include <windows.h>

#define TRUE 1
#define  FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int QElemType;

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

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

//构造一个空队列
Status InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q.front) {
        exit(OVERFLOW);
    }
    Q.front->next = NULL;
    return OK;
}

//销毁队列
Status DestoryQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}

//队列入队
Status EnQueue(LinkQueue &Q, QElemType e) {
    QueuePtr p;
    p = (QueuePtr) malloc(sizeof(QNode));
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

Status DeQueue(LinkQueue &Q, QElemType &e) {
    QueuePtr p;
    if (Q.front == Q.rear) {
        return ERROR;
    }
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p);
    return OK;
}

Status displayQueue(LinkQueue &Q) {
    QueuePtr front, rear;
    front = Q.front->next;
    rear = Q.rear;
    if (front == rear) {
        printf("空队列！\n");
        return OK;
    }
    while (front != NULL) {
        printf("%d\t", front->data);
        front = front->next;
    }
    printf("\n");
    return OK;
}

int main() {
    LinkQueue Q;
    int e;
    InitQueue(Q);
    EnQueue(Q, 10);
    EnQueue(Q, 20);
    EnQueue(Q, 30);
    EnQueue(Q, 40);
    printf("队中的元素是：\n");
    displayQueue(Q);
    DeQueue(Q, e);
    printf("出队的元素是： %d\n", e);
    printf("队中的元素是：\n");
    displayQueue(Q);
    DestoryQueue(Q);
}

No.6 循环队列

使用数组存取数据元素时，可以将数组申请的空间想象成首尾连接的环状空间使用

#include <stdio.h>
#include <malloc.h>
#include <windows.h>

#define TRUE 1
#define  FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXQSIZE 100 //最大队列长度

typedef int Status;
typedef int QElemType;

typedef struct {
    QElemType *base;
    int front; //队头指针
    int rear;  //队尾指针
} SqQueue;

//构造一个空队列 Q
Status InitQueue(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base) {
        exit(OVERFLOW); //存储分配
    }
    Q.front = Q.rear = 0;
    return OK;
}
Status DestroyQueue(SqQueue &Q)
{
    if(!Q.base)
    {
        printf("空队列\n");
        return OK;
    }
    free(Q.base);
    return OK;
}
int QueueLength(SqQueue Q)
{
    //返回Q的元素个数，即队列的长度
    return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
}
Status EnQueue(SqQueue &Q,QElemType e)
{
    //插入元素 e 为Q的新的队尾元素
    if((Q.rear+1)%MAXQSIZE == Q.front) {
        return ERROR; //队列满
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1)%MAXQSIZE;
    return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{
    //若队列不空，则删除Q的队头元素，用 e 返回其值，并返回OK;
    //否知返回ERROR
    if(Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front + 1)%MAXQSIZE;
    return OK;
}
Status displayQueue(SqQueue &Q)
{
    int front,rear;
    front = Q.front;
    rear = Q.rear;
    if(front == rear)
    {
        printf("空队列\n");
        return OK;
    }
    while((front + 1)%MAXQSIZE != rear)
    {
        printf("%d\t",Q.base[front]);
        front++;
    }
    printf("%d\n",Q.base[front]);
    return OK;
}
int main()
{
    SqQueue Q;
    int e;
    //初始化队列
    InitQueue(Q);
    //入队
    EnQueue(Q,10);
    EnQueue(Q,20);
    EnQueue(Q,30);
    printf("循环队列中的数据为：\n");
    displayQueue(Q);
    //出队
    DeQueue(Q,e);
    printf("出队的元素是：%d\n",e);
    printf("循环队列中的数据为：\n");
    displayQueue(Q);
    //销毁队列
    DestroyQueue(Q);
    system("pause");
    return 0;
}