堆疊與佇列

堆疊

什么是堆疊？

1. 堆疊（stack）是限定僅在表尾進行插入和洗掉操作的線性表，又被稱為后進先出的線性表，簡稱LIFO結構，

2. 堆疊是一個線性表，具有線性關系，我們把允許插入和洗掉的一端稱為堆疊頂（top)，另一端稱為堆疊底（bottom），

3. 堆疊的插入操作叫作進堆疊，堆疊的洗掉操作叫作出堆疊，如下動圖所示：

堆疊的順序存盤結構及實作

堆疊的結構體定義

typedef int SElemType
typedef struct Stack
{
    SElemType data[MAXSIZE];
    int top; //堆疊頂指標
}Stack;

進堆疊操作

//進堆疊
bool StackPush(Stack* s, SElemType x)
{
	if (s->size == MAXSIZE - 1) 
	{
		printf("堆疊滿!");
		return false;
	}

	s->size++;
	s->data[s->size] = x;
	printf("進堆疊成功!");
}

出堆疊操作

//出堆疊
bool StackPop(Stack* s)
{
	if (s->size == -1)
	{
		printf("堆疊空!");
		return false;
	}
	else
	{
		s->size--;
	}
}

兩堆疊共享空間

分析

當我們只有一個堆疊時，必須事先確定儲存空間，但如果儲存資料過多就會造成溢位，這時，我們可以用兩個相同型別的堆疊，并各自開辟一段陣列空間，當一個堆疊溢位時，溢位的資料儲存到另一個堆疊，但這容易造成一堆疊滿，一堆疊空的情況，那么，為了充分為調配好空間，我們可以選擇用一個陣列存盤兩個堆疊來解決這一問題，
如下圖，top1和top2分別表示堆疊1和堆疊2的堆疊頂，陣列長度size=6：

為了方便理解，這里的數字我用的是陣列的下標，陣列的兩端用兩個堆疊的堆疊底來表示，從堆疊1的堆疊底（0）開始，到堆疊2的堆疊底（size-1)結束，但資料進堆疊時，并不是嚴格的從左到右進行填充，當向堆疊2中填充資料時，是從右向左延伸的，即先是5進堆疊，再有4進堆疊，

現在我們來討論兩堆疊的中空堆疊與滿堆疊的情況：
進行討論前，我們要記住，top1+1==top2為堆疊滿這個結論是始終適用的

1. 滿堆疊

   這種情況又可以對堆疊1和堆疊2的狀態進行細分：

   1. 堆疊1和堆疊2都不為空堆疊

      

      注意，top1和top2不一定在中間相遇才是滿堆疊，只要top1和top2相遇就是滿堆疊

   2. 堆疊1為空堆疊==（top1=-1）或者堆疊2為空堆疊（top2=size)==

      

      上圖是堆疊1為空的情況
      

      上圖是堆疊2為空的情況

   綜上分析 ：當滿堆疊時，堆疊1和堆疊2可能都不為空堆疊，但也可能其中一個為空堆疊，但都滿足滿堆疊的結論 top1+1==top2為堆疊滿，

2. 空堆疊

   當堆疊1和堆疊2都為空時，即為空堆疊

   

下面進行代碼的演示

兩堆疊共享空間的結構體定義

typedef int SElemType;
typedef struct DoubleStack
{
	SElemType data[MAXSIZE];
	int top1;	/*堆疊1的堆疊頂指標*/
	int top2;	/*堆疊2的堆疊頂指標*/
}DoubleStack;

進堆疊

//進堆疊
bool DoubleStackPush(DoubleStack* s, SElemType x, int stackNumber)
{
	if (s->top1 + 1 == s->top2)  //滿堆疊
	{
		printf("堆疊滿!");
		return false;
	}
		
	if (stackNumber == 1)  //堆疊1有元素進堆疊
		s->data[++s->top1] = x;
	else if (stackNumber == 2)	//堆疊2有元素進堆疊
		s->data[--s->top2] = x;

	printf("進堆疊完成!");
}

出堆疊

//出堆疊
bool DoubleStackPop(DoubleStack* s, int stackNumber)
{
	if (stackNumber == 1)
	{
		if (s->top1 = -1)
			return false;
		else
			s->top1--;
	}
	else if (stackNumber == 2)
	{
		if (s->top2 == MAXSIZE)
			return false;
		else
			s->top2++;
	}
}

堆疊的鏈式存盤結構及實作

堆疊的鏈式存盤結構

1. 鏈堆疊中有堆疊頂，不需要頭結點，
2. 不存在滿堆疊的情況，
3. 空堆疊也就是top指向NULL的時候，

鏈堆疊的結構體

typedef struct StackNode
{
    SElemType data;
    struct StackNode* next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;	//堆疊頂指標
    int count;			//計數
}LinkStack;

進堆疊

1. 開辟新結點

   LinkStackPtr newNode=(LinkStackPtr)malloc(sizeof(StackNode));
   newNode->data=x;
   

2. 新結點鏈接到堆疊中

   newNode->next=S->top;
   

3. 將新結點賦值給堆疊頂指標

   S->top=newNode;
   S->count++;
   

完整代碼：

bool  StackPush(LinkStack *S, SElemType x)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    newNode->data=e;
    newNode->next=S->top;
    S->top=newNode;
    S->count++;
    return true;
}

出堆疊

bool StackPop(LinkStack *S)
{
    LinkStackPtr p;
    if(S->top==NULL)
        return false;
    else
    {
        newtop=S->p;//將堆疊頂結點賦值給p
        S->top=S->top->next;//堆疊頂指標后移一位
        free(p);
        S->count--;
        return true;
    }
}

堆疊的作用

簡化程式設計問題，使我們的注意力聚焦于要解決問題的核心，

應用（遞回）

斐波那契數列

假設一開始有一對具備繁殖能力的兔子，具有繁殖能力的兔子每個月能生出一對小兔子，且小兔子出生兩個月后就具有繁殖能力，假設所有兔子都不死，那么n年后可以得到多少只兔子呢？

依次類推我們得到如下表格

用數學公式概括：

f ( x ) = { 0 , 當 n = 0 1 , 當 n = 1 F ( n ? 1 ) + F ( n ? 2 ) , 當 n > 1 f(x)=\left\{ \begin{aligned} 0 &,&當n=0\\ 1 & , & 當n=1 \\ F(n-1) & +F(n-2), & 當n>1 \end{aligned} \right. f(x)=??????01F(n?1)?,,+F(n?2),?當n=0當n=1當n>1?

求經過k個月后兔子的對數代碼實作

遞回的終止條件非常重要，給了終止條件，計算機才能進行求解子問題并回溯，最終求出f(x)

int Fbi(int n)
{
    if(n<2)
        return n==0 ? 0 : 1; //若輸入的n=0，回傳0，否則當通過遞回得到n=1時，回傳1
    
    return Fbi(n-1)+Fbi(n-2);//不斷呼叫自己,直到i=1
}
int main()
{
    int k,total;
    scanf("%d",&k);
    printf("第%d個月后兔子的總對數為：%d對\n",k,Fbi(k));
}

對于遞回的題目，不要先去想遞回的程序，而是去找出對應的公式，當公式出來后，遞回的邏輯才會清晰起來，

漢諾塔問題

漢諾塔(Tower of Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，

為了方便后續的理解，我們先分析兩個盤子的情況：

要將A上的盤子移動到C上，一共需要3步，程序如下

下面我們以5個盤子為例進行分析：

現在我們5個盤子從A移動到為C，移動程序中不能出現大的在上小的在下，那么最少需要多少步才能完成？

分析：

如果我們事先把n-1個盤看成一個整體，那么相當于兩個盤，只需要進行三步就可以達到目的，

但很可惜，這個整體并不只有一個盤子，這個整體里面每個盤子的移動可能是不同的，我們現在也無法確定，那么我們可以暫時將這個整體看作一個未知數,這里我們用F(4)表示，于是我們分為以下步驟：

1. 將這n-1個盤子借助借助C先移動到B上(忽略轉移程序)，

   hanoi(n-1,'A','C','B');		//A上的n-1個盤借助C先移動到B上
   

2. 然后把A上剩下的一個盤移到C上，

   move('A','C');
   

3. 把B上的n-1（F(4)）個盤借助A移動到C上，

   hanoi(n-1,'B','A','C');
   

   但現在B上的F(4)，仍然是未知數，因此我們需要進一步把這4個盤看成兩個盤，借助A移到C上，如下圖，我們把這三個盤組成的整體稱為F(3)

? 1. 將F(3)轉移到A上(不要去想轉移程序)

? 2. 然后把B上剩余的盤子轉移到C上

3. 將F(3)移動到C上

但現在F(3)里面的每個盤的移動程序仍然是不確定的，我們又需要分為F(2)加一個底盤，這樣不斷將問題細分，直到得到F(1)，也就是n=1的時候，我們終于找到了終止條件，因為最后一個盤的移動是確定的，不再是未知數，那么既然F(1)已經確定了，那么F(2)也就確定了，因為其中一個盤的移動確定，另一個盤的移動也是確定的，F(2)確定，F(3)也就確定了，就這樣，通過F(1)回溯，前面的未知數都能確定下來了，也就是說每個盤子的移動程序也就確定下來了，

總結：遞回就是不斷將問題細分為一個個子問題，也就是如果我們要求解F(n)，那就先求解F(n-1)，要求解F(n-1),那我先求F(n-2)，······，當細分的子問題達到我的終止條件后，就可以通過回溯求解出前面的大問題，最初我們不必糾結于每一個盤子的移動程序，這些程序最侄訓通過遞回進行解決，

漢諾塔問題代碼實作

#include<stdio.h>

int total; //計數

void move(char A, char C)
{
	printf("step %d:%c --> %c\n", ++total, A, C);
}

void hanoi(int n, char A, char B, char C)//n個盤子在A上，借助B，移動到C上
{
	if (n == 1)//遞回終止條件，如果A上只有一個盤子，直接移動到C上
		move(A, C);
	else
	{
		hanoi(n - 1, A, C, B);//A上的n-1個盤子借助C移動到B上
		move(A, C);			//將A上最后一個盤子移動到C上
		hanoi(n - 1, B, A, C);//將B上的n-1個盤子借助A移動到C上
	}
}

void main()
{
	int n;

	printf("input the number of diskes:");
	scanf_s("%d", &n);
	printf("The step to moving %d diskes:\n", n);

	hanoi(n, 'A', 'B', 'C');
}

佇列

什么是佇列？

佇列（queue）是只允許在一端進行插入操作，而在另一端進行洗掉操作的線性表，也就是說是一種先進先出的線性表，簡稱FIFO，允許插入的一 端稱為隊尾，允許洗掉的一端稱為隊頭，

回圈佇列

佇列順序儲存的不足

佇列和堆疊不一樣，堆疊只在堆疊頂進行插入和洗掉操作，不需要挪動元素，因此時間復雜度始終為O(1)，雖然進佇列操作時間復雜度也為O(1)，但出佇列時，為了保證隊頭不為空，后面的元素都要向前挪動一位，時間復雜度為O(n)，

那么如果我們隊頭的位置用指標front來記錄，這時候就不一定是下標為0的位置，同時用rear記錄隊尾元素的后一位，當front等于rear是，就說明佇列為空，

如果我現在繼續讓新元素入隊，當rear移到陣列之外時，就會發生溢位

但現在陣列實際存盤的元素只有三個，并未達到陣列的存盤上限，下標為0和1的位置還是空的，為了解決這一情況，引入了回圈佇列，

什么是回圈佇列

把佇列頭尾相接的順序存盤結構

當我們繼續入隊a6，a6會放在下標為0的位置

但如果繼續入隊a7,rear就會等于front，但在前面我們認為rear等于front時，佇列為空，為了避免這種情況，我們一般會保留一個空位，這個空位不填充元素

下面我們來設計回圈佇列的程式：

1. 滿列條件，佇列最大長度記為QueueSize

   滿列的情況有兩種：

   1. rear<front

      

      此時滿足 rear+1=front

   2. rear>front

      

      此時滿足 （rear+1）% QueueSize=front

   由于以上兩種情況均符合第二種判斷條件，故將（rear+1）% QueueSize=front作為判斷佇列滿的條件，

2. 佇列長度計算公式(rear-front+QueueSize)% QueueSize

下面我們開始實作代碼

回圈佇列代碼實作

結構體

#define MAXSIZE 6
typedef int QElemType;

typedef struct Queue
{
	QElemType data[MAXSIZE];
	int front;	//頭指標，記錄隊頭的下標
	int rear;	//尾指標，記錄隊尾下一個元素位置的下標
}Queue;

初始化

void InitQueue(Queue* Q)
{
    Q->front=0;	//將頭指標記錄的下標初始化為0
    Q->rear=0;	//將尾指標記錄的下標初始化為0
}

求佇列長度

int QueueLength(Queue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

入佇列

void EnterQueue(Queue *Q,QElemType x)
{
    if(Q->front==Q->rear)
        return 0;
    
    Q->data[Q->rear]=x;				//將x賦值給下標為rear的元素
    Q->rear=(Q->rear+1)%MAXSIZE;	//rear后移一位，若超出陣列，則轉到陣列頭部
}

出佇列

void DeleteQueue(Queue *Q)
{
    if(Q->front==Q->rear)
        return 0;
    
    Q->front=(Q->front+1)%MAXSIZE;//front后移一位，若超出陣列，則轉到陣列頭部
}

佇列的鏈式存盤結構及實作

佇列的鏈式結構和單鏈表一樣，但只能在表尾進表頭出，簡稱為鏈佇列，

鏈佇列的代碼實作

結構體創建

typedef int QElemType;

typedef struct QueueNode
{
	QElemType data;
	struct QueueNode* next;
}QueueNode,*QueuePtr;

typedef struct
{
	QueuePtr front, rear;//front是指向頭結點的指標，不是隊頭！隊頭是頭結點的后一位，
}LinkQueue;

初始化

void QueueInit(LinkQueue *Q)
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QueueNode));
    Q->front->next=NULL;
    Q->rear->next=NULL;
}

入隊

void EnQueue(LinkQueue* Q, QElemType x)
{
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

    newnode->data = x;  //將資料賦給新結點
    newnode->next = NULL;
    Q->rear->next = newnode;    //將新結點鏈接到隊尾結點之后
    Q->rear = newnode;    //隊尾指標后移一位
}

出隊

void DeQueue(LinkQueue* Q)
{
    if (Q->front == Q->rear) //佇列為空
        return Q;

    QueueNode* p = Q->front->next;    //保存待洗掉結點
    Q->front->next = p->next;  //頭結點與隊頭結點的后一位鏈接
    if (Q->rear == p)   // 若隊頭就是隊尾，則洗掉后將rear指向頭結點
        Q->rear = Q->front;
    free(p);
}

列印佇列

void PrintQueue(LinkQueue Q)
{
    QueueNode* cur = Q.front->next;//保存隊頭結點，準備列印
    
    while (cur)
    {
        printf("%d-->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

鏈佇列完整代碼

#include<stdio.h>
#include<stdlib.h>

typedef int QElemType;

typedef struct QueueNode
{
	QElemType data;
	struct QueueNode* next;
}QueueNode,*QueuePtr;

typedef struct
{
	QueuePtr front, rear;
}LinkQueue;

//初始化
void QueueInit(LinkQueue* Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QueueNode));
    Q->front->next = NULL;
    Q->rear->next = NULL;
}

//入隊
void EnQueue(LinkQueue* Q, QElemType x)
{
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

    newnode->data = x;  //將資料賦給新結點
    newnode->next = NULL;
    Q->rear->next = newnode;    //將新結點鏈接到隊尾結點之后
    Q->rear = newnode;    //隊尾指標后移一位
}

//出隊
void DeQueue(LinkQueue* Q)
{
    if (Q->front == Q->rear) //佇列為空
        return Q;

    QueueNode* p = Q->front->next;    //保存待洗掉結點
    Q->front->next = p->next;  //頭結點與隊頭結點的后一位鏈接
    if (Q->rear == p)   // 若隊頭就是隊尾，則洗掉后將rear指向頭結點
        Q->rear = Q->front;
    free(p);
}

//列印佇列
void PrintQueue(LinkQueue Q)
{
    QueueNode* cur = Q.front->next;//保存隊頭結點，準備列印
    
    while (cur)
    {
        printf("%d-->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

//測驗
void test1()
{
	LinkQueue Queue;
	QueueInit(&Queue);
	EnQueue(&Queue, 1);
	EnQueue(&Queue, 2);
	EnQueue(&Queue, 3);
	EnQueue(&Queue, 4);

	PrintQueue(Queue);

	DeQueue(&Queue);
	DeQueue(&Queue);
	PrintQueue(Queue);
}
int main()
{
	test1();
	return 0;
}