栈和队列的实现(详解+图解!文末附完整代码)

简介: 栈和队列的实现(详解+图解!文末附完整代码)

栈的基本概念

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

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

出栈和入栈的操作如下:

他们都只能从栈顶进行出栈和进栈操作,所以栈要遵守先进后出的原则

栈的先进先出原则如下:

栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以我们在这里选择用数组来实现栈。

数组栈的结构图:

下面我们就用数组来是具体实现栈的增删查改等操作

头文件如下:

#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // 栈顶
  int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
创建栈

首先我们在这里将int作为本次栈的数据类型

我们还要定义一个结构体里面有数组,栈顶元素的下标的+1和栈的容量(栈里面的最多元素个数)

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // 
  int capacity;  //  
}Stack;
栈的初始化

栈的初始化就比较简单了,直接将top和容量置为0,并且把数组置为空

void StackInit(Stack* ps)
{
  assert(ps);
  ps->top = 0;
  ps->capacity = 0;
  ps->a = NULL;
}
栈的销毁

栈的销毁同样很简单,将数组free掉,防止出现野指针,同时置空,然后容量和栈顶元素下标置为0

void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
判断栈是否为空

在后面的增删查改等操作我们需要断言,为了增加代码的可读性,我们直接写一个函数 ,更加容易理解,如果栈顶元素下标为0,那么这个栈就为空 ,所以直接return top等于 0这个表达式的值,为空则返回 1,不为空则返回0

int StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
数据进栈

数据进栈是从栈顶入,我们首先要判断这个 栈是否已满,如果满了的话那么栈顶的下标就和容量相等,对于top和capacity的不理解的可以看这个图,top的意思如下图:

当capacity和top相等时其实是有两种情况的,一种时为空,另一种是栈满,,我们在这里就用一个三目操作符,如果为0,就将capacity初始化为4,否则将capacity的原来的值乘2,然后动态开辟realloc一块新的空间,大小就是newcapacity,这样我们就完成了扩容

然后我们将新空间temp给数组a

最后直接把插入的数据data给a[top],同时top++

void StackPush(Stack* ps, STDataType data)
{
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
    if (temp == NULL)
    {
      perror("realloc");
      return;
    }
    ps->capacity = newcapacity;
    ps->a = temp;
  }
  ps->a[ps->top] = data;
  ps->top++;
}
数据出栈

出栈及其简单,直接先判断栈是否为空,然后将top–即可

void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
获取栈顶元素

栈顶元素的下标其实就是top-1,所以直接返回a[top-1]

STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
获取栈内的元素个数

栈内元素个数就是top的值,栈为空top为0

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

栈的实现就完成了,完整代码如下:

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // ջ
  int capacity;  //  
}Stack;
void StackInit(Stack* ps)
{
  assert(ps);
  ps->top = 0;
  ps->capacity = 0;
  ps->a = NULL;
}
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
int StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackPush(Stack* ps, STDataType data)
{
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
    if (temp == NULL)
    {
      perror("realloc");
      return;
    }
    ps->capacity = newcapacity;
    ps->a = temp;
  }
  ps->a[ps->top] = data;
  ps->top++;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

队列

栈的基本概念

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

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

队列的实现

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

这里我们就用列表的结构来实现队列

头文件如下:

注意,这里我们定义了两个结构体,,第一个结构体其实只是链表的结构,里面有一个next一个data,第二个则是队列的结构,一个队头(出数据)指针,一个队尾指针(进数据),还有一个队列的大小

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<ctype.h>
// 链式结构:表示队列 
typedef int QDataType;
typedef struct QListNode
{
  struct QListNode* next;
  QDataType data;
}QNode;
// 队列的结构 
typedef struct Queue
{
  QDataType size;
  QNode* front;
  QNode* rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
队列的初始化

初始目前以及是熟能生巧了,很简单,size置为0,头尾指针置为空即可

void QueueInit(Queue* q)
{
  assert(q);
  q->size = 0;
  q->front = q->rear = NULL;
}
队列的销毁

队列的销毁我们需要花点功夫理解一下:

因为队列有多个节点,全部都要free掉 ,不然就可能会出现野指针的问题,所以我们在这里用一个while循环,将cur置为头指针,将next置为cur的next,这样当前cur的next就不会丢失。首先我们把cur给free掉,然后将cur置为next继续操作,直到cur为空,然后将front和rear置为空,size置为0即可。

void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = q->rear = NULL;
  q->size = 0;
}
判断队列是否为空

和栈一样,提高代码的可读性,如果size=0,其实队列就为空,但是头尾指针都为空时也可以,为空时返回1,不为空时返回0

int QueueEmpty(Queue* q)
{
  assert(q);
  return q->front == NULL && q->rear == NULL;
  /*return q->size == 0;*/
}
队列数据插入

要插入一个数据我们首先要做的就是开辟有一个新的链表节点,然后将他的next置为空,data置为你要插入的数据

插入数据分为两种情况,链表为空和不为空

链表为空时直接将front和rear置为新节点newnode同时size++

链表不为空时就将front的next置为newnode,rear置为newnode同时size++

void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->rear == NULL)
  {
    assert(q->front == NULL);
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;
}
队列数据删除

队列的删除我们就要判断队列是否为空,为空就不能删除了

同样的有两种情况:

链表只有一个节点时直接将头尾指针都置为空即可,size–

链表有多个节点时就将front的next置为front,size–

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  if (q->rear == q->front)
  {
    free(q->front);
    q->front = q->rear = NULL;
  }
  else
  {
    QNode* next = q->front->next;
    free(q->front);
    q->front = next;
  }
  q->size--;
}
获取队头数据

获取队头的元素 ,直接返回头指针的data即可

QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
获取队尾数据

获取队尾元素 同样简单,直接返回rear的data即可

QDataType QueueBack(Queue* q)
{
  assert(q);
  return q->rear->data;
}
求队列元素个数

直接返回size的值即可

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

队列的实现就完成了

完整代码如下:

void QueueInit(Queue* q)
{
  assert(q);
  q->size = 0;
  q->front = q->rear = NULL;
}
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = q->rear = NULL;
  q->size = 0;
}
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->front == NULL && q->rear == NULL;
  /*return q->size == 0;*/
}
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->rear == NULL)
  {
    assert(q->front == NULL);
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;
}
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  //һڵʱ
  if (q->rear == q->front)
  {
    free(q->front);
    q->front = q->rear = NULL;
  }
  //ڵ
  else
  {
    QNode* next = q->front->next;
    free(q->front);
    q->front = next;
  }
  q->size--;
}
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
QDataType QueueBack(Queue* q)
{
  assert(q);
  return q->rear->data;
}
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}

好了,今天的分享到这里就结束了,谢谢大家的支持!

相关文章
|
2月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
|
15天前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
栈区的非法访问导致的死循环(x64)
|
14天前
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
5月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
290 77
|
4月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
65 11
|
4月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
5月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
213 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
5月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
153 7
|
7月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
717 9
|
7月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
174 58