【資料結構——棧篇】

一、棧的順序儲存——順序棧

1、順序棧的表示和實現

因為棧底位置是固定不變的，所以可以將棧底位置設定在陣列的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的，故需要一個變數top來指示當前棧頂的位置，通常稱top為棧頂指標。

2、順序棧的定義

#define MAXSIZE 100
typedef struct
{
	SElemType* base;//棧底指標
	SElemType* top;//棧頂指標
	int stacksize;//可使用的最大容量
}SqStack;

SqStack S;//定義順序棧
S.stacksize = s;//棧的大小
S.base == S.top;//空棧
S.top - S.base == stacksize;//滿棧

2、順序棧初始化

演演算法思想：
1、分配空間並檢查空間是否分配成功，否則返回錯誤
2、棧頂指標top初始化為棧底指標base
3、stacksize = 棧的最大容量

Status IniStack(SqStack& S)
{
	S.base = new SElemType[MAXSIZE];//分配空間
	if (!S.base) exit(OVERFLOW);//分配失敗，返回錯誤
	S.top = S.base;//棧頂指標初始化為棧底指標
	S.stacksize = MAXSIZE;//初始化棧的最大容量
	return OK;
}

3、順序棧入棧

演演算法思想
1、判斷是否棧滿，若滿則出錯
2、新元素e壓入棧頂
3、棧頂指標+1

Status Push(SqStack& S, SElemType e)
{
	if (S.top - S.base == S.stacksize)
		return ERROR;//棧滿
	*S.top = e;//新元素e壓入棧頂
	S.top++;//棧頂指標+1
	return OK;
}

4、順序棧出棧

演演算法思想
1、判斷是否棧空，若空則出錯
2、棧頂指標-1
3、獲取棧頂元素e

Status Pop(SqStack& S, SElemType& e)
{
	if (S.top == S.base)
		return ERROR;//棧空報錯
	--S.top;//棧頂指標-1
	e = *S.top;//獲取棧頂元素e
	return OK;
}

5、取順序棧棧頂元素

SElemType GetTop(SqStack S)
{
	if (S.top != S.base)//棧非空
		return *(S.top - 1);//返回棧頂元素的值
	                        //棧頂指標不變
}

6、輸出棧內容

void OutPut_SqS(SqStack S)
{
	SElemType* p;
	if (S.top == S.base)
		printf("空棧！\n");
	else
		for (p = S.top - 1;p >= S.base;p--)
			printf("%d\n", *p);
}

二、棧的鏈式儲存——鏈棧

1、鏈式儲存方式表示的棧稱鏈棧
2、運算受限的單連結串列
3、連結串列的頭指標就是棧頂
4、不需要頭結點
5、插入與刪除僅在棧頂執行

1、鏈棧的儲存結構

typedef struct StackNode
{
	SElemType data;
	struct StackNode* next;
}StackNode,*LinkStack;

LinkStack S;

2、棧鏈的初始化

演演算法思想：
1、不需要頭結點
2、鏈棧的頭指標就是棧頂
3、棧鏈無棧滿問題，空間可擴充
4、空棧相當於頭指標指向NULL

Status IniStack(LinkStack& S)
{//構造一個空棧，棧頂指標置空
	S = NULL;
	return OK;
}

3、鏈棧的入棧

演演算法思想：
1、為入棧元素e分配空間，用指標p指向
2、將新結點指標域置為e
3、將新結點插入棧頂
4、修改棧頂指標為p

Status Push(LinkStack& S, SElemType e)
{
	p = new StackNode;//生成新結點
	p->data = e;//將新結點資料域置為e
	p->next = S;//將新結點插入棧頂
	S = p;//修改棧頂指標為p
	return OK;
}

4、鏈棧的出棧

演演算法思想：
1、判斷是否是空棧，若是空棧，返回錯誤
2、將棧頂元素賦值給e
3、臨時儲存棧頂元素的空間，以備釋放
4、修改棧頂指標，指向新的棧頂元素
5、釋放原棧頂元素的空間

Status Pop(LinkStack& S, SElemType& e)
{
	if (S == NULL)
		return ERROR;//棧空
	e = S->data;//將棧頂元素儲存到e中
	p = S;//用p臨時儲存棧頂元素的空間，以備釋放
	S = S->next;//修改棧頂指標
	delete p;//釋放原棧頂元素的空間
	return OK;
}

5、取鏈棧棧頂元素

SElemType GetTop(LinkStack S)
{
	if (S != NULL)
		return S->data;
}

6、輸出鏈棧的內容

void OutPut(LinkStack S)
{
	p = S;
	if (!p)
		printf("空棧！");
	else
		while (p)
		{
			printf("%d", p->data);
			p = p->next;
		}
}