当前位置：首页 > news >正文

栈以及队列的详细讲解

news 2026/5/24 22:01:09

1.栈的定义以及实现

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

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

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

一般情况下实现栈有两种，分为用数组实现以及用链表实现，由于用数组实现可以更小代价的进行出栈以及入栈操作所以这里我们使用的是数组实现的方式。

使用数组实现分为静态实现以及动态实现，静态实现不太实用，所以这里使用的是动态实现的栈

动态栈的定义，以及要实现的功能：

typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; //初始化 void StackInit(ST* ps); //进栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //获取栈顶元素 STDataType Stacktop(ST* ps); //获取栈的大小 int StackSize(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); //销毁栈 void StackDestroy(ST* ps);

这里的top指向的是栈里面最后一个元素的后面一个位置

1.1栈的初始化，以及进栈和出栈

操作代码如下

//初始化 void StackInit(ST* ps) { ps->a = NULL; ps->capacity = ps->top = 0; } //进栈 void StackPush(ST* ps,STDataType x) { assert(ps); if (ps->capacity == ps->top) { int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = realloc(ps->a, Newcapacity*sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } else ps->a = tmp; ps->capacity = Newcapacity; } ps->a[ps->top++] = x; } //出栈 void StackPop(ST* ps) { assert(ps && ps->top>0);//必须保证栈不为空才可以进行删除操作 ps->top--; }

1.2获取栈顶元素，获取栈的大小，判断是否为空，以及销毁的

代码如下图：

//获取栈顶元素 STDataType Stacktop(ST* ps) { assert(ps&&ps->top!=0); return ps->a[ps->top-1];//保证返回正确值的同时也不会改变ps->top的值 } //获取栈的大小 int StackSize(ST* ps) { assert(ps); return ps->top; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //销毁栈 void StackDestroy(ST* ps) { assert(ps); STDataType* tmp = ps->a; free(tmp); ps->a = NULL; ps->capacity = ps->top = 0; }

2.队列的定义以及实现

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头
在这里我们先定义一个结构体用于表示队列中的节点

typedef struct QueueNode { struct QueueNode* next; QEDataType data; }QueueNode;

然后我们再定义一个结构体用于表示这个队列

typedef struct Queue { QueueNode* phead;//队头指针 QueueNode* ptail;//队尾指针 int size;//表示队列中有多少个元素 }Queue;

需要实现的功能如下：

//初始化 void QueueInit(Queue*p); //入队 void QueuePush(Queue* p,QEDataType x); //出队 void QueuePop(Queue* p); //返回队头元素 QEDataType QueueFront(Queue* p); //返回队尾元素 QEDataType QueueBack(Queue* p); //返回队列的大小 int QueueSize(Queue* p); //判断队列是否为空 bool QueueEmpty(Queue* p); //销毁队列 void QueueDestroy(Queue* p);

2.1队列的初始化，入队，以及出队

代码实现如下：

//初始化 void QueueInit(Queue* p) { p->phead = p->ptail = NULL; p->size = 0; } //入队 void QueuePush(Queue* p, QEDataType x) { assert(p); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode== NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; if (p->phead ==NULL&& p->ptail == NULL) { p->phead = p->ptail = newnode; } else { p->ptail->next = newnode; p->ptail = p->ptail->next; } p->size++; } //出队 void QueuePop(Queue* p) { assert(p); assert(p->size != 0); if (p->phead == p->ptail) { free(p->phead); p->phead = p->ptail = NULL; p->size--; } else { QueueNode* tmp = p->phead->next; free(p->phead); p->phead = tmp; p->size--; } }

2.2队列的返回首尾元素，判空，队列大小，以及销毁代码

//返回队头元素 QEDataType QueueFront(Queue* p) { assert(p); assert(p->size != 0); return p->phead->data; } //返回队尾元素 QEDataType QueueBack(Queue* p) { assert(p); assert(p->size != 0); return p->ptail->data; } //返回队列的大小 int QueueSize(Queue* p) { assert(p); return p->size; } //判断队列是否为空 bool QueueEmpty(Queue* p) { assert(p); return p->size == 0; } void QueueDestroy(Queue*p) { assert(p); QueueNode* tmp; while (p->phead) { tmp = p->phead->next; free(p->phead); p->phead = tmp; } p->phead = p->ptail = NULL; p->size = 0; }

由于栈以及队列部分的内容比较简单需要强调的部分较少所以这一片就到这里了

查看全文

http://www.jsqmd.com/news/879811/