棧(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;
    }
}