1、棧
棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)拭荤。棧頂進(jìn)棧僚饭，棧頂出棧震叮。
- 數(shù)據(jù)結(jié)構(gòu)
typedef struct Data{
int value;
int min; //用來(lái)記錄棧的最小值
}*DataType;
typedef struct Stack
{
DataType link;//動(dòng)態(tài)數(shù)組，或者可以直接用靜態(tài)數(shù)組
int top;
}Stack;
- 棧的初始化
void InitStack(Stack *s)
{
s->top=0;
s->link=(DataType)malloc(Max*sizeof(struct Data));
}
- 進(jìn)棧
void Push(Stack *s, int d)
{
if(s->top==Max)
{
printf("棧已滿(mǎn),無(wú)法進(jìn)棧\n");
return;
}
DataType element=(DataType)malloc(sizeof(struct Data));
element->value=d;
if(s->top==0)
element->min=d;
else
{
element->min=s->link[(s->top)-1].min;
if(s->link[(s->top)-1].min>d)
element->min=d;
}
s->link[s->top]=*element;
s->top++;
}
- 出棧
void Pop(Stack *s)
{
if(s->top==0)
{
printf("棧為空\(chéng)n");
return;
}
s->top--;
}
- 棧的最小值
int MinStack(Stack *s)
{
return s->link[s->top-1].min;
}
2鳍鸵、隊(duì)列
隊(duì)列是FIFO（First In Fisrst Out）苇瓣，即先進(jìn)先出。有隊(duì)頭和隊(duì)尾兩個(gè)指針偿乖，分別指向隊(duì)列的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)击罪。隊(duì)頭出隊(duì)，隊(duì)尾入隊(duì)贪薪。
Paste_Image.png
- 數(shù)據(jù)結(jié)構(gòu)
typedef struct QNode{
TreeNode Node; //[TreeNode數(shù)據(jù)結(jié)構(gòu)]（http://www.reibang.com/p/1343b3e27869）
struct QNode * next;
}QNode,*QueueNode;
typedef struct LinkQueue{
QueueNode front;
QueueNode rear;
}LinkQueue;
- 隊(duì)列初始化
void Init(LinkQueue *q)
{
q->front=q->rear=(QueueNode)malloc(sizeof(QNode));//隊(duì)列的頭結(jié)點(diǎn)（空隊(duì)列中只有一個(gè)頭結(jié)點(diǎn)）
if(!q->front)//申請(qǐng)內(nèi)存空間失敗
exit(0);
q->front->next=NULL;
}
- 入隊(duì)
void EnQueue(LinkQueue *q,TreeNode treenode)
{
QueueNode qnode;
qnode=(QueueNode)malloc(sizeof(QNode));
qnode->Node=treenode;
/****插入隊(duì)列****/
qnode->next=q->rear->next;
q->rear->next=qnode;
/****改隊(duì)尾指針****/
q->rear=qnode;
}
- 出隊(duì)
void DeQueue(LinkQueue *q,TreeNode *node)
{
QueueNode p;
p=q->front->next;//頭結(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)
*node=p->Node;
q->front->next=p->next;
if(q->rear==p) //刪除的是否是最后一個(gè)節(jié)點(diǎn)
q->rear=q->front;
free(p);
}
- 隊(duì)列是否為空
int QueueEmpty(LinkQueue *q)
{
if(q->rear==q->front)//此時(shí)隊(duì)列中只剩一個(gè)頭結(jié)點(diǎn)外邓，則隊(duì)列為空
return 1;
else
return 0;
}
Paste_Image.png
