數據結構復習總結第三章棧和隊列

　　第三章棧和隊列

　　棧

　　棧的定義及基本運算

　　棧是限制僅在表的一端進行插入和刪除運算的線性表又稱為後進先出表(LIFO表)插入刪除端稱為棧頂另一端稱棧底表中無元素稱空棧基本運算有

　　) initstack(s)構造一個空棧;

　　) stackempty(s)判棧空;

　　) stackfull(s)判棧滿;

　　) push(sx)進棧;

　　) pop (s)退棧;

　　) stacktop(s)取棧頂元素

　　順序棧

　　棧的順序存儲結構稱順序棧順序棧的類型定義為

　　#define stacksize

　　typedef char datatype;

　　typedef struct{

　　datatype data[stacksize];

　　int top;

　　}seqstack;

　　當棧滿時做進棧運算必定產生空間溢出稱上溢 當棧空時做退棧運算必定產生空間溢出稱下溢上溢是一種錯誤應設法避免下溢常用作程序控制轉移的條件

　　在順序棧上的基本運算

　　) 置空棧

　　Void initstack(seqstack *s)

　　{

　　s>top=;

　　}

　　)判棧空

　　int stackempty(seqstack *s)

　　{

　　return s>top==;

　　}

　　)判棧滿

　　int stackfull(seqstack *s)

　　{

　　return s>top==stacksize;

　　}

　　)進棧

　　Void push(seqstack *sdatatype x)

　　{

　　if(stackfull(s))

　　error(stack overflow);

　　s>data[++s>top]=x;

　　}

　　)退棧

　　Datatype pop(seqstack *s)

　　{

　　if(stackempty(s))

　　error(stack underflow);

　　return S>data[s>top];

　　}

　　)取棧頂元素

　　Dtatatype stacktop(seqstack *s)

　　{

　　if(stackempty(s))

　　error(stack underflow);

　　return S>data[s>top];

　　}

　　鏈棧

　　棧的鏈式存儲結構稱鏈棧棧頂指針是鏈表的頭指針鏈棧的類型定義

　　typedef struct stacknode{

　　datatype data;

　　struct stacknode *next;

　　}stacknode;

　　typedef struct{

　　stacknode *top;

　　}linkstack;

　　鏈棧上的基本運算

　　) 建棧

　　Void initstack(linkstack *s)

　　{

　　s>top=NULL;

　　}

　　)判棧空

　　Int stackempty (linkstack *s)

　　{

　　return s>top==NULL;

　　}

　　) 進棧

　　Void push(linkstack *sdatatype x)

　　{

　　stacknode *p=(stacknode *)malloc(sizeof(stacknode));

　　p>data=x;

　　p>next=s>top;

　　s>top=p;

　　}

　　) 退棧

　　Datatype pop(linksatck *s)

　　{

　　datatype x;

　　stacknode *p=s>top;

　　if(stackempty(s))

　　error(stack underflow);

　　x=p>data;

　　s>top=p>next;

　　free(p);

　　return x;

　　}

　　) 取棧頂元素

　　Datatype stacktop(linkstack *s)

　　{

　　if(stackempty(s))

　　error(stack is empty);

　　return s>top>data;

　　}

　　隊列

　　隊列的基本定義和計算

　　隊列是一種運算受限的線性表允許刪除的一端稱隊首允許插入的一端稱隊尾隊列又稱為先進先出線性表FIFO表

　　隊列的基本運算

　　) initqueue(q)置空隊;

　　) queueempty(q)判隊空;

　　) queuefull(q)判隊滿;

　　) enqueue(qx)入隊;

　　) dequeue(q)出隊;

　　) queuefront(q)返回隊頭元素

　　順序隊列

　　隊列的順序存儲結構稱順序隊列設置front和rear指針表示隊頭和隊尾元素在向量空間的位置順序隊列中存在假上溢現象由於入隊和出隊操作使頭尾指針只增不減導致被刪元素的空間無法利用隊尾指針超過向量空間的上界而不能入隊

　　為克服假上溢現象將向量空間想象為首尾相連的循環向量存儲在其中的隊列稱循環隊列i=(i+)%queuesize

　　循環隊列的邊界條件處理由於無法用front==rear來判斷隊列的空和滿解決的方法有

　　) 另設一個布爾變量以區別隊列的空和滿;

　　) 少用一個元素在入隊前測試rear在循環意義下加是否等於front;

　　) 使用一個記數器記錄元素總數

　　循環隊列的類型定義

　　#define queuesize

　　typedef char datatype;

　　typedef struct{

　　int front;

　　int rear;

　　int count;

　　datatype data[queuesize];

　　}cirqueue;

　　) 置隊空

　　Void initqueue(cirqueue *q)

　　{

　　q>front=q>rear=;

　　q>count=;

　　}

　　) 判隊空

　　Int queueempty(cirqueue *q)

　　{

　　return q>count==;

　　}

　　) 判隊滿

　　Int queuefull(cirqueue *q)

　　{

　　return q>count==queuesize;

　　}

　　) 入隊

　　Void enqueue(cirqueue *q datatype x)

　　{

　　if(queuefull(q))

　　error(queue overfolw);

　　q>count++;

　　q>data[q>rear]=x;

　　q>rear=(q>rear+)%queuesize;

　　}

　　) 出隊

　　Datatype dequeue(cirqueue *q)

　　{

　　datatype temp;

　　if(queueempty(q))

　　error(queue underflow);

　　temp=q>data[q>front];

　　q>count;

　　q>front=(q>front+)%queuesize;

　　return temp;

　　}

　　) 取隊頭元素

　　Datatype queuefront(cirqueue *q)

　　{

　　if(queueempty(q))

　　error(queue is empty);

　　return q>data[q>front];

　　}

　　鏈隊列

　　隊列的鏈式存儲結構稱鏈隊列鏈隊列由一個頭指針和一個尾指針唯一確定

　　鏈隊列的定義

　　typedef struct queuenode

　　{

　　datatype data;

　　struct queue *next;

　　}queuenode;

　　typedef struct

　　{

　　queuenode *front;

　　queuenode *rear;

　　}linkqueue;

　　) 建空隊

　　Void initqueue(linkqueue *q)

　　{

　　q>front=q>rear=NULL;

　　}

　　) 判隊空

　　Int queueempty(linkqueue *q)

　　{

　　return q>front==NULL&&q>rear==NULL;

　　}

　　) 入隊

　　Void enqueue(linkqueue *qdatatype x)

　　{

　　queuenode *p=(queuenode *)malloc(sizeof(queuenode));

　　p>data=x;

　　p>next=NULL;

　　if(queueempty(q))

　　qfront=q>rear=p;

　　else{

　　q>rear>next=p;

　　q>rear=p;

　　}

　　}

　　) 出隊

　　Datatype dequeue(linkqueue *q)

　　{

　　datatype x;

　　queuenode *p;

　　if(queueempty(q))

　　error(queue is underflow);

　　p=q>front;

　　x=p>data;

　　q>front=p>next;

　　if(q>rear==p) q>rear=NULL;

　　free(p);

　　return x;

　　}

　　) 取隊頭元素

　　Datatype queuefront(linkqueue *q)

　　{

　　if(queueempty(q))

　　error(queue is empty);

　　return q>front>data;

　　}

　　附二:

　　第三章 棧和隊列

　　*************************************************************************************

　　棧(Stack)是僅限制在表的一端進行插入和刪除運算的線性表稱插入刪除這一端為棧頂另一端稱為棧底表中無元素時為空棧棧的修改是按後進先出的原則進行的我們又稱棧為LIFO表(Last In First Out)通常棧有順序棧和鏈棧兩種存儲結構

　　*************************************************************************************

　　棧的基
From:http://tw.wingwit.com/Article/program/sjjg/201311/23754.html