3.栈和队列(汇总版)

简介: 3.栈和队列(汇总版)

1.栈(一端插和删)

1.1栈的概念及结构

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

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

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

【注意:】因为不知道什么时候出栈,所以顺序也是多变的

具体实现,可以看一下下面这个图片的演示

关键的元素有

接下来就是我们的增删查改,通过接口来实现啦

主体:

// 静态
//typedef int STDataType;
// #define N 10
// typedef struct Stack
// {
//  STDataType _a[N];
//  int _top; // 栈顶
// }Stack;
//更多用的是下面的动态
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int STDataType;
typedef struct stack
{
  STDataType* a;//栈底
  int top;  //栈顶
  int capacity; //容量
}ST;
 
//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//入栈(压栈)
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* ps);

点拨:

//入栈
ps->a[ps->top] = x;
ps->top++;
//出栈
ps->top--;
//获取栈顶元素
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
  return ps->a[ps->top - 1];
  //栈顶元素其实就是top前一位
  //这里注意栈为空时不能获取到元素
}

有一个小细节:栈顶初始化的选择会影响到栈,所以还是要通过接口来实现,如下

栈的灵魂就在于top,top++,top--,更多的还是在做题中去理解吧

2.队列(一端插另一段删)

2.1队列的概念及结构

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

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

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

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

2.2 队列的实现

创建结构体QueueNode这个结构体是创建节点的,节点由数据和指向下一个节点的指针构成的

第二个结构体是创建指向节点的两个指针,对头指针head和队尾指针tail

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

队列的接口

void QueueInit(Queue* pq);   //初始化队列
void QueueDestory(Queue* pq);    //销毁队列
 
void QueuePush(Queue* pq, QueueDataType x); //插入元素
void QueuePop(Queue* pq);   //出队列
 
QueueDataType QueueFront(Queue* pq);  //查看队头元素
QueueDataType QueueBack(Queue* pq);   //查看队尾元素
 
bool QueueEmpty(Queue* pq);  //检查队列是否为空
int QueueSize(Queue* pq);    //查看队列的长度

1.初始化队列

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

2.销毁队列

当队列不为空时,用一个代替对头往后访问的指针cur ,当cur不为空时,用一个新的节点del 接收cur指向的节点。将del节点释放并置为空,cur在往后走完成对队列的遍历,最后将对头指针和队尾指针都置为空指针

void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;//再在其中定义Qnode引入
  while (cur)
  {
    QNode* del = cur;//暂存销毁
    cur = cur->next;//保留好进行后移
    free(del);
    del = NULL;//del对每个节点进行释放,保留了cur后移
 
  }
 
  pq->head = pq->tail = NULL;
 
}

3.插入元素

队列的性质插入元素只能是尾插,分为两种情况来看:1.队列为空 2.队列不为空

1. 队列为空时,先去malloc一个新节点,让对头和队尾都指向这个新节点

2. 当队列不为空时,malloc一个新节点,将新节点插入到tail指针的下一个位置,新的队尾指向新节点的下一个位置

void QueuePush(Queue* pq, QueueDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 1.开辟一个新空间
  if (newnode == NULL)   
  {
    perror("malloc fail!!!");
    exit(-1);    //不成功直接退出程序
  }
  else
  {
    newnode->data = x;   //2. 将数据导入到新空间中
    newnode->next = NULL; //新节点指向空
 
  }
 
  //如果队列为空
  if (pq->head ==NULL&& pq->tail==NULL)//说明队列空
  {
    pq->head = pq->tail = newnode;  //都指向新节点
  }
  else
  {
    pq->tail->next = newnode;//3. 将tail的下一个定为new
    pq->tail = pq->tail->next;// tail后移
  }
 
}

4.出队列(头删)

出队列也分为两种情况:1.队列有一个节点   2.队列有多个节点

void QueuePop(Queue* pq)//队列特性  头删
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //一个节点
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
 
  else//很多节点
  {
    QNode* del = pq->head;//del暂存然后销毁
    pq->head = pq->head->next;//保留起来好进行后移
    free(del);
    del = NULL;
  }
 
}

5.访问对头

访问得有元素,需要判断队列是否为空

QueueDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->head->data;
}

6.访问队尾

访问得保证队列有元素,需要判断队列是否为空

QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty);
 
 
    return pq->tail->data;
}

7.判断队列是否为空

bool QueueEmpty(Queue* pq)
{
    return pq->head == NULL;   //空返回1  有元素0
 
}

8.查看队列的元素个数

查看队列元素的个数得保证队列有元素,生成一个新的指针接受队头指针,代替头指针往后访问队列,返回n 的数值就是队列的元素个数。

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

Queue整体代码:

Queue.h

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
 
typedef int QueueDataType;
 
typedef struct QueueNode
{
  struct QueueNode* next;
  QueueDataType data;
 
}QNode;
 
typedef struct Queue
{
 
  QNode* head;
  QNode* tail;
 
 
}Queue;
 
 
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
 
void QueuePush(Queue* pq, QueueDataType x);
void QueuePop(Queue* pq);
 
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);
 
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
 

Queue.c

#include "Queue.h"
 
 
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
 
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
 
  }
 
  pq->head = pq->tail = NULL;
 
 
}
 
void QueuePush(Queue* pq, QueueDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail!!!");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
 
  }
 
  //如果队列为空
  if (pq->head ==NULL&& pq->tail==NULL)//说明队列空
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = pq->tail->next;
  }
 
 
 
}
 
 
 
void QueuePop(Queue* pq)//队列特性  头删
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //一个节点
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
 
  else//很多节点
  {
    QNode* del = pq->head;
    pq->head = pq->head->next;
    free(del);
    del = NULL;
  }
 
 
 
 
}
 
QueueDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->head->data;
}
 
 
QueueDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty);
 
 
  return pq->tail->data;
}
 
bool QueueEmpty(Queue* pq)
{
  return pq->head == NULL;   //空返回1  有元素0
 
}
int QueueSize(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty);
 
 
  int n = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    ++n;
    cur = cur->next;
  }
 
  return n;
 
 
}

test.c

#include"Queue.h"
 
void testqueue()
{
  Queue q;
  QueueInit(&q);
 
  QueuePush(&q, 555);
  QueuePush(&q, 666);
  QueuePush(&q, 777);
 
  QueuePush(&q, 1);
  
   
 
  while (!QueueEmpty(&q))
  {
 
    printf("%d", QueueFront(&q));
 
    QueuePop(&q);
 
    printf("\n");
  }
 
 
 
  QueueDestory(&q);
}
 
 
 
int main()
{
 
 
  testqueue();
 
  return 0;
}
相关文章
|
17天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
12天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
7天前
|
API
用栈翻转字符串
用栈翻转字符串
12 0
|
7天前
|
JavaScript
数据结构(用 JS 实现栈和队列【三种方式】)
数据结构(用 JS 实现栈和队列【三种方式】)
15 0
|
11天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
12天前
|
算法
数据结构与算法:栈与队列
数据结构与算法:栈与队列
|
15天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
14 0
|
15天前
|
存储 人工智能 程序员
技术心得记录:堆(heap)与栈(stack)的区别
技术心得记录:堆(heap)与栈(stack)的区别
12 0
|
17天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
9 0
|
18天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
24 5