数据结构——栈,队列,及其结构特点应用。1

简介: ​✅<1>主页:我的代码爱吃辣📃<2>知识讲解:数据结构——栈,队列。🔥<3>创作者:我的代码爱吃辣☂️<4>开发环境:Visual Studio 2022🏡<5>系统环境:windows 10💬<6>前言:今天来学习一下,数据结构中的栈和队列的实现和应用。

🦃一.栈

🐔(1)什么是栈

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


60f8ba2f815343f2b721ba72b887eabc.png


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

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


9db0a952046e479a9649582f6e273d81.gif


🐣(2)栈的实现:

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为栈即插入和删除(入栈和出战栈)都是在线性表的尾部进行操作,数组的尾部的插如和删除的时间复杂度都是 O(1) ,而如果是链式结构,去实现栈结构,针对尾插和尾删的时间复杂度都是 O(n) ,而双向循环带头的链表,虽然可以解决这个问题,但是.......


我们将栈的实现分为以下各个部分:

1.栈的定义 (StactInit)

typedef int STDateType;  //数据类型
typedef struct Stact
{
  STDateType* date; //数组
  int capacity;   //栈的容量
  int top;      //栈内数据的个数
}ST;
ST* StactInit()
{
  ST* Stact = (ST*)malloc(sizeof(ST));  //创建栈的结构
    //栈的结构初始化
  Stact->capacity = 4; 
  Stact->top = 0;
  Stact->date = (STDateType*)malloc(sizeof(STDateType)*Stact->capacity);
    //返回栈
  return Stact;
}

2.栈的销毁 (StactDestroy)

void StactDestory(ST* Stact)
{
  assert(Stact);
  //先释放数组申请的空间
  free(Stact->date);
  Stact->date = NULL;
  Stact->capacity = 0;
  Stact->top = 0;
  //在释放栈的结构体空间
  free(Stact);
}

3.栈的StactPushBank操作 (入栈)

void StactPushBank(ST* Stact, STDateType x)
{
  //断言Stact,当进行Push时,栈结构必须存在(Stact!=NULL),
  //如果不存也就是栈是空(Stact==NULL),那Push的操作就是非法的
  assert(Stact);
  //每次对栈的底层是数组,所以每次都要检查是否需要扩容
  if (Stact->capacity == Stact->top)
  {
    STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
    if (tmp==NULL)
    {
      perror("realloc");
      exit(-1);
    }
    Stact->date = tmp;
    Stact->capacity *= 2;
  }
  //将x入栈,数组的栈内数据的个数加一
  Stact->date[Stact->top++] = x;
}

4.栈的StactPopBank操作 (出栈)

void StactPopBank(ST* Stact)
{
  assert(Stact);
  //当栈已经空了,还去出栈就是非法了
  assert(!StactEmpty(Stact));  
  Stact->top--;
}

5.栈的 StactTop (得到栈顶元素)

STDateType StactTop(ST* Stact)
{
  assert(Stact);
  //当栈已经空了,无法获取栈顶元素
  assert(!StactEmpty(Stact));
  return Stact->date[Stact->top - 1];
}

6.栈的StactSize (元素个数)

int StactSize(ST* Stact)
{
  assert(Stact);
  return Stact->top;
}

7.栈的判空 (StactEmpty)

bool StactEmpty(ST* stact)
{
  assert(stact);
  //当栈内数据个数为0时,栈为空
  return stact->top == 0;
}

测试:

void Print(ST* Stact)
{
  assert(Stact);
  for (int i = 0; i < Stact->top; i++)
  {
    printf("%d ", Stact->date[i]);
  }
  printf("\n");
}
int main()
{
  ST* Stact= StactInit();
  StactPushBank(Stact, 100); 
  StactPushBank(Stact, 200); 
  StactPushBank(Stact, 300); 
  StactPushBank(Stact, 400); 
  Print(Stact);
  printf("StactSize:%d\n",StactSize(Stact));
  //Pop一次
  StactPopBank(Stact);
  Print(Stact);
  printf("StactSize:%d\n", StactSize(Stact));
  StactDestory(Stact);
  return 0;
}



🌱(3).栈的应用

(1)例题

若进栈序列为 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


分析:选项A,1进1出,2进3进4进,4出3出2出,所以出栈顺序1,4,3,2,选项A正确。


          选项B,1进2进,2出,3进3出,4进,4出1出,所以出栈顺序2,3,4,1,选项B正确。


          选项C,1进2进3进,3出,此时想要出2,就必须先出栈1,所以选项C错误。


          选项D,1进2进3进,3出,4进,4出2出1出,所以出栈顺序3,4,2,1,选项D正确。


(2)例题


LeetCode ———— 20. 有效的括号


题目描述:


b76eff3ad7f143498a9b83d75e64c680.png


思路分析:


遇到左括号就进栈,遇到右括号就出栈,将出栈的左括号与右括号进行匹配,如果匹配成功就继续,如果匹配失败就返回false。


8c617e2b121d49f6beb66afc278e5d41.gif


//栈结构
typedef char STDateType;
typedef struct Stact
{
  STDateType* date;
  int capacity;
  int top;
}ST;
ST* StactInit();
void StactPushBank(ST* Stact, STDateType x);
int StactSize(ST* Stact);
void StactDestory(ST* Stact);
void StactPopBank(ST* Stact);
STDateType StactTop(ST* Stact);
bool StactEmpty(ST* stact);
ST* StactInit()
{
  ST* Stact = (ST*)malloc(sizeof(ST));
  Stact->capacity = 4;
  Stact->top = 0;
  Stact->date = (STDateType*)malloc(sizeof(STDateType) * Stact->capacity);
  return Stact;
}
void StactPushBank(ST* Stact, STDateType x)
{
  assert(Stact);
  if (Stact->capacity == Stact->top)
  {
    STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    Stact->date = tmp;
    Stact->capacity *= 2;
  }
  Stact->date[Stact->top++] = x;
}
bool StactEmpty(ST* stact)
{
  assert(stact);
  return stact->top == 0;
}
STDateType StactTop(ST* Stact)
{
  assert(Stact);
  assert(!StactEmpty(Stact));
  return Stact->date[Stact->top - 1];
}
void StactPopBank(ST* Stact)
{
  assert(Stact);
  assert(!StactEmpty(Stact));
  Stact->top--;
}
void StactDestory(ST* Stact)
{
  assert(Stact);
  free(Stact->date);
  Stact->date = NULL;
  Stact->capacity = 0;
  Stact->top = 0;
  free(Stact);
}
int StactSize(ST* Stact)
{
  assert(Stact);
  return Stact->top;
}
bool isValid(char* s) {
  //创建栈
  ST* stact = StactInit();
  while (*s)
  {
    //遇到左括号进栈
    if (*s == '(' || *s == '{' || *s == '[')
    {
      StactPushBank(stact, *s);
      s++;
    }
    else
    { //遇到右括号出栈,如果出栈的括号时,
      //栈中已经空,此时括号匹配已经失败
      if (StactEmpty(stact))
      {
        StactDestory(stact);
        return false;
      }
      //如果栈不为空,出栈的左括号,与遇到的右括号匹配
      //如果匹配成功就,继续向后走,匹配失败就返回false
      char ch = StactTop(stact);
      StactPopBank(stact);
      if ((ch == '(' && *s == ')') ||
        (ch == '[' && *s == ']') ||
         ch == '{' && *s == '}')
      {
        s++;
      }
      else
      {
        StactDestory(stact);
        return false;
      }
    }
  }
  //当括号匹配匹配完时,如果栈中还有括号,
  //也就意味着匹配失败。
  if (!StactEmpty(stact))
  {
    StactDestory(stact);
    return false;
  }
  StactDestory(stact);
  return true;
}


🌾二.队列

🌲(1)什么是队列

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。


6443b536dae748559067d052b566dfd1.gif


🌵 (2)队列的实现

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


1.队列的定义——QueueInit


由于队列是,队尾入数据,队头出数据,为了方便数据的入队,我们除了队头指针,还会设计一个队尾指针。

typedef int QUDateType;
typedef struct QueueNode
{
  QUDateType date;
  struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
  int size;
}Queue;
void QueueInit(Queue* pque)
{
  assert(pque);
  pque->head = NULL;
  pque->tail = NULL;
  pque->size = 0;
}
int main()
{
  Queue Q;
  QueueInit(&Q);
  return 0;
}

2.入队操作——QueuePush

void QueuePush(Queue* pque,QUDateType x)
{
  //断言队列结构,当进行入队操作时,队列结构一定不能为空
  assert(pque);
  //申请空间
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  //赋值
  newnode->date = x;
  newnode->next = NULL;
  //如果队列为空,此时入队的就是第一个数据,也将是队列的头尾数据
  if (pque->head == NULL)
  {
    pque->head = pque->tail = newnode;
  }
  //如果队列不为空,就将数据连接到队尾巴后面
  else
  {
    pque->tail->next = newnode;
    pque->tail = newnode;
  }
  //队列中数据个数加一
  pque->size++;
}

3.队列销毁——QueueDestroy

void QueueDestroy(Queue* pque)
{
  assert(pque);
  QueueNode* cur = pque->head;
  while (cur)
  {
    QueueNode* nextnode = cur->next;
    free(cur);
    cur = nextnode;
  }
  pque->head = pque->tail = NULL;
}

4.得到对头数据——QueueFront

QUDateType QueueFront(Queue*pque)
{
  assert(pque);
  assert(!QueueEmpty(pque));
  return pque->head->date;
}

5.队列判空——QueueEmpty

bool QueueEmpty(Queue* pque)
{
  assert(pque);
  return pque->head == NULL && pque->tail == NULL;
}

6.删除对头数据——QueuePop

void QueuePop(Queue* pque)
{
  assert(pque);   //队列结构不能为空
  assert(!QueueEmpty(pque));   //删除数据时队列不能为空 
  //队列中只有一个数据的时候
  if (pque->head->next == NULL)
  {
    free(pque->head);
    pque->tail = pque->head = NULL;
  }
  //队列中数据个数大于1
  else
  {
    QueueNode* popnode = pque->head;
    pque->head = pque->head->next;
    free(popnode);
  }
  //数据个数减一
  pque->size--;
}

7.得到队尾数据——QueueBack

QUDateType QueueBack(Queue* pque)
{
  assert(pque);
  assert(!QueueEmpty(pque));
  return pque->tail->date;
}

8.得到队列中数据个数——QueueSize

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

测试:

int main()
{
  Queue Q;
  QueueInit(&Q);
  //插如100 .200 300 ,400 ,
  QueuePush(&Q, 100);
  QueuePush(&Q, 200);
  QueuePush(&Q, 300);
  QueuePush(&Q, 400);
  //输出队头数据
  printf("%d ", QueueFront(&Q));
  //输出队尾数据
  printf("%d ", QueueBack(&Q));
  //输出队列数据个数
  printf("%d \n", QueueSize(&Q));
  //输出队列中的数据
  while (!QueueEmpty(&Q))
  {
    printf("%d ", Q.head->date);
    QueuePop(&Q);
  }
  //队列销毁
  QueueDestroy(&Q);
  return 0;
}


bb036e81f0a54c54a7e86300c4f55968.png

相关文章
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5
|
23天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
40 5
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
48 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
191 9
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
48 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器