資訊工程 - 演算法與資料結構 - 資料結構 - 堆疊和佇列 - (Stack&Queue)

上一篇:資訊工程 - 演算法與資料結構 - 資料結構 - 鏈結串列(Linked List)

目錄:資訊工程 - 演算法與資料結構  -  Algorithm&Data Struncture(目錄)


堆疊(Stack)

堆疊(stack),逐次輸入輸出的資料暫時保存的資料結構。

後進先出(Last In First Out(LIFO))的資料結構。


堆疊(stack)的定義

typedef struct stack

{

int *data;

int top;//top從0開始,切不大於max_size

int max_size;

}*stack;

需要説明一下,typedef的用法實際是自製關鍵字。

而花括號之後的*stack表示該sttruct的指針。

舉個例子:

typedef struct a

{

     ......

}newname, *newpointerName;

這段代碼等於我給struct a取別名newname,并且把它struct a的指針稱作*newpointerName,因此在使用時,將具有等同效力。


堆疊(stack)的資料追加

void push(stack s, int val)

{

if(s->top<s->max_size)

s->data[s->top++]=val;//top++表示top=top+1,并且落後執行

//我舉個例子,top默認應該是從0開始的,所以data[0]首先被賦值,完成后top變成了1

}


堆疊(stack)的資料取出

int pop(stack s)

{

if(s->top>0)

return s->data[--s->top];//--s->top表示s->top=top-1,并且優先執行

//舉個例子,假設現在有1個資料,默認top為1,但是這個資料實際存儲在Data[0],所以得優先-1

}


注意:top的初始化一般是從0開始的。


佇列(Queue)

キュー(待ち行列)

佇列。

佇列和堆疊(stack)相反,是先進先出(First In First Out(FIFO))的資料結構。

從名字上就很直觀,這就和排隊一樣,先排隊的自然先得到解決。


迴圈佇列

迴圈佇列是指,當rear超過了範圍,我們可以讓指針重置到0。

重新0,1,2,3,4,5這樣開始。



迴圈佇列的定義:

typedef struct queue

{

int *data;

int front;//游標,指向最前,默認0

int rear;//游標,指向最後,默認应该是小于max_size,通常是max_size-1

int max_size;

}*queue;


迴圈佇列的資料取出:

int dequeue(queue q)

{

if(q->front!=q->rear)//判断是否已经没有数据

{//设一个{5,6,7}的队列

int head=q->data[q->front];//这里head等于Data[0]=5

q->front=(q->front+1)%q->max_size;//1%3=1,font=1,这个时候data[q->front]=6

return head;//这里的数据结构变成{NULL,6,7},front是从1开始

}

}

類似的代碼:https://qiita.com/Sekiyuuu/items/5cb3e3ae958557d4f11f


迴圈佇列的資料追加:

void enqueue(queue q,int x)

{ //判定是否有空餘可以加入佇列

if((q->rear+1)%q->max_size!=q->front)//這句話什麽意思呢,擧個例子,只有2個數字的佇列,它的front是0,rear是1,max_size設為2,這樣(1+1)%2=0,不可追加

{//可追加的情況是,max_size比如3,2÷3=0余2,所以2%3=2,所以可以進行追加

q->data[q->rear]=x;//根據rear的游標,追加到末尾

q->rear=(q->rear+1)%q->max_size;//把2的賦值給rear

}

}


重點:

你應該肯定在疑惑——

迴圈佇列的資料追加有什麽意義?它不就是個環形?哪裏和循環有關?


其實,追加和取出應該是一起使用的,準確的講,

  1. 佇列永遠是連續的
  2. 佇列永遠是從頭部開始取值

基於這兩點,可能會出現,一個佇列,前面空出來一大堆,後面滿了的情況

這個時候,你就可以通過

(q->rear+1)%q->max_size!=q->front

來判斷是否滿。(即判斷前面是否空出,因爲前面因爲取出而產生了front的移動,那肯定還可以繼續放新的data)

具體動畫可以查看影片

【用動畫演示迴圈佇列和堆疊(stack)是怎麽操作的,noip真題】 【精準空降到 04:19】

https://www.bilibili.com/video/BV1ub4y1m7Qj/?share_source=copy_web&t=259

資料結構之迴圈佇列動畫演示

https://www.bilibili.com/video/BV1ob411T7Uk

迴圈佇列的本質只是爲了高效利用内存空間。


理解以上之後,還有一件事就是:

  • 迴圈佇列始終都會浪費1個空間。(這個空間處於rear的之後,front之前)

我們隊空的條件是front==rear,

判斷隊滿的條件是(rear+1)%MAXSIZE==front

所以説這個rear+1的空間就被浪費掉了。


習題

1. 堆疊(stack)

這裏給出筑波大學2007年的關於Stack的過去問。

這一題是要求用鏈結串列(Linked List)實現堆疊(stack)

筑波大学・2007・スタック

2個函數push()和pop(),push()是往stack裏面進行element追加,pop()是將element取出,當stack為空,報error。這個問題要求你不要報error。用可以保持整數的Linked List實現。示意圖如上圖所示。

(1) 以下是,為stack增加element所編寫的C語言程式。請填寫A,B,C的空欄。函數malloc()是分割指定byte數(1byte=8bit),獲得address(注意圖中malloc是無法直接使用的)。該問,memory的分割常時成功。定數NULL是指什麽element都沒有指向的pointer。

解答:

先解釋圖。

圖已告知我們,sp本身是指struct element的最後一個元素。

因此,我們新增加的e應當指向sp,然後賦值data,最後把這個新增加的element變成新的sp。

代碼如下:

#include "stdafx.h"

#include "malloc.h"


struct element{

struct element *link;

int data;

};

struct element *sp;


void push(int data)

{

struct element *e;

e=(element *)malloc(sizeof(struct element));

        e->link=sp;

e->data=data;

sp=e;

}


int _tmain(int argc, _TCHAR* argv[])

{

push(1);

printf("%d \n",sp->data);

push(2);

printf("%d \n",sp->data);

push(3);

printf("%d \n",sp->data);

printf("%d \n",sp->link->data);

printf("%d \n",sp->link->link->data);

return 0;

}

結果:

4.6.1 push()

筑波大学・2007・スタック


(2) 解答:

答案是-590。

需要補充一下pop:

int pop()

{

int data=sp->data;

sp=sp->link;

return data;

}


(3) 解答:

void swap()

{

int arg1,arg2;

arg2=pop();

arg1=pop();

push(arg2);

push(arg1);

}


(4) 解答:

void negate(void)

{

push(-sp->data);

swap();

pop();

}



下一篇:資訊工程 - 演算法與資料結構 - 資料結構 - 二元樹(Binary Tree)

目錄:資訊工程 - 演算法與資料結構  -  Algorithm&Data Struncture(200

留言

這個網誌中的熱門文章

【TOEIC】多益復習800分的準備 - 第2天(從600分進步到800分計劃)

微積分 - 求不定積分 $$\int \:tanxdx$$ Integral of tan x dx

【TOEIC】多益復習800分的準備 - 第4天(從600分進步到800分計劃)