AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】栈和队列--＞理解和实现（赋源码)

2024-08-08 21
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】栈和队列--＞理解和实现（赋源码)

前言

  1. 栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先被移除。
  2. 队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（FIFO），即最先进入的元素最先被移除。

栈和队列有各自的特点，严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。

一、栈和队列的理解

对于栈的理解：

栈如同这个图一样，要是想拿出数据，必须从上面一个一个往下面拿。这也正是 LIFO 的体现。

对于队列的理解：

队列如同这个图一样，要是想拿出数据，必须前面一个一个往向后面拿。这也正是 FIFO 的体现。

二、栈的实现（顺组表）

2.1 栈的功能

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

2.2 栈结构体的定义及其初始化

结构体的定义

typedef int STDataType;

typedef struct stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;

初始化（开辟空间）

void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  
  ps->capacity = 4;
  ps->top = 0;
}

2.3 压栈（存储数据）

//压栈
void STpush(ST* ps,STDataType x)
{
  assert(ps);

  ps->a[ps->top] = x;
  ps->top++;
}

2,4 删除数据

在这里面删除数据是配合，栈顶出栈。每次拿出一个数据，就要减少一个数据。

void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));

  ps->top--;
}

2.5 计算栈内元个数

//大小
int STSize(ST* ps)
{
  assert(ps);

  return ps->top;
}

2.6 判断栈内是否为空

这里运用 bool 类型直接返回，比较方便。

bool STEmpty(ST* ps)
{
  assert(ps);

  return ps->top == 0;
}

2.7 出栈

//出栈
STDataType STTop(ST* ps)
{
  assert(ps);

  return ps->a[ps->top-1];
}

2.8 增加容量

//检查容量
void CheckCapacity(ST*ps)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
    if (tmp == NULL)
    {
      perror("malloc fail");
      return;
    }
    ps->capacity *= 2;
    ps->a = tmp;
  }
}

2.9 销毁栈

//销毁
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

三、队列的实现（单链表）

3.1 队列的功能

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

3.2 队列的结构体定义以及初始化

结构体定义

定义两个结构体，第一个为存放数据，第二个结构体为两个指针，分别指向头和尾

typedef int QDataType;

typedef struct QNode
{
  struct QNode* next;
  QDataType data;

}QNode;

typedef struct Queue
{
  QNode*head;
  QNode*tail;
   
  int szie;
}Queue;

初始化

//初始化
void QueueInit(Queue* ps)
{
  assert(ps);
  
  ps->head = ps->tail = NULL;
  
  ps->szie = 0;
  
}

3.3 队列销毁

//销毁
void QueueDestroy(Queue* ps)
{
  assert(ps);
  QNode* cur = ps->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }

  ps->head = ps->tail = NULL;
  ps->szie = 0;
}

3.4 入队（插入数据）

//入队
void QueuePush(Queue* ps,QDataType x)
{
  assert(ps);

  QNode* newcode = (QNode*)malloc(sizeof(QNode));
  if (newcode == NULL)
  {
    perror("malloc fail");
    return ;
  }
  newcode->next = NULL;
  newcode->data = x;

  if (ps->head == NULL)
  {
    ps->head = ps->tail = newcode;
    
  }
  else

  {
    
    ps->tail->next = newcode;
    ps->tail = newcode;
  }

  ps->szie++;

}

3.5 删除数据（头删）

//删除
void QueuePop(Queue* ps)
{
  assert(ps);
  assert(ps->head != NULL);
  assert(!QueueEmpty(ps));

  if (ps->head->next == NULL)
  {
    free(ps->head);
    ps->head = ps->tail = NULL;
  }
  else
  {
    QNode* next = ps->head->next;
    free(ps->head);
    ps->head = next;

  }
  ps->szie--;
}

3.6 计算队列元素个数

//大小
int QueueSize(Queue* ps)
{
  assert(ps);

  return ps->szie;
}

3.7 判断是否队列为空

//判空队
bool QueueEmpty(Queue* ps)
{
  assert(ps);

  return ps->szie == 0;
}

3.8 出队（头）

//出队头
QDataType QueueTop(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));

  return ps->head->data;
}

3.9 出队（尾）

//出队尾
QDataType QueueBack(Queue* ps)
{
  assert(ps);

  return ps->tail->data;
}

四、栈和队列的源码

栈

Stack.h

#pragma once

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


typedef int STDataType;

typedef struct stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;

//初始化
void STInit(ST* ps);
//压栈
void STpush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//出栈
STDataType STTop(ST* ps);
//检查容量
void CheckCapacity(ST* ps);
//销毁
void STDestroy(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"


//初始化
void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STDataType*)malloc(sizeof(STDataType*)*4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  
  ps->capacity = 4;
  ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{
  assert(ps);

  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

//检查容量
void CheckCapacity(ST*ps)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
    if (tmp == NULL)
    {
      perror("malloc fail");
      return;
    }
    ps->capacity *= 2;
    ps->a = tmp;
  }
}

//压栈
void STpush(ST* ps,STDataType x)
{
  assert(ps);

  ps->a[ps->top] = x;
  ps->top++;
}

//删除
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));

  ps->top--;
}

//判空
bool STEmpty(ST* ps)
{
  assert(ps);

  return ps->top == 0;
}

//出栈
STDataType STTop(ST* ps)
{
  assert(ps);

  return ps->a[ps->top-1];
}

//大小
int STSize(ST* ps)
{
  assert(ps);

  return ps->top;
}

test.c

#define _CRT_SECURE_NO_WARNINGS


#include "stack.h"

void teststack()
{
  ST st;
  STInit(&st);

  STpush(&st, 1);
  STpush(&st, 2);
  STpush(&st, 3);
  STpush(&st, 4);
  STpush(&st, 5);

  printf("%d", STSize(&st));
  printf("\n");

  while (!STEmpty(&st))
  {
    printf("%d ", STTop(&st));
    STPop(&st);
  }
  printf("\n");
  printf("%d", STSize(&st));

  STDestroy(&st);

}



int main()
{
  teststack();

  return 0;
}

队列

Queue.h

#pragma once

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

typedef int QDataType;

typedef struct QNode
{
  struct QNode* next;
  QDataType data;

}QNode;

typedef struct Queue
{
  QNode*head;
  QNode*tail;
   
  int szie;
}Queue;


//单链表的实现，FIFO

//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//入队
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//大小
int QueueSize(Queue* ps);
//判空队
bool QueueEmpty(Queue* ps);
//出队头
QDataType QueueTop(Queue* ps);
//出队尾
QDataType QueueBack(Queue* ps);

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



//初始化
void QueueInit(Queue* ps)
{
  assert(ps);

  ps->head = ps->tail = NULL;

  ps->szie = 0;

}

//销毁
void QueueDestroy(Queue* ps)
{
  assert(ps);
  QNode* cur = ps->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }

  ps->head = ps->tail = NULL;
  ps->szie = 0;
}

//入队
void QueuePush(Queue* ps,QDataType x)
{
  assert(ps);

  QNode* newcode = (QNode*)malloc(sizeof(QNode));
  if (newcode == NULL)
  {
    perror("malloc fail");
    return ;
  }
  newcode->next = NULL;
  newcode->data = x;

  if (ps->head == NULL)
  {
    ps->head = ps->tail = newcode;
    
  }
  else

  {
    
    ps->tail->next = newcode;
    ps->tail = newcode;
  }

  ps->szie++;

}

//删除
void QueuePop(Queue* ps)
{
  assert(ps);
  assert(ps->head != NULL);
  assert(!QueueEmpty(ps));

  if (ps->head->next == NULL)
  {
    free(ps->head);
    ps->head = ps->tail = NULL;
  }
  else
  {
    QNode* next = ps->head->next;
    free(ps->head);
    ps->head = next;

  }
  ps->szie--;
}

//大小
int QueueSize(Queue* ps)
{
  assert(ps);

  return ps->szie;
}

//判空队
bool QueueEmpty(Queue* ps)
{
  assert(ps);

  return ps->szie == 0;
}

//出队头
QDataType QueueTop(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));

  return ps->head->data;
}

//出队尾
QDataType QueueBack(Queue* ps)
{
  assert(ps);

  return ps->tail->data;
}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"



void testQueue()
{
  Queue s;
  QueueInit(&s);

  QueuePush(&s, 1);
  QueuePush(&s, 2);
  QueuePush(&s, 3);
  QueuePush(&s, 4);

  

  //printf("%d ", QueueTop(&s));
  //QueuePop(&s);
  //printf("%d ", QueueTop(&s));
  //QueuePop(&s); 
  //printf("%d ", QueueTop(&s));
  //QueuePop(&s); 
  //printf("%d ", QueueTop(&s));
  //QueuePop(&s);
  //printf("\n");

  while (!(QueueEmpty(&s)))
  {
    printf("%d ", QueueTop(&s));
    QueuePop(&s);
  }


  QueueDestroy(&s);

}

int main()
{
  testQueue();


  return 0;
}

文章标签：
存储
关键词：
数据结构队列
数据结构队列源码
数据结构栈源码
数据结构源码
数据结构栈
chian-ocean
目录
相关文章
可能只会写BUG
|
3天前
|
Linux C++ Windows
栈对象返回的问题 RVO / NRVO
具名返回值优化（(Name)Return Value Optimization，(N)RVO）是一种优化机制，在函数返回对象时，通过减少临时对象的构造、复制构造及析构调用次数来降低开销。在C++中，通过直接在返回位置构造对象并利用隐藏参数传递地址，可避免不必要的复制操作。然而，Windows和Linux上的RVO与NRVO实现有所不同，且接收栈对象的方式也会影响优化效果。
可能只会写BUG
10 2
小Lee
|
18天前
|
存储 安全 编译器
缓冲区溢出之栈溢出（Stack Overflow
【8月更文挑战第18天】
小Lee
39 3
1387503158665997
|
5天前
crash —— 获取内核地址布局、页大小、以及栈布局
crash —— 获取内核地址布局、页大小、以及栈布局
1387503158665997
8 0
Star时光
|
5天前
|
存储 程序员 C语言
堆和栈之间有什么区别
【9月更文挑战第1天】堆和栈之间有什么区别
Star时光
45 0
cz游客
|
14天前
|
机器学习/深度学习 消息中间件 缓存
栈与队列的实现
栈与队列的实现
cz游客
35 0
aliyun6365824167
|
19天前
|
测试技术
【初阶数据结构篇】队列的实现（赋源码）
首先队列和栈一样，不能进行遍历和随机访问，必须将队头出数据才能访问下一个，这样遍历求个数是不规范的。
aliyun6365824167
22 0
睡觉待开机
|
24天前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
睡觉待开机
17 0
服务端技术栈
|
22天前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
35 1
栈的几个经典应用，真的绝了
热爱技术的小郑
|
24天前
|
C语言
用栈实现将一个十进制数值转换成八进制数值。即用该十进制数值除以8，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值
这篇文章展示了如何使用栈（包括顺序栈和链栈）实现将十进制数值转换成八进制数值的方法，通过C语言编程演示了两种栈的实现方式和使用场景。
热爱技术的小郑
35 1
用栈实现将一个十进制数值转换成八进制数值。即用该十进制数值除以8，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值
小狮子安度因1
|
19天前
|
负载均衡 网络协议 安全
DKDP用户态协议栈-kni
DKDP用户态协议栈-kni
小狮子安度因1
22 5