Stack
第一種定義(推薦, 可以實現(xiàn)動態(tài)分配Stack SIZE)
typedef struct {
ElemType *base; //用指針指明stack base;
int top; //標記出stack top;
int stacksize; //當前已經(jīng)分配的存儲空間, 以元素為單位; 類似于MAXSIZE概念
}SqStack;
- 從第一種定義看出, 求當前stack length可以直接(top-base)/sizeof(ElemType) (不用+1, 因為top指向了下一位);
第二種定義(定死Stack的SIZE)
typedef struct {
ElemType stack[MAXSIZE]; //直接定義一個數(shù)組, 定死了內(nèi)存
int top; //標記出stack top;
} SqStack;
- 從第二種定義, 我們可以看出stack length可以直接top得出(top指向的是空的下一位, 但是stack數(shù)組從stack[0]開始, 因為stack-length = top-1-0+1 = top);
/*構(gòu)造空棧*/
//要顧及到各個struct中的各個參數(shù)如base, top, stacksize;
Status InitStack(SqStack *S) {
S->base = (ElemType *)malloc(SIZE*sizeof(ElemType));
S->stacksize = SIZE;
S->top = 0;
return 0;
}
/*GetTop*/
//先檢查是否為空棧, 不是才可以輸出base[top-1];
ElemType GetTop(SqStack *S) {
if (S->top==0) {printf("GetTop UNDERFLOW\n"); return ERROR;}
else {return S->base[S->top-1];}
}
/*Pop*/
//先檢查是否為空棧, 不是才可以用top--來縮減棧的高度;
Status Pop(SqStack *S) {
if (S->top==0) {printf("Pop UNDERFLOW\n"); return ERROR;}
else {S->top--; return 0;}
}
/**/
//先檢查是否棧滿了, 滿了就realloc內(nèi)存, 然后才可以push e到top原來位置, 然后讓top上浮一位;
Status Push (SqStack *S, ElemType e) {
if (S->top >= SIZE) {
S->base = (ElemType *)realloc(S->base,(SIZE+INCREMENT)*sizeof(ElemType));
S->stacksize += INCREMENT;
if (!S->base) {printf("Push OVERFLOW\n"); exit(OVERFLOW);}
}
S->base[S->top] = e;
S->top++;
return 0;
}
Queue
typedef struct {
ElemType *base; //最好不要寫死容量, 以適應不同大小的輸入
int front, rear;
int length; //應對隊列頭減少而尾部到頂?shù)那樾? 必須計數(shù)num來實現(xiàn)不浪費空間; stack沒有這個問題, length直接top值就是了;
int queuesize;
}SqQueue;
/*GetFront*/
//先檢查是否length==0, 然后再取base[front]
ElemType GetFront(SqQueue *Q) {
if (Q->length==0) {
printf("GetFront UNDERFLOW\n"); return ERROR;
} else {
return Q->base[Q->front];
}
}
//先檢查Q是否是空的, 非空才把front往后移動一個位置;
Status DeQueue(SqQueue *Q) {
if (Q->length==0) {
printf("DeQueue UNDERFLOW\n"); return ERROR;
} else {
Q->front++;
}
}
//先檢查Q是否是滿的, 非滿的再添加, 別忘了rear, length都要++
Status EnQueue(SqQueue *Q, ElemType e) {
if (Q->length==SIZE) {
//動態(tài)分配內(nèi)存
Q->base = (ElemType *)realloc(Q->base,(SIZE+INCREMENT)*sizeof(ElemType));
Q->queuesize += INCREMENT;
if (!Q->base) {printf("EnQueue OVERFLOW\n"); exit(OVERFLOW);}
}
Q->base[Q->rear] = e;
Q->rear++;
Q->length++;
printf("rear: %d\n",Q->rear);
return 0;
}
后記: queue的數(shù)據(jù)結(jié)構(gòu)定義和stack基本一個套路, 都是采用順序線性表的定義方式(*elem, length, listsize→stack/queue(數(shù)組名就是指針), top/front,rear, length, size (top本身包含了計算length的方法))
DFS和棧, BFS和隊列
棧和隊列是簡單, 使用的數(shù)據(jù)結(jié)構(gòu), 運用范圍很廣.
圖算法中最基本的DFS和BFS算法的實現(xiàn)分別依靠棧和隊列.
相關(guān)算法代碼可以參考我的圖算法文章.
