数据结构03-队列和栈

3：队列（QUEUE）

3.1：队列的定义和性质

队列：只允许前端（front，队首）进行删除操作，而在后端（rear，队尾）进行插入操作的数据结构。

从队首删除队尾插入的性质，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的数据结构。

队列最典型的性质：先进先出(FIFO)。

如：操作系统的进程调度就是用的队列。

3.2：队列的结构和常见操作

3.2.1：队列结构：尾部插入，前端删除

image.png

队列底层数据结构可以使用链表或者数组。

基于数组的队列，在不断的插入元素和删除元素的时候，数组的内存空间将会不断的向上滑动（如上图中间部分所示），这在实际应用过程中肯定是不好的，因此假如数组的长度为MAX，通过用rear=(rear+1)%MAX和front=(front+1)%MAX来移动数组的前端和尾端，可以限制它们在数组的当前空间，这样就构成了一个循环队列（如上图右边部分所示）。

3.2.1：队列基本操作

队列包含创建，入队，出队，队空判断，对满判断等操作。

  1. 创建-int CreateQue();用于创建一个队列，一般需要初始化队列的前端和后端指针。
  2. 入队-int EnQueue(int e);将特定的元素e从队列的尾部插入。
  3. 出队-int DeQueue(int *e);获取队列头部的数据并从队列删除。
  4. 判断队列满-int IsQueueFull();判断队列是否已满，如果队列满了就不能再从尾部插入数据了，只对基于数组的队列有效。
  5. 判断队列空-int IsQueueEmpty();判断队列是否为空，如果队列为空，就不能从队首删除数据了，在构造基于链表的队列的 时候，队列为空，插入第一个元素的时候，也需要特别的处理。

3.3：基于链表的队列实现

基于链表的数组没有满的时候

如图：


image.png

链表结点的存储结构如下：

typedef struct _node {
       int value;
       struct _node *next;
}node, *pnode;

//其中值的部分存放的是一个整数data，这部分数据可以自己再定义，增减。
node *front = NULL;   //队头指针，由于是全局变量，请注意多线程安全
node *rear = NULL;    //队尾指针，由于是全局变量，请注意多线程安全

//创建
int creatQueue() {
    front = rear = NULL;//将front和rear置为NULL
    
    return 1;
}

//判断队列是否为空
int isQueueEmpty() {
    if(front==NULL&&rear==NULL) {//front和rear等于NULL是队列为空的标志
        return 1;
    }
    
    return 0;
}

//入队
int enQueue(int value) {
    node *p = (node *)malloc(sizeof(node));
    
    if (!p) {
        return -1;
    }
    
    memset(p, 0, sizeof(node));
    p->value = value;
    p->next = NULL;
    
    if(isQueueEmpty) {//队列为空，直接将rear和front指向该结点
        rear = front = p;

        return 1;
    } else {
        rear->next = p;
        p->next = NULL;
        rear = p;
        
        return 1;
    }
}

//出队
int deQueue(int *pValue) {//必须传指针，否则出队的值无法获取
    if(pValue == NULL) {//传入空值
        return -1;
    }
    
    if(isQueueEmpty) {//空链表
        return -1;
    } 
    
    if(rear==front && rear!=NULL && front!=NULL) {//一个节点时
        *e = front->value;
        free(front);
        front = rear = NULL;
        
        return 1;
    }
    
    *e = front->value;
    node *pfront = front;
    front = front->next;
    free(pfront);
    
    return 1;
}

//遍历队列
void traverseQueue() {
    while(!isQueueEmpty()) {
        int value;  
        deQueue(&value);
        printf("%d ",value);
    }
    
    printf("\n");
}

//队列测试代码
int main(int argc, int* argv[]) {
    int value;
    
    createQueue();
    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    
    deQueue(&value);
    printf("value:%d\n", value);
       
    enQueue(5);
    enQueue(6);
    
    deQueue(&value);
    printf("value:%d\n", value);
    deQueue(&value);
    printf("value:%d\n", value);
       
    traverseQueue();
    
    return 0;
}

3.4：基于数组的队列实现

基于数组的循环队列，有3种形态：

  1. 队列为空:front等于rear；
  2. 正常形态:front指向队首元素，rear指向队尾元素的下一个位置；
  3. 队列满：这个时候，队尾指针指向队首指针的前一个位置（空位）。
image.png
#define MAXSIZE 100//数组的元素个数
int arrayQueue[MAXSIZE]={0};//队列的底层数据结构，数组，支持100个元素
int rear = 0;//队列后端，插入的位置
int front = 0;//队列前端，删除的位置

//创建
int creatArrayQueue() {
    front = rear = 0;//将front和rear置为0
    
    return 1;
}

//判断队列是否为空 
int isArrayQueueEmpty() {//front等于rear，队列即为空
    if (front == rear) {
        return 1;
    } 
    
    return 0;
}

//判断队列是否为满
int isArrayQueueFull() {
    if (front == (rear+1)% MAXSIZE) {
        return 1;
    }
    
    return 0;
}

//入队
int enArrayQueue(int value) {
    if(isArrayQueueFull()) {
        return -1;
    }
    
    arrayQueue[rear] = value;
    rear = (rear+1)%MAXSIZE;
    
    return 1;
}

//出队
int duArrayQueue(int *pValue) {
    if(isArrayQueueEmpty()) {
        return -1;
    }
    
    if(pValue == NULL) {
        turn -1;
    }
    
    *pValue = arrayQueue[front];
    front = (front+1)%MAXSIZE;
    
    return 1;
}

//遍历
int traverseQueue() {
    while(!isQueueEmpty()) {
        int value;
        
        if(deQueue(&value)) {
            printf("%d", v);
        }
    }
    
    printf("\n");
    
    return 1;
}

4：栈(STACK)

4.1：栈的定义和性质

栈：允许在同一端进行插入和删除操作的数据结构。

  1. 栈顶(top)：被允许进行插入和删除操作的一端；栈顶浮动；
  2. 栈底(bottom)：栈底固定
  3. 空栈：栈中元素个数为零时为空栈
  1. 进栈(PUSH)：插入元素
  2. 出栈(POP)：删除元素

由于栈规定只能在同一端进行插入和删除，因此栈的一个典型特点就是后进先出。

栈.png

4.2：栈的结构和常见操作

4.2.1：栈的结构

栈的底层数据结构包含链表与数组。可以通过链表或者数组来构造栈。


基于链表的栈.png
基于数组的栈.png

4.3：栈的基本操作

1. 栈的创建:int createStack();负责初始化栈的基本结构，比如栈顶指针的初始化。
2.入栈:int push(int data);将数据从栈顶插入
3.出栈:int pop(int *data);获取栈顶数据，并将数据从栈顶删除
4.栈空判断:int isStackEmpty();判断栈是否为空，栈为空，就不能再pop了。
5.栈满:int isStackFull();判断栈是否为满，栈满就不能再插入数据了。只有基于数组的栈，才需要判断栈是否已满。

4.4：基于链表的栈实现

//先定义栈的结点结构：
typedef struct _node {
       int value;
       struct _node *next;
} node, *pnode;

//栈顶指针初始化：
node *top = NULL;

//创建栈：
int createStack() {
       top = NULL;

       return 1;
}

 

//判断栈是否为空：
int isStackEmpty() {
       return top==NULL?1:0;//top为NULL的时候，栈为空
}

//入栈：
int push(int value) {
       node *p = (node *)malloc(sizeof(node));

       if(p==NULL) {
              return -1;
       }

       memset(p,0,sizeof(node));
       p->value = value;
       p->next = NULL;

       //栈为空的时候，插入的是第一个结点
       if(isStackEmpty()) {
              top = p;

              return 1;
       }

       //栈非空的时候，插入一个结点
       p->next = top;
       top = p;

       return 1;
}

//出栈
int pop(int *e) {
       if (isStackEmpty()) {
              return -1;
       }

       if(e == NULL) {
              return -1;
       }

       //当栈只有一个结点的时候：
       if(top->next == NULL) {
              *e = top->value;
              free(top);
              top = NULL;

              return 1;
       } 

       //当栈中存放不止一个元素的时候
       *e = top->value;
       node *p = top;
       top = top->next;
       free(p);
       
       return 1;
}

//栈的遍历：
void traverseStack() {
       while(!IsStackEmpty()) {
              int val;
              pop(&val);
              printf("%d ", val);
        }

       printf("\n");
}

//接口测试：

int _tmain(int argc, _TCHAR* argv[]) {
       createStack();
       
       for(int i=0; i<10; i++) {
              push(i+1);
       }

       int val;
         pop(&val);
       printf("val:%d\n", val);

       traverseStack();

       return 0;
}

4.5：基于数组的栈实现

image.png
#define MAXSIZE 1000//栈中数组容纳的元素个数
int stackArray[MAXSIZE]={0};//栈的底层数据结构：数组stack
int top=0;//栈顶

//创建栈
int createStack() {
       top = 0;//将top置零

       return 1;
}

//判断栈是否满
int isStackFull() {
       return top==MAXSIZE?1:0;
}

//判断栈是否空
int isStackEmpty() {
       return top==0?1:0;
}

//入栈：
int push(int val) {
       if(isStackFull()) {
              return -1;
       }

       stackArray[top++]=val;

       return 1;
}

//出栈：
int pop(int *e) {
       if(isStackEmpty()) {
              return -1;
       }

       if(e==NULL) {
              return -1;
       }
       
       *e = stackArray[--top];
       
       return 1;
}

//栈的遍历：
void traverseStack() {
       while(!isStackEmpty()) {
              int val;
              pop(&val);
              printf("%d ",val);
       }

       printf("\n");
}

//接口测试：
int _tmain(int argc, _TCHAR* argv[]) {
       createStack();

       for(int i=0;i<500;i++) {
              push(i+1);
       }

       int val;
       pop(&val);
       printf("val:%d\n", val);

       traverseStack();

       return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,098评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,213评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,960评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,519评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,512评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,533评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,914评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,574评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,804评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,563评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,644评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,350评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,933评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,908评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,146评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,847评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,361评论 2赞 342

推荐阅读更多精彩内容

  • 疯狂java笔记之栈和队列
    栈 栈的英文单词是Stack,它代表一种特殊的线性表，这种线性表只能在固定一端（通常认为是线性表的尾端）进行插入，...
    Jack921阅读 1,492评论 0赞 5
  • 二. 数据结构之线性结构
    本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,862评论 0赞 7
  • 计算机二级选择题干货（五）——数据结构和算法
    1、线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表，这种线性表只能在固定的...
    雾熏阅读 2,380评论 0赞 10
  • 阅读理解
    这阵子读了点书，越读我越困惑。我在想作者在写这些的时候想了些什么，为什么要写？我看到的是否是表面？于是我没看完一本...
    蒋将江阅读 123评论 0赞 0
  • 聊天语言
    // 我聊天的时候说话会无意识的逗趣…… 敲完发出去了才发现自己幽默了一下，还是挺冷的那种。 接着越看越起鸡皮疙瘩...
    寒岚秋水阅读 117评论 0赞 0