目录:
1. 栈 的表示和实现
2. 队列 的表示和实现
一:栈(Stack)的表示和实现
1.1栈的概念及结构
栈:一种特殊的线性表,只允许在固定的一端进行插入与删除元素操作。
进行数据插入和删除操作的一端称为栈顶 ,另一端称为栈底。栈中的数据元素遵守 后进先出 LIFO ( Last In First Out) 的原则。
压栈 :栈的插入操作叫做进栈/ 压栈 / 入栈, 入数据在栈顶 。
出栈 :栈的删除操作叫做出栈。出数据也在栈顶。
就像如图这种薯片一样:
了解这么多,我们做一点小总结:
1.先进入栈的元素 会放在栈的底部。2.取出元素的时候,先取出顶部元素。3.如果栈空了---不可取出元素
1.2 栈的实现
栈的实现一般可以使用 数组或者链表实现 ,相对而言数组的结构实现更优一些。因为数组在尾上
插入数据的代价比较小。
定义栈的结构体:
以上是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈:
提前需要注意的是,对top指针的初始化
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; //容量
}ST;
栈所需的接口:
void StackInit(ST* ps); //初始化栈
void StackDestory(ST* ps); //栈的销毁
void StackPush(ST* ps, STDataType x); // 入栈
void StackPop(ST* ps); // 出栈
STDataType StackTop(ST* ps); //取栈顶元素int StackSize(ST* ps); //获取栈中有效元素个数
bool StackEmpty(ST* ps); //检测栈是否为空
代码的实现:
#include<stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; //容量
}ST;
void StackInit(ST* ps)//初始化
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)//申请失败的话
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;//top=0 指向的是栈顶数据的下一个
//top=-1 指向的是栈顶的数据
}
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
// 入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
// 满了---> 增容
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)//增容失败的话
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
// 出栈
void StackPop(ST* ps)
{
assert(ps);
// 栈空了,调用Pop,直接中止程序报错
assert(ps->top > 0);
ps->top--;
}
//返回栈顶元素
STDataType StackTop(ST* ps)
{
assert(ps);
// 栈空了,调用Top,直接中止程序报错
assert(ps->top > 0);
return ps->a[ps->top -1];
}
//数据个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
对代码进行检验:
二:队列(Queue) 的表示和实现
1.1队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的 特殊线性表。队列具有 先进先出 FIFO(First In First Out)入队列:进行插入操作的一端 称为 队尾出队列:进行删除操作的一端 称为队头
就像下图排队买包子一样:
我们了解到:
1.出队列,只能从队头 出队入队列, 只能加到队尾,不能插队2.队中的元素不做修改,只能在队头删除,队尾增加元素3.队列 如果队空,不能进行删除
2.队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,
出队列在数组头上出数据,效率会比较低。
// 一个节点typedef struct QListNode{struct QListNode * n ext ;QDataType data ;} QNode ;// 队列的结构typedef struct Queue{QNode * head ;//头指针QNode * tail ;//尾指针} Queue ;
队列所需的接口:
// 初始化队列void QueueInit ( Queue * p q );// 队尾入队列void QueuePush ( Queue * p q , QDataType data );// 队头出队列void QueuePop ( Queue * p q );// 获取队头元素QDataType QueueFront ( Queue * p q );// 获取队尾元素QDataType QueueBack ( Queue * p q );// 获取队列中有效元素个数size_t QueueSize(Queue* pq)// 检测队列是否为空,如果为空返回非零结果,如果非空返回 0bool QueueEmpty ( Queue * p q );// 销毁队列void QueueDestroy ( Queue * p q );
代码实现:
#include<stdio.h>
#include<Stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data; //存储数据
struct QueueNode* next; //记录下一个节点
}QNode;
//保存队头和队尾
typedef struct Queue
{
QNode* head; //头指针
QNode* tail; //尾指针
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
//销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;//指针置空
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点
assert(newnode);
newnode->next = NULL;
newnode->data = x;
if (pq->tail == NULL)//空队列则两其头尾均指向新节点
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);//头尾均不能为空
if (pq->head->next == NULL)//当只有一个节点时
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;//等于空 为真
//不等于空 为假
}
//获取有效元素个数
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
//获取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);//头不能为空才可以获取头部数据
return pq->head->data;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
对代码进行检验:
分享到这里,谢谢!!