棧和隊列修煉指南

1. 棧

1. 1 概念及結構

• 棧：是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素的操作。進行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端為棧底。

• 棧中的數(shù)據(jù)元素遵守后進先出原則(LIFO)原則

• 壓棧：棧的插入操作稱為進棧/壓棧/入棧，其位置在棧頂

• 出棧：棧的刪除操作稱為出棧，其位置也在棧頂

1.2 分類（數(shù)組棧和鏈式棧）

數(shù)組棧（推薦方式，因為在數(shù)組尾插代價更小）

鏈式棧：相較數(shù)組棧無優(yōu)勢，且一般將鏈表尾作為棧底，鏈表頭作為棧頂（單鏈表情況下）

1.3 數(shù)組棧

1.3.1 結構的定義

typedef int STElemType;
typedef struct Stack
{STElemType *data;	//動態(tài)棧int top;int capacity;
}ST;

1.3.2 初始化

void StackInit(ST *pt)
{pt->data = (SElemType *)malloc(N*sizeof(SElemTyp  e));if (!pt->data){perror("malloc");exit(1);}pt->capacity = N;	//N表示初始的最大容量pt->top = 0;	//此時top指向的是棧頂元素的下一個位置，也可以定義為pt->top=-1,這樣，top就是指向棧頂元素
} 

1.3.3 銷毀

void StackDestroy(ST *pt)
{free(pt->data);pt->top=pt->capacity=0;
} 

1.3.4 判斷棧是否為空

bool StackEmpty(ST *pt)
{return pt->top==0; 	//若為真即棧為空，則返回1，否則返回0
} 

1.3.5入棧

void StackPush(ST *pt,SElemType x)
{if(pt->top==pt->capacity)			//如果容量已滿{pt->capacity *= 2;		//將容量擴為原來的兩倍ST* temp = realloc(pt->data, pt->capacity*sizeof(SElemType));if(!temp){perror("malloc");exit(1);}pt->data = temp;}//入棧pt->data[pt->top]=x;pt->top++;
}

1.3.6 出棧

void StackPop(ST *pt) 
{assert(!stackEmpty(pt));	//棧不能為空//出棧pt->top--;
}

1.3.7 返回棧頂元素

SElemType StackTop(ST *pt)
{assert(!stackEmpty(pt));	//棧不能為空return pt->data[pt->top-1]; 
} 

1.3.8 返回棧的元素個數(shù)

int StackSize(ST *pt)
{return pt->top;
} 

1.3.9 將棧的元素全部取出

void StackPrint(ST *pt)
{assert(!stackEmpty(pt));	//棧不能為空while(!StackEmpty(pt)){printf("%d ",StackTop(pt));	//遵循先入后出原則，從上往下取pt->top--;}
} 

1.4 練習

學習完棧的基本概念和相關操作后，你可以利用棧的特性做下面的OJ題：

有效括號序列👉題目解析

逆波蘭表達式求值👉題目解析

刪除字符串中的所有相鄰重復項👉題目解析

包含min函數(shù)的棧👉題目解析

---

2. 隊列

2.1 概念及結構

• 隊列：只允許在一端進行入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表
• 遵循先進先出的原則FIFO
• 入隊列：進行插入操作的一段叫做隊尾
• 出隊列：進行刪除操作的一段叫做隊頭
  

2.2. 分類（數(shù)組隊列和鏈隊列）

數(shù)組隊列：由于出隊列出的是隊頭元素，因此數(shù)組隊列出數(shù)據(jù)的效率低下，不推薦使用

鏈隊列：入和出數(shù)據(jù)的效率都很高，是隊列常用的表示法

2.3 鏈隊列

2.3.1 結構的定義

typedef int QDataType;	//存儲的數(shù)據(jù)類型typedef struct QueueNode	//鏈隊列的節(jié)點
{struct QueueNode *next;QDataType data;
}QueueNode;typedef struct Queue	//定義存放指向隊頭，隊尾指針的結構體
{QueueNode *head;	//指向隊頭QueueNode *tail;	//指向隊尾
}Queue;

2.3.2 初始化

void QueueInit(Queue *pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}

2.3.3 銷毀

void QueueDestroy(Queue *pq)
{QueueNode *cur = pq->head;	//定義臨時變量while (cur){  pq->head = pq->head->next;	//鏈表下滑free(cur);		//釋放空間cur = pq->head;	//更新臨時變量} pq->tail = NULL;	//空間釋放完畢后head已經(jīng)為空，但tail成為了野指針，所以要置空
}

2.3.4 判斷隊列是否為空

bool QueueEmpty(Queue *pq) 
{assert(pq);return pq->head == NULL;
}

2.3.4 入隊

void QueuePush(Queue *pq,QDataType x)
{assert(pq);QueueNode *newnode=(QueueNode *)malloc(sizeof(QueueNode));		//創(chuàng)建新節(jié)點if (NULL == newNode){perror("malloc");exit(1);}newnode->data=x;newnode->next=NULL;if(QueueEmpty(pq))	//如果隊列為空{pq->head=newnode;	//使隊頭、隊尾指針同時指向新節(jié)點pq->tail=newnode;}else{pq->tail->next=newnode;	//使隊尾指針的指向下一個節(jié)點的指針指向新節(jié)點pq->tail=newnode;	//更新隊尾指針}
}

2.3.5 出隊

void QueuePop(Queue *pq) 
{assert(pq);assert(!QueueEmpty(pq));	//隊列不能為空QueueNode *cur=pq->head;	//定義臨時變量保存隊頭指針pq->head=pq->head->next;	//使隊頭指針指向下一個節(jié)點free(cur);		//釋放原來的隊頭if(pq->head==NULL)pq->tail=NULL;	//如果節(jié)點已經(jīng)全部出隊，則要將隊尾指針置空，防止形成野指針
}

2.3.6 返回隊頭/隊尾數(shù)據(jù)域

//返回隊頭元素
QDataType QueueFront(Queue *pq)	 
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//返回隊尾元素 
QDataType QueueBack(Queue *pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

2.3.7 返回隊列元素個數(shù)

int QueueSize(Queue *pq)
{QueueNode *cur=pq->head;int size=0;while(cur){size++;cur=cur->next;}return size;
}
//也可以在隊列結構體中增加size變量，每入隊一個size就加一

2.4 練習

隊列常常被用來對一些復雜數(shù)據(jù)結構的廣度優(yōu)先遍歷，但由于目前還未學習，故不作深入討論

除了這種最基本的只能從隊尾插入數(shù)據(jù)，從隊頭刪除數(shù)據(jù)的隊列外，其實還有循環(huán)隊列、雙端隊列、單調(diào)隊列等許多復雜但功能強大的隊列結構，如果小伙伴們感興趣，也可以看看：

👉循環(huán)隊列

👉雙端隊列 & 單調(diào)隊列

如果小伙伴們愿意挑戰(zhàn)，也可以做一做滑動窗口的最大值👉題目解析

---

3. 棧和隊列的相互表示

這里拿兩道OJ題來進行說明：

用兩個棧表示隊列👉題目解析

用兩個隊列表示棧👉題目解析