棧(stack)與隊(duì)列(queue)
Stack
棧的定義：
特殊的線性表 一般指的是順序棧
棧是限定僅在```表尾```進(jìn)行插入和刪除操作的線性表(后進(jìn)先出) 妨马；
棧的抽象數(shù)據(jù)類型：
ADT 棧(stack)
Data
同線性表。元素具有相同的類型雳锋，相鄰元素具有前驅(qū)和后繼關(guān)系
Operation
InitStack(*S): 初始化棧捡硅，建立一個(gè)空棧敢课；
DestroyStack(*S): 銷毀棧追他；
ClearStack(*S): 將棧清空绎签；
StackEmpty(S): 判斷棧是否為空震捣，若為空荔棉，則返回true，否則返回false伍派；
GetTop(S,*e): 用e返回棧頂元素江耀；
Push(*S,e): 入棧剩胁；插入新元素e到棧頂诉植；
Pop(*S,*e): 出棧秕噪；刪除棧頂元素衰粹，用e返回其值捻脖；
StackLength(S): 返回棧S的元素個(gè)數(shù) 并蝗。
endADT
順序棧的結(jié)構(gòu)定義
#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;
*/
初始化
// 初始化操作决左，建立一個(gè)新的空棧
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;
}
進(jìn)棧操作：
// 插入元素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
隊(duì)列的定義
另一種特殊的線性表 一般指的是鏈隊(duì)列
隊(duì)列是只允許在一端進(jìn)行插入操作围详，而在另一端進(jìn)行刪除操作的線性表焰盗。(先進(jìn)先出)
隊(duì)列的抽象數(shù)據(jù)類型：
ADT 隊(duì)列(Queue)
Data
同線性表觉至，元素具有相同的類型剔应，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
InitQueue(*Q): 初始化操作，建立一個(gè)空隊(duì)列峻贮；
DestroyQueue(*Q): 銷毀隊(duì)列Q席怪；
ClearQueue(*Q): 將隊(duì)列Q清空；
GetHead(Q,*e): 用e返回隊(duì)列的隊(duì)頭元素纤控；
InsertQueue(*Q,e): 插入新元素e到隊(duì)列Q中并成為隊(duì)尾元素挂捻；
DeQueue(*Q,*e): 刪除隊(duì)列中的隊(duì)頭元素，并用e返回其值船万；
QueueLength(Q): 返回隊(duì)列Q的元素個(gè)數(shù)
endADT
鏈隊(duì)列的結(jié)構(gòu)定義
typedef int QElemType;
typedef struct QNode{ //結(jié)點(diǎn)結(jié)構(gòu)
QELemType data;
sturct QNode *next;
}QNode,*QueuePtr;
typedef struct{ //隊(duì)列的鏈表結(jié)構(gòu)
QueuePtr front,rear;
}LinkQueue;
初始化操作
step1:創(chuàng)建一個(gè)頭結(jié)點(diǎn)刻撒；
step2:將隊(duì)列的頭指針和尾指針都指向這個(gè)生成的頭結(jié)點(diǎn)（空鏈隊(duì)列）
// 初始化操作，建立一個(gè)新鏈隊(duì)列
void InitQueue(LinkQueue *q) {
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)) ;
if( !q->front) {
exit(0);
}
q->front->next = NULL;
}
入隊(duì)列操作
圖例：
入隊(duì)列
// 插入元素e為新的隊(duì)尾元素
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的新結(jié)點(diǎn)p賦值給原隊(duì)尾結(jié)點(diǎn)的后繼
Q->rear = p;//把當(dāng)前的p設(shè)置為隊(duì)尾結(jié)點(diǎn)耿导，rear指向s声怔。
return OK;
}
出隊(duì)列操作
圖例：
出隊(duì)列
出隊(duì)列
// 刪除Q的隊(duì)頭元素，用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;
}
銷毀隊(duì)列
// 銷毀一個(gè)隊(duì)列
void DestroyQueue(LinkQueue *Q)
{
while( Q->front){
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
}
