数据结构(栈与列队)

简介: 数据结构(栈与列队)

概念与结构

1. 栈⼀种特殊的线性表,其只允许在固定的⼀端进行插入和删除元素操作。

2. 进行数据插入和删除操作的⼀端称为栈顶,另⼀端称为栈底。

3. 栈中的数据元素遵守后进先出的原则。

4. 栈的插入操作叫做进栈,栈的删除操作叫做出栈。

5. 栈的实现⼀般可以使用数组或者链表实现。

6. 相对而言,使用数组结构实现更优⼀些。因为数组结构更简单,而且能够胜任所有功能。

7. 栈不能遍历,也不找到中间和下面的数据,只能找到最上面的数据,是阉割版的线性表。

07170f9e5eb66e8e78dcc529b9762f4c_b9a95223966347d89e902a85a5f45c80.png

1. 想象一下玩具枪的弹夹,我们给弹夹上子弹的时候,先上的子弹被压在弹夹的最下面,后装的子弹在最上面,打枪的时候后装的子弹最先被打出。


2. 这个弹夹其实就是一种栈的数据结构。我们一般把先进后出,后进先出的这种数据结构称之为栈。


3. 从栈的操作特性上看栈这是一种"操作受限的线性表",它只支持在一端插入和删除数据。

分步实现栈的功能

创建栈的结构体

typedef int STDataType;
typedef struct Stack
{
  STDataType* arr;//创建动态数组(指针)
  int capacity;//栈的空间大小
  int top;//栈顶,是栈中最后一个数据的下一位
}Stack;

初始化栈

void InitStack(Stack* ps)
{
  assert(ps);
    //Stack* ps=&stack;本质上是判断:调用函数时候有没有传参数,如果没有那么ps指向任意值,就有可能是NULL。
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}

进栈

void StackPush(Stack* ps, int x)
{
  //判断空间是否足够
  if (ps->capacity == ps->top )
  {
    int Newcapacity = ps->capacity == 0 ? 4: 2 * ps->capacity;
        //在原有的空间基础上继续开辟空间,需要使用realloc()。
    STDataType* tmp = (STDataType*)realloc(ps->arr, Newcapacity * sizeof(STDataType));
    //判断空间开辟是否成功
        if (tmp == NULL)
    {
      perror("realloc fail");
      exit(1);
    }
    else
    {
      ps->arr = tmp;
      ps->capacity = Newcapacity;
    }
  }
    ps->arr[ps->top++] = x;//指针当作动态数组使用
}

出栈

void StackPop(Stack* ps)
{
  assert(ps);
  assert(ps->top!=0);//当栈中没有元素时候,就不能出栈了。
  ps->top--;
}

查找栈首元素

STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(ps->top != 0);
  return ps->arr[ps->top - 1];//top指向最后一个元素的下一位
}

销毁栈

void DestroyStack(Stack* ps)
{
  assert(ps);
  if (ps->arr)
    {
    free(ps->arr);//释放动态数组空间
    }
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}

实现栈的代码

<stack.h> 文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* arr;//创建动态数组(指针)
  int capacity;//栈的空间大小
  int top;//栈顶
}Stack;
//初始化
void InitStack(Stack* ps);
void DestroyStack(Stack* ps);
void StackPush(Stack* ps, STDataType x);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);

<stack.c>文件

#include "stack.h"
void InitStack(Stack* ps)
{
  assert(ps);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
void DestroyStack(Stack* ps)
{
  assert(ps);
  if (ps->arr)
    free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, int x)
{
  //判断空间是否足够
  if (ps->capacity == ps->top )
  {
    int Newcapacity = ps->capacity == 0 ? 4: 2 * ps->capacity;
    STDataType* tmp = (STDataType*)realloc(ps->arr, Newcapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(1);
    }
    else
    {
      ps->arr = tmp;
      ps->capacity = Newcapacity;
    }
  }
    ps->arr[ps->top++] = x;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(ps->top!=0);
  ps->top--;
}
STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(ps->top != 0);
  return ps->arr[ps->top - 1];//top指向最后一个元素的下一位
}

<test.c>文件

#include "stack.h"
int main()//栈里面的数据不能被遍历,也不能被随机访问。
{
  Stack stack1;
  InitStack(&stack1);
  //DestroyStack(&stack1);
  StackPush(&stack1, 1);
  StackPush(&stack1, 2);
  StackPush(&stack1, 3);
  StackPush(&stack1, 4);
  StackPush(&stack1, 5);
  StackPush(&stack1, 6);
  while (stack1.top != 0)
  {
    int data=StackTop(&stack1);
    printf("%d\n", data);
    StackPop(&stack1);
  }
  DestroyStack(&stack1);
  return 0;
}

队列

概念与结构

1. 只允许在⼀端进行插入数据操作,在另⼀端进行删除数据操作的特殊线性表。


2. 队列具有先进先出的原则。


3. 队列也可以用数组和链表的结构实现。


4. 使用链表的结构实现更优⼀些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。


5. 在数组实现的列队中,出队操作通常需要将队首元素移除。如果队首元素被移除后,队列中的其他元素需要向前移动一位以填补空缺。这个过程的时间复杂度是 O(n),其中 n 是队列中元素的数量。


分步实现列队的功能

创建列队结构体

typedef int DataType;
typedef struct QueueNode  //列队节点结构体
{
  DataType data;
  struct QueueNode* next;
}QueueNode;
typedef struct Queue  //列队结构体
{
  QueueNode* phead;
  QueueNode* ptail;
  int size;
}Queue;

初始化列队

void InitQueue(Queue* ps)
{
  assert(ps);
  ps->phead = ps->ptail = NULL;
  ps->size = 0;
}

入队

void AddQueue(Queue* ps, DataType x)
{
  assert(ps);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(DataType));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    ps->phead = ps->ptail = newnode;
  }
  else
  {
    ps->ptail->next = newnode;
    ps->ptail = newnode;
  }
  ps->size++;
}

出队

void PopQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  if (ps->phead == ps->ptail)
  {
    free(ps->phead);//列队只有一个节点时
    ps->phead = ps->ptail = NULL;
  }
  else
  {
    QueueNode* next = ps->phead->next;
    free(ps->phead);
    ps->phead = next;
  }
  ps->size--;
}

查找队头

DataType TakeFrontQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  return ps->phead->data;
}

查找对尾

DataType TakeBackQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  return ps->ptail->data;
}

查找队伍长度

int QueueSize(Queue* ps)
{
  return ps->size;
}

销毁队列

void DestroyQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  QueueNode* pcur = ps->phead;
  while (pcur)
  {
    QueueNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  ps->phead = ps->ptail = NULL;
  ps->size = 0;
}

实现列队的代码

<queue.h>文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int DataType;
typedef struct QueueNode
{
  DataType data;
  struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
  QueueNode* phead;
  QueueNode* ptail;
  int size;
}Queue;
void InitQueue(Queue* ps);
void AddQueue(Queue* ps, DataType x);
void PopQueue(Queue* ps);
DataType TakeFrontQueue(Queue* ps);
DataType TakeBackQueue(Queue* ps);
int QueueSize(Queue* ps);
void DestroyQueue(Queue* ps);

<queue.c>文件

#include "queue.h"
void InitQueue(Queue* ps)
{
  assert(ps);
  ps->phead = ps->ptail = NULL;
  ps->size = 0;
}
void AddQueue(Queue* ps, DataType x)
{
  assert(ps);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(DataType));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    ps->phead = ps->ptail = newnode;
  }
  else
  {
    ps->ptail->next = newnode;
    ps->ptail = newnode;
  }
  ps->size++;
}
void PopQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  if (ps->phead == ps->ptail)
  {
    free(ps->phead);//列队只有一个节点时
    ps->phead = ps->ptail = NULL;
  }
  else
  {
    QueueNode* next = ps->phead->next;
    free(ps->phead);
    ps->phead = next;
  }
  ps->size--;
}
DataType TakeFrontQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  return ps->phead->data;
}
DataType TakeBackQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  return ps->ptail->data;
}
int QueueSize(Queue* ps)
{
  return ps->size;
}
void DestroyQueue(Queue* ps)
{
  assert(ps);
  if ((ps->phead == NULL) && (ps->ptail == NULL))
  {
    exit(1);//要求列队不能为空
  }
  QueueNode* pcur = ps->phead;
  while (pcur)
  {
    QueueNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  ps->phead = ps->ptail = NULL;
  ps->size = 0;
}

<test.c> 文件

#include "queue.h"
int main()
{
  Queue q;
  InitQueue(&q); 
  AddQueue(&q, 1);
  AddQueue(&q, 2);
  AddQueue(&q, 3);
  AddQueue(&q, 4);
  AddQueue(&q, 5);
  printf("%d\n", TakeFrontQueue(&q));
  PopQueue(&q);
  printf("%d\n", TakeFrontQueue(&q));
  printf("%d\n", TakeBackQueue(&q));
  printf("%d\n", QueueSize(&q));
  DestroyQueue(&q);
  //PopQueue(&q);
  //PopQueue(&q);
  //PopQueue(&q);
  return 0;
}

致谢

 感谢您花时间阅读这篇文章!如果您对本文有任何疑问、建议或是想要分享您的看法,请不要犹豫,在评论区留下您的宝贵意见。每一次互动都是我前进的动力,您的支持是我最大的鼓励。期待与您的交流,让我们共同成长,探索技术世界的无限可能!

相关文章
|
25天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
115 9
|
16天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
22 1
|
3天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
21 5
|
18天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
21天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
23天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
47 4
|
27天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
72 1
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
17 0
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
33 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器