【C/数据结构和算法】:栈和队列

简介: 【C/数据结构和算法】:栈和队列

1. 栈

1.1 栈的概念及结构

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶

出栈:栈的删除操作叫做出栈。出数据也在栈顶

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾插和头删的实际复杂度为O(1),是非常合适的。

1.3 栈的功能

  • 初始化栈
  • 销毁栈
  • 入栈
  • 出栈
  • 获取栈顶元素
  • 获取栈内有效元素的个数
  • 判断栈内是否为空,如果为空返回非0结果,不为空返回0

1.4 栈的功能的实现

(1)定义一个动态增长的栈

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  STDataType top;//定义栈顶
  size_t capacity;//栈的容量
}ST;

(2)初始化栈

void StackInit(ST* ps)
{
  //初始化空间
   ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->a == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  ps->top = 0;//top指向的是栈顶元素的下一个
  ps->capacity = 4;//初始化4个空间
}

(3)销毁栈

void StackDestory(ST* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

(4)入栈(相当于顺序表的尾插)

void StackPush(ST* ps, STDataType x)
{
  //插入数据之前判断是否增容
  if (ps->top == ps->capacity)
  {
    STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2);
    if (tmp == NULL)
    {
      printf("realloc fail!\n");
      return;
    }
    else
    {
      ps->a = tmp;
      ps->capacity *= 2;
    }
  }
   
   //注意由于我们定义top=0,这两条语句的顺序不能调换
  ps->a[ps->top] = x;
  ps->top++;
}

(5)出栈(相当于顺序表的头删)

void StackPop(ST* ps)
{
  assert(ps);//断言
    assert(ps->top>0);//栈空了,就要停止删除
    
  ps->top--;
}

(6)获取栈顶元素

STDataType StackTop(ST* ps)
{
  assert(ps);//断言
  assert(ps->top > 0);//栈为空时,防止越界
  return ps->a[ps->top - 1];
}

(7)获取栈内有效元素的个数

int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

(8)判断栈内是否为空,如果为空返回非0结果,不为空返回0

bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}

1.5 完整代码

Stack.h

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  STDataType top;//定义栈顶
  size_t capacity;//栈的容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//从栈顶插入数据
void StackPush(ST* ps, STDataType x);
//从栈顶删除数据
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);
//获取栈内有效元素个数
int StackSize(ST* ps);
//判断栈内是否为空,如果为空返回非0结果,不为空返回0
bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Stack.h"
void StackInit(ST* ps)
{
  //初始化空间
   ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->a == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  ps->top = 0;//top指向的是栈顶元素的下一个
  ps->capacity = 4;//初始化4个空间
}
void StackPush(ST* ps, STDataType x)
{
  //插入数据之前判断是否增容
  if (ps->top == ps->capacity)
  {
    STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2);
    if (tmp == NULL)
    {
      printf("realloc fail!\n");
      return;
    }
    else
    {
      ps->a = tmp;
      ps->capacity *= 2;
    }
  }
  
    //注意由于我们定义top=0,这两条语句的顺序不能调换
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);//断言
    assert(ps->top>0);//栈空了,就要停止删除
  ps->top--;
}
STDataType StackTop(ST* ps)
{
  assert(ps);//断言
  assert(ps->top > 0);//栈为空时,防止越界
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackDestory(ST* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Stack.h"
void StackTest()
{
  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);
  }
  StackDestory(&st);
}
int main()
{
  StackTest();
  return 0;
}

2. 队列

2.1 队列的概念及结构

队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出

FIFO(First In First Out)

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

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

2.2 队列的实现

队列也可以数组和链表的结构实现,使用单链表的结构实现更优一些。

因为如果使用数组的结构,出队列在数组头上出数据,这时需要挪动数据,时间复杂度为O(n),效率会比较低。

而单链表的尾插和头删的时间复杂度为O(1),十分合适。

2.3 队列的功能

  • 初始化队列
  • 销毁队列
  • 入队列
  • 出队列
  • 获取队列头部元素
  • 获取队列尾部元素
  • 获取队列中有效元素的个数
  • 判断队列是否为空,为空返回非0,不为空返回0

2.4 队列的功能的实现

(1)定义一个队列

typedef int QTDataType;
typedef struct QNode
{
  struct QNode* next;
  QTDataType data;
}QNode;
typedef struct Queue
{
  struct QNode* tail;
  struct QNode* head;
}Queue;

(2)初始化队列

void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}

(3)销毁队列

void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
      QNode* next = cur-> next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}

(4)入队列(相当于单链表的尾插)

void QueuePush(Queue* pq, QTDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //没有一个结点
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  //多个节点
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}

(5)出队列(相当于单链表的头删)

void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  //只有一个节点时,防止tail成为野指针
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    //保存下一个节点的地址
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}

(6)获取队列头部元素

QTDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  return pq->head->data;
}

(7)获取队列尾部元素

QTDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->data;
}

(8)获取队列中有效元素的个数

int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}

(9)判断队列是否为空,为空返回非0,不为空返回0

int QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

2.5 完整代码

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QTDataType;
typedef struct QNode
{
  struct QNode* next;
  QTDataType data;
}QNode;
typedef struct Queue
{
  struct QNode* tail;
  struct QNode* head;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QTDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部元素
QTDataType QueueFront(Queue* pq);
//获取队列尾部元素
QTDataType QueueBack(Queue* pq);
//判断队列是否为空,为空返回非0,不为空返回0
int QueueEmpty(Queue* pq);
//获取队列中有效元素的个数
int QueueSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QTDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //没有一个结点
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  //多个节点
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  //只有一个节点时,防止tail成为野指针
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    //保存下一个节点的地址
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}
int QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
QTDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  return pq->head->data;
}
QTDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
      QNode* next = cur-> next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Queue.h"
void QueueTest()
{
  Queue q;
  QueueInit(&q);
  
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  
    //打印队列内的数据,由于不能破坏队列先进先出的特性,
    //所以不能直接遍历,需要出一个删一个
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  QueueDestory(&q);
}
int main()
{
  QueueTest();
  return 0;
}
目录
相关文章
|
21小时前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
8 1
|
3天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
8 0
|
3天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
7 0
|
5天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
10 0
|
6天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
7天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
13 1
【数据结构】算法的复杂度
|
8天前
|
API
用栈翻转字符串
用栈翻转字符串
13 0
|
2天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
8天前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点,算法规划路径并显示长度。测试显示,尽管在某些复杂情况下计算路径可能与实际有偏差,但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论,不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好,但在交通拥堵等特殊情况下需结合其他数据提升准确性。
|
8天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。