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

数据结构-栈和队列（一）

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

1.栈

1.1 栈的概念及结构

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

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

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

数据进栈出栈遵循后进先出的原则：

下面看两道例题：

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

答案是B。

2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1

答案是C。

这道题说可以在进栈的过程中出栈，ABD不用说，只有C，先出栈的是3，说明此时栈里面1和2肯定还在，而1不可能在2之前出栈，所以选C。

1.2 栈的实现

实现栈有两种方式，一种是数组栈，一种是链式栈：

这里我们采用数组栈，因为数组在尾插的代价比较小。

首先，我们来定义一个结构体：

typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;//栈顶元素位置
  int capacity;//容量
}ST;

下面我们来实现栈：

初始化栈：

初始化很简单，但要注意断言pst是否为空。（pst是结构体变量的地址，永远不为空，所以需要断言）

void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->top = 0;//指向栈顶元素的下一个位置
  pst->capacity = 0;
}

入栈：

入栈时，我们要为栈开辟空间，然后才能插入数据。由于只有入栈需要开辟空间，所以这里我们并没有封装开辟空间的函数，直接在入栈函数里面开辟空间就行。

当pst->top=pst->capacity=0时，说明此时还没有就开辟空间，所以我们给它开辟4个字节大小。下次再进去，不等于0，空间就增容到上次的2倍。

void STPush(ST* pst, STDatatype x)
{
  //开辟空间
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
    if (tmp == NULL)
    {
      perror("malloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
  //插入
  pst->a[pst->top] = x;
  pst->top++;
}

判空函数：

bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}

出栈：

出栈只需要将pst->top--即可，但是注意要断言此时的栈不能为空。

STEmpty函数是用来判断栈是否为空，它的返回值类型是bool型，bool型返回true或false，当pst->top=0时，说明此时栈为空，返回true，取反!true为假，断言报错。

bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;
}

获取栈顶元素：

直接返回栈顶元素即可，pst->top是栈顶元素的下一个位置，所以要返回pst->top-1处的值。

STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top - 1];
}

获取栈中有效元素的个数：

int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}

销毁栈：

因为是数组栈，所以直接free数组名即可。

void STDestory(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}

完整代码：

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
STTest1()
{
  ST st;
  STInit(&st);
  STPush(&st, 1);
  STPush(&st, 2);
  printf("%d ", STTop(&st));
  STPop(&st);
  STPush(&st, 3);
  STPush(&st, 4);
  STPush(&st, 5);
  while (!STEmpty(&st))
  {
    printf("%d ", STTop(&st));
    STPop(&st);
  }
  STDestory(&st);
}
int main()
{
  STTest1();
  return 0;
}

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* pst);
//入栈
void STPush(ST* pst, STDatatype x);
//出栈
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈顶元素
STDatatype STTop(ST* pst);
//获取栈中有效元素个数
int STSize(ST* pst);
//销毁栈
void STDestory(ST* pst);

Stack.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDatatype x)
{
  //开辟空间
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : (pst->capacity) * 2;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
    if (tmp == NULL)
    {
      perror("malloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
  //插入
  pst->a[pst->top] = x;
  pst->top++;
}
//判空函数
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
//出栈
void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;
}
//获取栈顶元素
STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top - 1];
}
//获取栈中有效数据的个数
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
//销毁栈
void STDestory(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}

测试：

2. 队列

2.1 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列中的元素遵循先进先出的原则

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

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

队列很好理解，就像在食堂打饭一样，先排进队的先打饭，打完饭先走，

2.2 队列的实现

要实现队列，最好使用链表的方式，因为数组头删效率比较低。

我们先来定义一个结构体：

typedef int QDatatype;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDatatype data;
}QNode;

很明显，这是个单链表，我们要实现队列，还要知道队列的头和尾，以及队列中有效数据的个数，所以索性把它们也定义成一个结构体：

typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;

phead就是队列的头，ptail就是队列的尾

下面我们来实现队列吧。

队列的初始化：

//初始化队列
void QueueInit(Queue* pq)
{
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}

队尾入队列：

和栈相似，在入队函数内部开辟空间，这其实就是单链表的尾插（不带哨兵位）。

//队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
    assert(pq->phead == NULL);
    pq->phead = pq->ptail=newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}

判空函数：

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size ==0 ;
}

队头出队列：

这相当于单链表的头删，注意分情况，一个节点和多个节点要单独写，同时要用判空函数QueueEmpty()断言队列是否为空。

//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //一个节点
  //多个节点
  if (pq->phead->next == NULL)
  {
    free(pq->phead);
    pq->phead = pq->ptail= NULL;
  }
  else
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->size--;
}

获取队列头部元素：

//获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}

获取队列尾部元素：

//获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}

获取队列中有效元素个数：

//获取队列中有效元素个数
int Queuesize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

销毁队列：

//销毁队列
void DestoryQueue(Queue* pq)
{
  assert(pq);
  while (pq->phead)
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

完整代码：

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
QueueTest1()
{
  Queue pq;
  QueueInit(&pq);
  QueuePush(&pq, 1);
  QueuePush(&pq, 2);
  QueuePop(&pq);
  printf("%d ", QueueFront(&pq));
  QueuePush(&pq, 3);
  QueuePush(&pq, 4);
  printf("%d ", QueueBack(&pq));
  while (!QueueEmpty(&pq))
  {
    printf("%d ", QueueFront(&pq));
    QueuePop(&pq);
  }
  DestoryQueue(&pq);
}
int main()
{
  QueueTest1();
  return 0;
}

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDatatype;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDatatype x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部元素
QDatatype QueueFront(Queue* pq);
//获取队列尾部元素
QDatatype QueueBack(Queue* pq);
//获取队列中有效元素个数
int Queuesize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//销毁队列
void DestoryQueue(Queue* pq);

Queue.c 

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化队列
void QueueInit(Queue* pq)
{
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
//队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
    assert(pq->phead == NULL);
    pq->phead = pq->ptail=newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
//判空函数
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size ==0 ;
}
//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //一个节点
  //多个节点
  if (pq->phead->next == NULL)
  {
    free(pq->phead);
    pq->phead = pq->ptail= NULL;
  }
  else
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->size--;
}
//获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}
//获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}
//获取队列中有效元素个数
int Queuesize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
//销毁队列
void DestoryQueue(Queue* pq)
{
  assert(pq);
  while (pq->phead)
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

测试：

以上就是栈和队列的实现了，下一节我们讲几个栈和队列QJ题，

未完待续。。。

关键词：
数据结构队列
数据结构栈队列
数据结构栈
数据结构栈和队列
成屿
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
191 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
32 1
龙大吉
|
24天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
45 5
德国都芳最好
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
83 21
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
34 2
dufadayang
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
51 4
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
26 1
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
48 0
星霜旅人
|
2月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
23 1
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
48 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器