肖鴻昌建筑網(wǎng)站寧波網(wǎng)絡營銷推廣公司
棧和隊列修煉指南
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題來進行說明:
用兩個棧表示隊列👉題目解析
用兩個隊列表示棧👉題目解析