資訊工程 - 演算法與資料結構 - 資料結構 - 堆疊和佇列 - （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）
留言
張貼留言