首页 > 其他分享 >王道408用数组，链表以及双向链表实现栈、队列

王道408用数组，链表以及双向链表实现栈、队列

时间：2023-08-05 18:55:39浏览次数：32  
标签：王道 return int next 链表 bool data rear 408

我在电脑上敲了一遍，又在纸上模拟了一遍

下面记录在电脑上敲的:

一、用数组实现栈

#include <stdio.h>
#include <string.h>
#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int top;
}stack;

void InitStack(stack & S){
    S.top = -1;
    S.data[0] = 5;
    memset(S.data,0,sizeof(S.data));
    // printf("%x\n%x\n\n\n",S.data,&S.data);          // 这俩地址指向了同一个位置a
}

bool IsEmpty(stack S){
    if(S.top == -1)
        return 1;
    return 0;
}

bool IsFull(stack S){
    if(S.top == MaxSize-1)
        return 1;
    return 0;
}

bool Push(stack &S,int x){
    if(IsFull(S))
        return 0;
    S.data[++S.top] =  x;
    return 1;
}

bool Pop(stack &S,int &x){
    if(IsEmpty(S))
        return 0;
    x = S.data[S.top--];
    return 1;
}

int main(){
    stack sk;
    InitStack(sk);
    Push(sk,1);
    Push(sk,2);
    Push(sk,3);
    Push(sk,4);
    Push(sk,5);
    int ans;
    for(int i=0;i<=7;i++){
        if(Pop(sk,ans)){
            printf("%d\n",ans);
        }
        else{
            puts("Empty Stack!!!");
        }
    }
    return 0;
}

二、用单链表实现栈

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

#include <typeinfo>
typedef struct SNode{
    int data;
    struct SNode *next;
} SNode,*Listack;


void InitStack(Listack &S){  // 定义头节点
    S = (Listack )malloc(sizeof(SNode));
    S->next = NULL;
    return ;
}

bool IsStackEmpty(Listack S){
    if(S->next == NULL){
        return 1;
    }
    return 0;
}
bool StackPush(Listack &S,int x){
    SNode * p = (SNode *)malloc(sizeof(SNode));
    p->data = x;
    p->next = S->next;
    S->next = p;
    return 1;
}
bool StackPop(Listack &S,int &x){
    if(IsStackEmpty(S)){
        return 0;
    }
    SNode * p = S->next;
    x = p->data;
    S->next = p->next;
    free(p);
    return 1;
}

int main(){
    SNode * sn;
    InitStack(sn);
    StackPush(sn,1);
    StackPush(sn,2);
    StackPush(sn,3);
    StackPush(sn,4);
    StackPush(sn,5);
    int ans;
    for(int i = 0;i<=7;i++){
        if(StackPop(sn,ans)){
            printf("%d\n",ans);
        }
        else{
            printf("EmptyStack!!!\n");
        }
    }
    return 0;
}

三、用双链表实现栈

#include <stdio.h>
#include <malloc.h>
typedef struct _DbNode{
    int data;
    struct _DbNode * next;
    struct _DbNode * last;
}DbNode,*PDNode;


typedef struct _LiDbNode{           // 定义这个结构体只是为了管理收尾两个节点，中间的节点还是全部由DbNode构成的
    DbNode * head;
    DbNode * rear;
}LiDbNode,*PDbStack;

void InitDbNode(PDbStack &S){
    DbNode * p = (DbNode *)malloc(sizeof(DbNode));
    S = (LiDbNode *)malloc(sizeof(LiDbNode));
    p->last = p->next = NULL;
    S->head = S->rear = p;
}

bool DbStackPush(PDbStack  &S,int x){
    DbNode * p = (DbNode *)malloc(sizeof(DbNode));
    p->data = x;
    p->next = NULL;
    p->last = S->rear;
    S->rear->next = p;
    S->rear = p;
    return 1;
}

bool IsDbStackEmpty(PDbStack S){
    if(S->head == S->rear){
        return 1;
    }
    return 0;
}

bool DbStackPop(PDbStack &S,int &x){
    if(IsDbStackEmpty(S)){
       return 0;
    }
    
    DbNode * p = S->rear;           // 注意这里 S->rear指向的就是尾节点，而在后续用单链表实现Queue的时候，S-front指向的是头节点，也就是说S->front->next才是指向的节点，这是一个小坑，注意!!
    p->last->next = NULL;
    S->rear = p->last;
    x = p->data;
    free(p);    
    return 1;
}

int main(){
    PDbStack sn;
    InitDbNode(sn);
    DbStackPush(sn,1);
    DbStackPush(sn,2);
    DbStackPush(sn,3);
    DbStackPush(sn,4);
    DbStackPush(sn,5);
    int ans;
    for(int i = 0;i<=7;i++){
        if(DbStackPop(sn,ans)){
            printf("%d\n",ans);
        }
        else{
            printf("EmptyStack!!!\n");
        }
    }


    return 0;
}

四、用数组实现队列

#include <stdio.h>
#include <string.h>
#define MaxSize 50

typedef struct{
    int data[MaxSize];
    int head,rear;
}queue;

void InitQueue(queue &q){
    memset(q.data,0,sizeof(q.data));
    q.head = q.rear = 0;
}

bool IsEmpty(queue q){
    if(q.rear == q.head)
        return 1;
    return 0;
}

bool IsFull(queue q){
    if((q.rear + 1) % MaxSize == q.head)
        return 1;
    return 0;
}

bool EnPush(queue &q,int x){
    if(IsFull(q)) return 0;
    q.data[q.rear] = x;             // 这里为了区分队列是否满/空，我们牺牲了一个存储单元，使rear永远指向最后一个数据的下一位置，这也是不用++q.rear的原因,小坑...
    q.rear = (q.rear+1) % MaxSize;
    return 1;
}

bool DePop(queue &q,int &x){
    if(IsEmpty(q)) return 0;
    x = q.data[q.head];             // head 一直指向最开始的数据单元
    q.head = (q.head + 1) % MaxSize;
    return 1;
}

int main(){
    queue qe;
    InitQueue(qe);
    for(int i = 0;i<=70;i++){
        if(!EnPush(qe,i))
            printf("%d -- ",i);
            puts("Full Queue!!!");
    }
    
    int ans;
    for(int i=0;i<=70;i++){
        if(DePop(qe,ans)){
            printf("%d\n",ans);
        }
        else{
            printf("%d -- ",i);
            puts("Empty Queue!!!");
        }
    }

    return 0;
}

五、用单链表实现队列

#include <stdio.h>
#include <malloc.h>
typedef struct _QNode{
    int data;
    struct _QNode * next;    
}QNode,*pQNode;

typedef struct _LinkQueue{
    QNode* rear;
    QNode* front;
}LinkQueue,*pLinkQueue;

void InitQueue(pLinkQueue &Q){  // 初始化队列，创建头节点，使队头指向头节点，队尾指向头节点//
    Q = (LinkQueue *)malloc(sizeof(LinkQueue));
    QNode *q = (QNode *)malloc(sizeof(QNode));
    q->next = NULL;
    Q->rear = Q->front = q;
}

bool IsEmpty(pLinkQueue Q){
    if(Q->front == Q->rear) return 1;
    return 0;
}

bool EnPush(pLinkQueue &Q,int x){
    QNode *q = (QNode *)malloc(sizeof(QNode));
    q->next = NULL;
    q->data = x;
    Q->rear->next = q;
    Q->rear = q;
    return 1;
}


bool DePop(pLinkQueue &Q,int &x){
    if(IsEmpty(Q)) return 0;
    QNode *q = Q->front->next;              //要注意这里和前面用双向链表实现栈的时候不太一样，当时S->rear指的是最后一个节点，而这里的S->front指的是头节点，而不是第一个节点，我们需要用S->front->next来获得第一个节点，切记切记!!!
    x = q->data;
    Q->front->next = q->next;

    if(Q->rear == q)                //当原队列中只有一个节点时，删除后，让尾指针重新指向头结点!!//
        Q->rear = Q->front;        
    free(q);
    return 1; 
}

int main(){         
    pLinkQueue qe;
    InitQueue(qe);
    EnPush(qe,1);
    EnPush(qe,2);
    EnPush(qe,3);
    EnPush(qe,4);
    EnPush(qe,5);
    int ans;
    for(int i=0;i<=7;i++){
        if(DePop(qe,ans)){
            printf("%d\n",ans);
        }
        else{
            puts("Empty Queue!!!");
        }
    }
    return 0;    
}

 

 

标签：王道,return,int,next,链表,bool,data,rear,408
From： https://www.cnblogs.com/lordtianqiyi/p/17608415.html

相关文章

  • LeetCode 206 反转链表,LeetCode 92反转链表Ⅱ
    反转链表给你单链表的头节点head，请你反转链表，并返回反转后的链表。示例1：输入：head=[1,2,3,4,5]输出：[5,4,3,2,1]示例2：输入：head=[1,2]输出：[2,1]示例3：输入：head=[]输出：[]提示：链表中节点的数目范围是[0,5000]-5000<=Node.val<=5000写法一：不使用头节点，......
  • 算法：深挖合并 K 个有序链表
    本人刷题时思考的几个解法，欢迎交流力扣链接：合并2个有序链表力扣链接：合并K个有序链表目录合并2个有序链表合并k个有序链表K个中minNode排序队列取minNode队头手动实现的排序队列优先级队列分治合并2个有序链表合并2个有序链表操作模型：for->cur=min(list1......
  • GO:用链表实现栈的操作
         ......
  • 反转链表系列图解
    1.反转链表给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。图解代码实现publicListNodeReverseList(ListNodehead){ListNodecur=head;ListNodepre=null;ListNodenext=null;......
  • 【数据结构 | 入门】线性表与链表 （问题引入&实现&算法优化）
    ......
  • 【剑指Offer】16、合并两个排序的链表
    【剑指Offer】16、合并两个排序的链表题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。解题思路：首先需要判断几个特殊情况，即判断输入的两个指针是否为空。如果第一个链表为空，则直接返回第二个链表；如果第二个链表为空，则直接......
  • C习题-链表02
    1、设数据结构 B=(D, R) ，其中D={ a, b, c, d, e, f }、 R={ (a,b ） , (b, c ） , (c, d ） , (d, e), (e, f), (f,a） }，该数据结构为（ ）。A、非线性结构B、循环队列C、循环链表D、线性结构答案：A;图是非线性结构;线性结构：一对一，除第一个与最后一......
  • c语言链表demo
    #include<stdio.h>#include<stdlib.h>//定义节点结构体structnode{intdata;structnode*next;/*注意：这行使用了node,node必须在这行之前定义*/};intmain(intargc,constchar*argv[]){//1.定义链表的头节点,并初始化structno......
  • C习题-链表01
    1、用邻接表表示图进行深度优先遍历时,通常是采用（）来实现算法的。A.栈B.队列C.树D.图答案：A；深度优先遍历(DFS)：从某个顶点出发，一直往下一个顶点遍历，直到没有下一个顶点为止，再返回上一个顶点的其他路径继续进行深度优先，直到该出发顶点的所有深度优先遍历结......
  • 什么时候该用数组型容器、什么时候该用链表型容器？
    选择数组型容器还是链表型容器取决于特定的使用场景和需求。以下是一些指导原则：使用数组型容器的情况：快速随机访问：数组在具有固定大小的情况下，可以通过索引进行快速随机访问，时间复杂度为O(1)。这是因为数组的元素在内存中是连续存储的。内存连续性：数组在内存中是连续存储......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99