【数据结构】栈和队列的模拟实现(两个方式实现)

简介: 【数据结构】栈和队列的模拟实现(两个方式实现)

学习目标:

      这一篇博客将学习栈和队列的相关知识,队列是两种基础的数据结构,在现在一定要打好基础,在之后的学习生涯中,也常常遇见,例如:深度优先搜索(DFS)广度优先搜索(BFS)……今天要学习栈和队列的模拟实现:数组模拟实现栈,用单链表模拟实现队列,用数组模拟实现队列。


学习内容:

通过上面的学习目标,我们可以列出要学习的内容:

  1. 用数组模拟实现栈
  2. 用数组模拟实现队列
  3. 用单链表模拟实现队列

一、栈的相关知识

1.1 栈的概念及结构

下面先来一段大白话,在介绍栈的文章中都会出现的。

      栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作(类似于尾插尾删)。我们先来介绍两个概念——栈顶与栈底:进行数据插入和删除操作的一端为栈顶,而另一端为栈底。高大上一点的叫法是:栈中的元素遵守后进先出LIFO(Last In First Out)的原则。

下面,我们在来介绍两个操作——圧栈与入栈:

  • 压栈:栈的插入操作是进栈/压栈/入栈,入数据在栈顶;
  • 出栈:栈的删除操作是出栈,出数据在栈顶。

1.2 栈的实现

      现在,我们学习了两个数据结构:顺序表与链表,到底用哪个数据结构实现栈比较好呢?在这里我们选用数组来模拟实现栈。

为什么我们要用数组模拟实现栈会更好一些?

      栈的两个操作无疑就是尾插与尾删,这两个操作在数组中都比较容易实现(相对于链表),而且数组存储的数据内容比较集中,CPU高速缓存命中率高,尽可能小地不污染缓存区,所以用数组模拟实现比较好一些。

      在现实生活中,我们一般要实现能够进行动态增长的栈,而不是静态的栈(比较死板,在实际应用中不常见)。虽然,静态的栈在实际生活中不常见,但是在算法题目中还是可以进行使用,而且在算法题中,我们不用考虑内存泄漏问题hh。下面来实现吧!

代码一:实现动态的栈

第一步,我们先来定义要使用的头文件:

#include <stdio.h>  //必须要包含的头文件
#include <assert.h> //要使用assert进行断言,防止出现一下不好的情况发生
#include <stdbool.h> //在C语言中,没有提供bool变量
#include <stdlib.h>  //使用一些申请内存空间的函数

第二步,我们要让主角登场,构造栈的结构体:

typedef int StDatatype; // 为了方便以后更改数组中的数据类型
typedef struct stack {
  StDatatype* a;  // 一个动态空间
  int top;   // 表示栈的栈顶
  int capacity; // 表示栈现在有多少空间
}ST;

第三步,我们要定义一些我们要实现栈功能的一些函数:栈的初始化(定义一个结构,一定要初始化成员变量)、栈的销毁、栈的插入操作、栈的删除操作、查看栈的栈顶元素、查看栈的大小、查看栈是否为空

//栈的初始化
void stackinit(ST* stk);
//栈的插入操作
void stackpush(ST* stk, StDatatype x);
//栈的删除操作
void stackpop(ST* stk);
//返回栈的栈顶元素
StDatatype stacktop(ST* stk);
//判断栈是否为空
bool stackempty(ST* stk);
//返回栈的大小
int stacksize(ST* stk);
//销毁栈
void stackdestroy(ST* stk);

栈的初始化操作:

void stackinit(ST* stk)
{
  assert(stk); //防止传空指针
  //有两个方式进行初始化
  //法1
  stk->a = NULL;
  stk->capacity = 0;
  stk->top = 0; //如果这里指向0,top表示的是栈的大小
}
 
//法2
void stackinit(ST* stk)
{
    assert(stk);
    stk->a = NULL;
    stk->capacity = 0;
    stk->top = -1; //如果这里指向-1,top表示的是栈顶元素的下标
}

栈的销毁操作:

void stackdestroy(ST* stk)
{
  assert(stk);
 
  free(stk->a);
  stk->a = NULL; // 别忘记置空,防止野指针出现
    free(stk);
    stk = NULL;
}
// 因为栈所使用的是数组,所以直接销毁即可

栈的插入操作:

void stackpush(ST* stk, StDatatype x)
{
  assert(stk);
  //因为我们在这里的栈的空间是没有创建的
  if (stk->capacity == stk->top) 
  {
    int newcapacity = stk->capacity == 0 ? 4 : stk->capacity * 2;
    StDatatype* tmp = (StDatatype*)realloc(stk->a, newcapacity * sizeof(StDatatype));
    if (tmp == NULL) {
      perror(tmp);
      return;
    }
    stk->a = tmp;
    stk->capacity = newcapacity;
  }
//插入操作相当于尾插
  stk->a[stk->top] = x;
  stk->top++;  // 别忘了栈顶要加1
}

栈的删除操作:

void stackpop(ST* stk)
{
  assert(stk);
  assert(stk->top > 0);
  stk->top--;
}

返回栈的栈顶元素:

StDatatype stacktop(ST* stk)
{
  assert(stk);
  assert(stk->top > 0);
 
  return stk->a[stk->top - 1]; // top == 0
    //return stk->a[stk->top];  // top == -1
}

判断栈是否为空:

bool stackempty(ST* stk)
{
// 第一种写法:
  assert(stk);
  if (stk->top == 0)
  {
    return true;
  }
  return false;
// 第二种写法:
  //return stk->top == 0;
}

返回栈的大小:

int stacksize(ST* stk)
{
  assert(stk);
  return stk->top;  // top == 0
    //return stk->top + 1; // top == -1
}

代码二:实现静态的栈

struct my_stack
{
    int a[10];
    int size;
    int capacity;
}

二、队列的相关知识

2.1 队列的概念及结构

      队列在日常生活中无处不在,排队就是一种典型的队列。对此,我们大致可以得知:队列是只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的性质。和栈一样,队列具有两个基本操作——入队和出队:

入队:进行插入操作的一端称为队尾;

出队:进行删除操作的一端称为队头。

2.2 队列的实现

      与实现栈类似,我们先来讨论一下使用哪种数据结构方便一些?是使用顺序表呢,还是使用链表呢?是使用单链表呢还是使用双向链表?

      分析一下队列的插入和删除操作,发现插入操作是尾插,而删除操作是头删。在实现顺序表和链表时,对于头删操作来说,链表更为简单,而顺序表需要进行移动数据,效率较低。因此,我们使用链表来实现操作。

代码一:链表实现队列

第一步,我们还是先将头文件加上:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

第二步,我们来建立一下队列的数据结构:

typedef int QueDatatype;
 
typedef struct queue {
  QueDatatype x;
  struct queue* next;
}Queue;
 
//由于要用二级指针,并且我们还有多个成员,
//然后就用结构体
 
typedef struct Qnode {
  Queue* phead;
  Queue* ptail;  // 存储链表的尾结点,方便于尾插
  int size;
}Qnode;

第三步,我们来定义一下队列的功能:队列的初始化,队列的销毁,队列的插入操作,队列的删除操作,返回队列的队头元素,返回队列的大小,检查队列是否为空。

//队列初始化
void queueinit(Qnode* qnd);
//队列销毁
void queuedestroy(Qnode* qnd);
//队列的插入操作
void queuepush(Qnode* qnd, QueDatatype x);
//队列的删除操作
void queuepop(Qnode* qnd);
//队列的对头元素
QueDatatype queuefront(Qnode* qnd);
//队列的大小
int queuesize(Qnode* qnd);
//检查队列是否为空
bool quueueempty(Qnode* qnd);

队列的初始化操作:

void queueinit(Qnode* qnd)
{
  assert(qnd);
 
  qnd->phead = qnd->ptail = NULL;
  qnd->size = 0;
}

队列的销毁操作:

void queuedestroy(Qnode* qnd)
{
  assert(qnd);
 
  //销毁是要从头到尾进行销毁的
  Queue* cur = qnd->phead;
  while (cur)
  {
    Queue* del = cur->next;
    free(cur);
    cur = del;
  }
// 只有一个结点的情况,会出现一个野指针
  qnd->phead = qnd->ptail = NULL;
  qnd->size = 0;
}

队列的插入操作:

void queuepush(Qnode* qnd, QueDatatype x)
{
  assert(qnd);
  //创建好了结构体,然后进行操作
  Queue* tmp = (Queue*)malloc(sizeof(Queue));
  //防止创建失败
  if (tmp == NULL)
  {
    perror(tmp);
    return;
  }
  tmp->x = x;
  tmp->next = NULL;
  //将这个新结点链接到链表中
  if (qnd->phead == NULL)
  {
    qnd->phead = qnd->ptail = tmp;
  }
  else 
  {
    qnd->ptail->next = tmp;
    qnd->ptail = tmp;
  }
  qnd->size++;
}

队列的删除操作:

void queuepop(Qnode* qnd)
{
  assert(qnd);
  //头结点不能为空
  assert(qnd->phead);
  //其次,在只有一个结点的过程中,会出现野指针
  Queue* del = qnd->phead;
  qnd->phead = del->next;
  free(del);
  del = NULL;
 
  if (qnd->phead == NULL)
  {
    qnd->ptail = NULL;
  }
 
  qnd->size--;
}

返回队列的队头元素:

QueDatatype queuefront(Qnode* qnd)
{
  assert(qnd);
  //不能队列为空
  assert(qnd->phead);
  return qnd->phead->x;
}

返回队列的大小:

int queuesize(Qnode* qnd)
{
  assert(qnd);
  return qnd->size;
}

检查队列是否为空:

bool quueueempty(Qnode* qnd)
{
  assert(qnd);
  //if (qnd->phead ==NULL)
  //{
  //  return true;
  //}
  //return false;
 
  return qnd->phead == NULL;
}

代码二:数组实现队列

int q[N], hh, tt = -1;

学习产出:

  1. 用数组模拟实现栈
  2. 用数组模拟实现队列
  3. 用单链表模拟实现队列
相关文章
|
16天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
12天前
|
API
用栈翻转字符串
用栈翻转字符串
14 0
|
12天前
|
JavaScript
数据结构(用 JS 实现栈和队列【三种方式】)
数据结构(用 JS 实现栈和队列【三种方式】)
16 0
|
15天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
16天前
|
算法
数据结构与算法:栈与队列
数据结构与算法:栈与队列
|
19天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
16 0
|
20天前
|
存储 人工智能 程序员
技术心得记录:堆(heap)与栈(stack)的区别
技术心得记录:堆(heap)与栈(stack)的区别
13 0
|
22天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
9 0
|
22天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
22天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
27 5