栈和队列是两种常用的，重要的数据结构
栈和队列是限定插入和删除只能在表的“端点”进行的线性表
栈和队列是线性表的子集（是插入和删除位置受限的线性表）
栈
定义：只能在表的一端（栈顶）进行插入和删除运算的线性表
逻辑结构：与线性表相同，仍为一对一关系
存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见
运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则
头文件和宏定义
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
typedef char StackElemType;//栈数据类型
顺序栈的表示
typedef struct {
StackElemType* base;//栈底指针
StackElemType* top;//栈顶指针
int stacksize;//栈可用最大容量
}SqStack;
顺序栈的初始化
步骤：1.分配空间并检查空间是否分配失败，若失败则返回错误
2.设置栈底和栈顶指针
3.设置栈大小
Status InitStack(SqStack* s)//构造一个空栈
{
s->base = (StackElemType*)malloc(sizeof(StackElemType) * MAXSIZE);
if (!s->base)//存储分配失败
exit(OVERFLOW);
s->top = s->base;//栈顶指针等于栈底指针
s->stacksize = MAXSIZE;//栈的容量
return OK;
}
图片来自于青岛大学–王卓老师的PPT截图
顺序栈判断栈是否为空
Status StackEmpty(SqStack s)
{//若栈为空，返回TRUE;否则返回FALSE
if (s.base == s.top)
{
return TRUE;
}
else
return FALSE;
}
求顺序栈长度
Status StackLength(SqStack s)
{
return s.top - s.base;
}
图片来自于青岛大学–王卓老师的PPT截图
清空顺序栈
Status ClearStack(SqStack s)
{
if (s.base)
{
s.top = s.base;
}
return OK;
}
销毁顺序栈
Status DestroyStack(SqStack* s)
{
if (s->base)
{
free(s->base);
s->stacksize = 0;
s->base = s->top = NULL;
}
return OK;
}
顺序栈的入栈
Status Push(SqStack* s, StackElemType e)
{
if (s->top - s->base == s->stacksize)
return ERROR;
*(s->top) = e;
s->top++; //*(s->top++)=e;
return OK;
}
顺序栈的出栈
Status Pop(SqStack* s, StackElemType* e)
{//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if (s->base == s->top)
return ERROR;
*e = *(--(s->top));
return OK;
}
图片来自于青岛大学–王卓老师的PPT截图
链栈的表示
运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针
typedef struct StackNode {
StackElemType data;
struct StackNode* next;
}StackNode,*LinkStack;
图片来自于青岛大学–王卓老师的PPT截图
链栈初始化
Status InitStack_chain(LinkStack* S)
{//构造一个空栈，栈顶指针置为空
*S = NULL;
return OK;
}
判断链栈是否为空
Status StackEmpty_chain(LinkStack S)
{
if (S == NULL)
return TRUE;
else
return FALSE;
}
链栈的入栈
Status Push_chain(LinkStack* S,StackElemType e)
{
LinkStack p = (LinkStack)malloc(sizeof(StackNode));//生成新结点p
p->data = e;//将新结点数据域置为e
p->next = *S;//将新结点插入栈顶
*S = p;//修改栈顶指针
return OK;
}
图片来自于青岛大学–王卓老师的PPT截图
链栈的出栈
Status Pop_chain(LinkStack* S, StackElemType* e)
{
if (*S == NULL)
return ERROR;
LinkStack p = *S;
*e = (* S)->data;
*S = (*S)->next;
free(p);
return OK;
}
图片来自于青岛大学–王卓老师的PPT截图
取栈顶元素
StackElemType GetTop(LinkStack S)
{
if (S != NULL)
return S->data;
}
队列
定义：只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表
逻辑结构：与线性表相同，仍为一对一关系
存储结构：用顺序队列或链队存储均可
运算规则：先进先出（FIFO）
头文件和宏定义
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef char QElemType;
#define MAXQSIZE 100//最大队列长度
队列的顺序表示
typedef struct {
QElemType* base;//初始化的动态分配存储空间
int front;//头指针
int rear;//尾指针
}SqQueue;
图片来自于青岛大学–王卓老师的PPT截图
队列的初始化
Status InitQueue(SqQueue* Q)
{
Q->base= (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);//分配存储空间
if (!Q->base)//存储分配失败
exit(OVERFLOW);
Q->front = 0;//头指针尾指针置为0，队列为空
Q->rear = 0;
return OK;
}
求队列长度
int QueueLength(SqQueue Q)
{
return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
循环队列入队
Status EnQueue(SqQueue* Q, QElemType e)
{
if ((Q->rear + 1) % MAXQSIZE == Q->front)//队满
return ERROR;
Q->base[Q->rear] = e;//新元素加入对尾
Q->rear = (Q->rear + 1) % MAXQSIZE;//队尾指针加一
return OK;
}
循环队列出队
Status DeQueue(SqQueue* Q, QElemType* e)
{
if (Q->front == Q->rear)//队空
{
return ERROR;
}
*e = Q->base[Q->front];//保存队头元素
Q->front = (Q->front + 1) % MAXQSIZE;//队头元素加一
return OK;
}
取队头元素
QElemType GetHead(SqQueue Q)
{
if (Q.front != Q.rear)//队列不为空
{
return Q.base[Q.front];//返回队头指针元素的值，队头指针不变
}
}
判断循环队列是否为空
Status IsEmpty_Sq(SqQueue* Q)
{
if (Q->front == Q->rear)
return TRUE;
else
return FALSE;
}
判断循环队列是否队满
Status IsFull_Sq(SqQueue* Q)
{
if ((Q->rear + 1) % MAXQSIZE == Q->front)
return TRUE;
else
return FALSE;
}
链队数据类型定义
//链队 //有头结点
//链队数据类型定义
typedef struct Qnode {
QElemType data;
struct Qnode* next;
}Qnode,*Qnode_L;
typedef struct LinkQueue {
Qnode_L front;//队头指针
Qnode_L rear;//队尾指针
}LinkQueue;
图片来自于青岛大学–王卓老师的PPT截图
链队列初始化
图片来自于青岛大学–王卓老师的PPT截图
Status InitQnode(LinkQueue* Q)
{
Q->front = Q->rear=(Qnode_L)malloc(sizeof(Qnode));
if (!Q->front)
exit(OVERFLOW);
Q->front->next = NULL;
return OK;
}
销毁链队列
Status DestroyQnode(LinkQueue* Q)
{
while (Q->front)
{
Qnode_L p = Q->front->next;
free(Q->front);
Q->front = p;
}
return OK;
}
链队入队
Status EnQnode(LinkQueue* Q,QElemType e)
{
Qnode_L S = (Qnode_L)malloc(sizeof(Qnode));
if (!S)
exit(OVERFLOW);
S->data = e;
Q->rear->next = S;
S->next = NULL;
Q->rear = S;
return OK;
}
链队列出队
Status DeQnode(LinkQueue* Q, QElemType* e)
{
if (Q->front == Q->rear)
return ERROR;
Qnode_L p= Q->front->next;
*e = Q->front->next->data;
Q->front->next = Q->front->next->next;
if (p == Q->rear)
{
Q->front = Q->rear;
}
free(p);
return OK;
}
求链队列的队头元素
Status GetTopQnode(LinkQueue* Q, QElemType* e)
{
if (Q->front == Q->rear)
return ERROR;
*e = Q->front->next->data;
return OK;
}