栈和队列的实现

2022-10-23
吉林
本文字数：2415 字
阅读完需：约 8 分钟

一、栈

1.概念

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵循后进先出的原则。注意从栈顶入，栈顶出

二、栈的实现(顺序表)

1.函数的定义和结构体的创建——stack.h

#pragma once#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedef int datatype;typedef struct stack{  datatype* a;  int top;  int capacity;}ST;void stackinit(ST* p);void stackpush(ST* p, datatype x);int stacktop(ST* p);void stackpop(ST* p);int stacksize(ST* p);bool stackempty(ST* p);void stackdestroy(ST* p);

复制代码

2.函数的调用——test.c

#include"stack.h"int main(){  ST st;  stackinit(&st);  stackpush(&st, 1);  stackpush(&st, 2);  stackpush(&st, 3);  stackpush(&st, 4);  while (!stackempty(&st))//判断是否为空  {    printf("%d ", stacktop(&st));//出栈    stackpop(&st);//移除栈顶元素  }  stackdestroy(&st);//内存销毁  return 0;}

复制代码

3.栈的接口

1.初始化

void stackinit(ST* p)//栈的初始化{  assert(p);  p->a = NULL;  p->top = 0;  p->capacity = 0;}

复制代码

2.入栈

void stackpush(ST* p, datatype x)//入栈{  assert(p);  if (p->top == p->capacity)//扩容  {    int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;    datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity);    if (tmp != NULL)    {      p->a = tmp;      p->capacity = newcapacity;//扩容成原来的2倍    }  }  p->a[p->top] = x;  p->top++;}

复制代码

3.移除栈顶元素

void stackpop(ST* p)//移除栈顶元素{  assert(p);  assert(p->top > 0);  p->top--;}

复制代码

4.出栈

int  stacktop(ST* p)//出栈{  assert(p);  assert(p->top > 0);  return p->a[p->top - 1];//top从0开始，每次入栈top都向后移，所以top-1是实际储存的元素}

复制代码

5.判断为空

bool  stackempty(ST* p)//是否为空{  return p->top == 0;//当栈中没有数据时，则为空，为真， 否则为假。}

复制代码

6.栈中元素个数

int stacksize(ST* p)//栈中元素个数{  assert(p);  return p->top;//虽然top是指向下一个，但是top从0开始，top正好是元素个数}

复制代码

7.内存销毁

void stackdestroy(ST* p)//内存销毁{  assert(p);  free(p->a);//销毁动态开辟数组  p->a = NULL;  p->top = 0;  p->capacity = 0;}

复制代码

三、队列

1.概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的原则。入队列：进行插入操作的一段称为队尾出队列：进行删除操作的一端称为对头注意：对尾入，对头出

四、队列的实现(链表)

1.函数的定义和结构体的创建——queue.h

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedef int datatype;typedef struct queuenode{  datatype data;  struct queuenode* next;}queuenode;typedef struct queue{  queuenode * head;  queuenode * tail;}queue;void queueinit(queue*p);void queuedestroy(queue* p);void queuepush(queue* p,datatype x);void queuepop(queue* p);datatype queuefront(queue* p);datatype queueback(queue* p);int queuesize(queue* p);bool queueempty(queue* p);

复制代码

2.函数的调用——test.c

#include"queue.h"int main(){  queue p;  queueinit(&p);  queuepush(&p, 1);  queuepush(&p, 2);  queuepush(&p, 3);  queuepush(&p, 4);  while (!queueempty(&p))//判断为空  {    datatype front = queuefront(&p);    printf("%d ", front);    queuepop(&p);  }  queuedestroy(&p);//内存销毁  return 0;}

复制代码

3.取一级指针的原因

正常来说，如果将 head 与 tail 放在 queuenode 内部，应该取二级指针，但是由于此时定义的是结构体为 queue 的变量，改变的是该变量的内部。所以只取一级指针就可以。

4.队列的接口的实现

1.初始化

void queueinit(queue* p)//初始化队列{  assert(p);  p->head = NULL;  p->tail = NULL;}

复制代码

2.入队列

void queuepush(queue* p,datatype x)//入队列 (队尾入){  assert(p);  queuenode* newnode = (queuenode*)malloc(sizeof(queuenode));  newnode->data = x;  newnode->next = NULL;  if (p->tail == NULL)  {    p->tail = newnode;    p->head = newnode;  }  else  {    p->tail->next = newnode;    p->tail = newnode;  }}

复制代码

3.删除数据

void queuepop(queue* p)//删除数据{  assert(p);  assert(!queueempty(p));//断言队列是否为空  queuenode* next = p->head->next;  free(p->head);  p->head = next;  if (p->head == NULL)//当删除只剩下最后一个节点时 head与tail都指向，free(head) ,tail就变成了野指针  {    p->tail = NULL;  }}

复制代码

4.取对头数据

datatype queuefront(queue* p)//取队头数据{  assert(p->head);  assert(!queueempty(p));  return p->head->data;}

复制代码

5.取队尾数据

datatype queueback(queue* p)//取队尾数据{  assert(p->head);  assert(!queueempty(p));  return p->tail->data;}

复制代码

6.取队的元素个数

int queuesize(queue* p)//队的数量{  assert(p);  int sum = 0;  queuenode* cur = p->head;  while (cur != NULL)  {    sum++;    cur= cur->next;  }  return sum;}

复制代码

7.判断为空

bool queueempty(queue* p)//判断队列是否为空{  assert(p);  return p->head == NULL;}

复制代码

8.内存销毁

void queuedestroy(queue* p)//内存销毁{  assert(p);  queuenode* cur = p->head;  while (cur != NULL)  {    queuenode* next = cur->next;    free(cur);    cur = next;  }  p->head = NULL;  p->tail = NULL;}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/6eb654b4e51b5d1eaf1f76da4】。文章转载请联系作者。

lovevivi

关注

还未添加个人签名 2022-10-12 加入

还未添加个人简介

发布

暂无评论

创作场景

栈和队列的实现

一、栈

1.概念

二 、栈的实现(顺序表)

1.函数的定义和结构体的创建——stack.h

2.函数的调用——test.c

3.栈的接口

1.初始化

2.入栈

3.移除栈顶元素

4.出栈

5.判断为空

6.栈中元素个数

7.内存销毁

三、队列

1.概念

四、队列的实现(链表)

1.函数的定义和结构体的创建——queue.h

2.函数的调用——test.c

3.取一级指针的原因

4.队列的接口的实现

1.初始化

2.入队列

3.删除数据

4.取对头数据

5.取队尾数据

6.取队的元素个数

7.判断为空

8.内存销毁

lovevivi

评论

二、栈的实现(顺序表)