栈(stack)与队列(queue)
Stack
栈的定义：
特殊的线性表 一般指的是顺序栈
栈是限定仅在```表尾```进行插入和删除操作的线性表(后进先出) ；
栈的抽象数据类型：
ADT 栈(stack)
Data
同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
InitStack(*S): 初始化栈，建立一个空栈；
DestroyStack(*S): 销毁栈；
ClearStack(*S): 将栈清空；
StackEmpty(S): 判断栈是否为空，若为空，则返回true，否则返回false；
GetTop(S,*e): 用e返回栈顶元素；
Push(*S,e): 入栈；插入新元素e到栈顶；
Pop(*S,*e): 出栈；删除栈顶元素，用e返回其值；
StackLength(S): 返回栈S的元素个数 。
endADT
顺序栈的结构定义
#define STACK_INIT_SIZE 20
typedef char SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int StackSize;
}sqStack;
/*
typedef char SElemType;
typedef struct{
SElemType data[MAXSIZE] ;
SElemtype *top;
}sqStack;
*/
初始化
// 初始化操作，建立一个新的空栈
void InitStack(sqStack *S) {
S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if( !S->base){
exit(0);
}
S->top = S->base;
S->StackSize = STACK_INIT_SIZE;
}
进栈操作：
// 插入元素e为新的栈顶元素
Status Push(sqStack *S,SElemType e){
if(S->top - S->base >= S->StackSize){
S->base = (SElemType *)realloc(S->base,(S->StackSize + STACK_INIT_SIZE) * sizeof(SElemType));
if( !S->base){
exit(0);
}
}
*(S->top) = e;
S->top++;
return OK;
}
出栈操作：
// 删除栈顶元素，用e返回其值
Status Pop(sqStack *S,SElemType *e){
if(S->base == S->top){
return;
}
S->top--;
*e = *S->top;
}
Queue
队列的定义
另一种特殊的线性表 一般指的是链队列
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。(先进先出)
队列的抽象数据类型：
ADT 队列(Queue)
Data
同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
InitQueue(*Q): 初始化操作，建立一个空队列；
DestroyQueue(*Q): 销毁队列Q；
ClearQueue(*Q): 将队列Q清空；
GetHead(Q,*e): 用e返回队列的队头元素；
InsertQueue(*Q,e): 插入新元素e到队列Q中并成为队尾元素；
DeQueue(*Q,*e): 删除队列中的队头元素，并用e返回其值；
QueueLength(Q): 返回队列Q的元素个数
endADT
链队列的结构定义
typedef int QElemType;
typedef struct QNode{ //结点结构
QELemType data;
sturct QNode *next;
}QNode,*QueuePtr;
typedef struct{ //队列的链表结构
QueuePtr front,rear;
}LinkQueue;
初始化操作
step1:创建一个头结点；
step2:将队列的头指针和尾指针都指向这个生成的头结点（空链队列）
// 初始化操作，建立一个新链队列
void InitQueue(LinkQueue *q) {
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)) ;
if( !q->front) {
exit(0);
}
q->front->next = NULL;
}
入队列操作
图例：
入队列
// 插入元素e为新的队尾元素
Status InsertQueue(LinkQueue *Q,QElemType 2) {
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if( !p ){
exit(0);
}
p->data = e;
p->next = NULL;
Q->rear->next = p;//把拥有元素e的新结点p赋值给原队尾结点的后继
Q->rear = p;//把当前的p设置为队尾结点，rear指向s。
return OK;
}
出队列操作
图例：
出队列
出队列
// 删除Q的队头元素，用e返回其值
Status DeleteQueue(LinkQueue *Q,QElemType *e){
QueuePtr p;
if( Q->front == Q->rear)
return ;
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if( Q->rear == p)
Q->rear = Q->front;
free(p);
retuen OK;
}
销毁队列
// 销毁一个队列
void DestroyQueue(LinkQueue *Q)
{
while( Q->front){
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
}
