三、棧和隊列 | 數據結構

來自專欄 輕鬆跨考計算機專業研究生入學考試

一、棧和隊列的基本概念

1、棧的基本概念

棧的定義：一種只能在一端進行插入和刪除操作的線性表。可以進行操作的一端叫做棧頂，另一端叫做棧底。棧的刪除和插入操作一般叫做進棧和出棧。

2、棧的特點

先進後出（FILO）

3、棧的存儲結構

一般有兩種：鏈式棧和順序棧。可以理解成在操作上加以限制的鏈表和順序表。

4、棧的數學性質：Catalan數

二、棧和隊列的存儲結構、演算法和應用

1、棧和隊列結構體定義

1）順序棧

typedef struct { int data[maxSize]; int top;}Sqstack;

2）鏈棧結點定義

typedef struct LNode{ int data; struct LNode*next;}LNode;

3）順序隊列定義

typedef struct { int data[maxSize]; int front; int rear;}SqQueue;

4）鏈隊定義

a、鏈隊結點

typedef struct QNode{ int data; struct QNode*next;}QNode;

b、鏈隊類型

typedef struct{ QNode*front; QNode*rear;}LiQueue;

2、順序棧

1）順序棧的幾個要素

a、幾個狀態：

I、棧為空：st.top==-1（從0開始存儲）

II、棧為滿：st.top==maxSize-1

III、上溢：棧滿時繼續入棧就會發生上溢的狀態。

IV、下溢：棧空時繼續出棧就會發生下溢的狀態。

b、兩個操作

I、進棧：st.data[++st.top]=x;

II、出棧：x=st.data[st.top---];

2）初始化棧的代碼

void initStack(Sqstack& st){ st.top=-1;}

3）判斷棧空的代碼

int isEmpty(Sqstack& st){ if(st.top==-1)return 1; else return 0;}

4）進棧代碼

int push(Sqstack& st,int x){ if(-1==st.top)return 0; st.data[++st.top]=x; return 1;}

5）出棧代碼

int pop(Sqstack& st,int &x){ if(-1==st.top)return 0; x=st.data[st.top--]; return 1;}

3、棧鏈

1）鏈棧的定義

a、兩個狀態

I、棧空：lst->next==NULL;

II、棧滿：不存在棧滿的情況（假設內存無限大的情況）

2）鏈棧的初始化

void initStack(LNode* &lst){ lst=(LNode*)malloc(sizeof(LNode));//創造一個頭結點 lst->next=NULL;}

3）判斷棧為空

int isEmpty(LNode* lst){ if(NULL==lst->next)return 1; else return 0;}

4）進棧代碼

void push(LNode* &lst,int x){ LNode* p=(LNode*)malloc(sizeof(LNode)); p->data=x; p->next=NULL;//將新節點指針域置NULL，可以避免一些錯誤 p->next=lst->next; lst->next=p;}

5）出棧代碼

int pop(LNode* &lst,int &x){//出棧數據保存於x if(NULL==lst->next)return 0; LNode*p=lst->next; lst->next=lst->next->next; x=p->data; free(p); return 1;}

4、棧的應用

1）括弧匹配Valid Parentheses - LeetCode

2）求逆波蘭表達式POJ 2694：逆波蘭表達式

5、順序隊

1）循環隊列

隊列的front指針指向剛出隊的元素，rear指針指向剛入隊的元素。隊列進隊時rear+=1，出隊時，front+=1，兩個指針最終會到達maxSize-1處，雖然隊中已經沒有元素，但無法讓元素進隊，這就是假溢出。

為了解決這個問題，可以將隊列的尾部和頭部連接起來，弄成一個環，如圖。

2）循環隊列要素

a、兩個狀態

I、隊空：qu.rear==qu.front

II、隊滿：(qu.rear+1)%maxSize==qu.front

b、兩個操作

I、進隊：qu.rear=(qu.rear+1)%maxSize; qu.data[qu.rear]=x;

II、出隊：qu.front=(qu.front+1)%maxSize;x=qu.data[qu.front];

3）初始化隊列

void initQueue(SqQueue &qu){ qu.front=qu.rear;}

4）判斷隊列是否為空

int isEmpty(SqQueue &qu){ if(qu.front==qu.rear)return 1; else return 0;}

5）進隊

int enQueue(SqQueue &qu,int x){ if(qu.front==qu.rear)return 0; qu.rear=(qu.rear+1)%maxSize; qu.data[qu.rear]=x; return 1;}

6）出隊

int deQueue(SqQueue &qu,int &x){ if(qu.front==qu.rear)return 0; qu.front=(qu.front+1)%maxSize; x=qu.data[qu.front]; return 1;}

6、鏈隊

1）鏈隊的要素

a、兩個狀態：

I、隊為空：lqu->front==NULL||lqu->rear==NULL

II、隊為滿：不存在隊滿（假設內存無限）

b、兩個操作

I、p進隊：lqu->rear->next=p;lqu->rear=p;

II、出隊為x：p=lqu->front;x=p->data;lqu->front=lqu->front->next;

2）初始化鏈表

void initQueue(LiQueue* &lqu){ lqu=(LiQueue*)malloc(sizeof(LiQueue)); lqu->front=lqu->rear=NULL;}

3）判斷隊空

int isEmpty(LiQueue* lqu){ if(!lqu->front||!lqu->rear)return 1; else return 0;}

4）入隊

void enQueue(LiQueue* lqu,int x){ QNode*p=(QNode*)malloc(sizeof(QNode)); p->data=x; p->next=NULL; if(!lqu->front||!lqu->rear) lqu->front=lqu->rear=p; else{ lqu->rear->next=p; lqu->rear=p; }}

5）出隊

int deQueue(LiQueue* lqu,int &x){ if(!lqu->front||!lqu->rear)return 0; QNode*p=lqu->front; x=p->data; if(lqu->front==lqu->rear) lqu->front=lqu->rear=NULL; else lqu->front=lqu->front->next; free(p); return 1;}

三、抽象數據類型

Wiki：抽象數據類型（Abstract Data Type，ADT）是計算機科學中具有類似行為的特定類別的數據結構的數學模型；或者具有類似語義的一種或多種程序設計語言的數據類型。

可以理解成API的功能定義清晰，但不考慮演算法的實現以及存儲方式的數據結構。

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

推薦閱讀：