資訊工程 - 演算法與資料結構 - 資料結構 - 堆疊和佇列 - (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
}
}
重點:
你應該肯定在疑惑——
迴圈佇列的資料追加有什麽意義?它不就是個環形?哪裏和循環有關?
其實,追加和取出應該是一起使用的,準確的講,
- 佇列永遠是連續的
- 佇列永遠是從頭部開始取值
基於這兩點,可能會出現,一個佇列,前面空出來一大堆,後面滿了的情況。
這個時候,你就可以通過
(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)
留言
張貼留言