1、堆疊：僅在表尾進行插入和洗掉操作的線性表，后進先出LIFO，
1）表尾端（允許插入和洗掉的一端）為堆疊頂，表頭端（不允許插入和洗掉的一端）為堆疊底，
2）入堆疊：插入元素的操作，出堆疊：洗掉堆疊頂元素
3）堆疊的應用：數值轉化、括號匹配檢驗、行編輯程式、迷宮求解、運算式求值
2、堆疊的兩種存盤表示方式
1）順序堆疊（堆疊的順序存盤結構）：利用一組地址連續的存盤單元一次存放自堆疊底到堆疊頂的資料元素，同時附設指標top指示堆疊頂元素在順序堆疊中的位置，top=0表示空堆疊，
2）鏈堆疊（堆疊的鏈式存盤結構）;優點是便于多個堆疊共享存盤空間和提高效率，
3、括號匹配檢驗
1）左括號，則進堆疊，
2）右括號，若堆疊為空，則右括號多，
3）右括號，與堆疊頂元素比較，若相等則左括號出堆疊，若不相等則不匹配，
4）運算式檢驗結束時，若堆疊空則匹配成功，否則左括號多，
4、堆疊的基本操作
InitStack(&S)：構造空堆疊
DestroyStack(&S)：銷毀堆疊
ClearStack(&S)：清空堆疊
StackEmpty(S)：判斷堆疊是否為空，若為空則回傳true，否回傳false
StackLength(S)：回傳堆疊的長度
GetTop(S,&e)：用e回傳堆疊的堆疊頂元素
Push(&S,e)：插入e為新堆疊頂
Pop(&S,&e)：洗掉堆疊頂元素，并用e回傳其值，
5、共享堆疊：利用堆疊底位置相對不變性的特性，使得兩個順序堆疊共享一個一維資料空間，將兩個堆疊底設定在共享空間的兩端，
1）top0=-1時0號堆疊為空，top1=maxsize時1號堆疊為空，僅當兩個堆疊頂指標相鄰（top1-top0=1）時，堆疊滿，
2）當0號堆疊進堆疊時top0先加1再賦值，1號堆疊進堆疊時top1先減1在賦值，
6、堆疊的順序存盤型別描述
#define maxsize 50typedef struct {
int data[maxsize];
int top;//堆疊頂指標,初始時設定S.top=-1，堆疊頂元素為：S.data[S.top]，堆疊空條件：S.top==-1堆疊滿條件：S.top==maxsize-1堆疊長：S.top+1
}Sqstack; 1）初始化堆疊
void initstack(Sqstack &S)
{
S.top = -1;
}
2）判斷堆疊空
bool stackempty(Sqstack S)
{
if (S.top == -1)
{
return true;
}
else
{
return false;
}
}
3）進堆疊
bool push(Sqstack &S, int e)
{
if (S.top == maxsize - 1)
{
return false;
}
S.data[++S.top] = e;
return true;
}
5）出堆疊
bool pop(Sqstack &S, int &e)
{
if (S.top == -1)
{
return false;
}
e = S.data[S.top--];
return true;
}
6）讀堆疊頂元素
bool GetTop(Sqstack S, int &e)
{
if (S.top == -1)
{
return false;
}
e = S.data[S.top--];
return true;
} 7、堆疊的鏈式存盤結構型別描述
typedef struct Linkstack {
int data;
struct Linkstack *next;
}*Listack; 8、一些基本問題的解決 1）以IO分別表示入堆疊和出堆疊操作，堆疊的初態和終態都為空，可以操作的序列稱為合法序列，判斷序列是否合法，
int judge(cha A[])
{
int i = j = k = 0;
while (A[i]!='\0')
{
switch (A[i])
{
case 'I':j++;
break;
case 'O':k++;
if (k > j)
{
printf("序列非法\n");
exit(0);
}
}
i++;
}
if (j != k)
{
printf("序列非法");
return false;
}
else
{
printf("序列合法");
return true;
}
}
2）設堆疊S1，S2都擦用順序堆疊，并共享一個存盤區[0,...,maxsize-1]，采用堆疊頂相向、迎面增長的存盤方式，出堆疊和入堆疊的實作，i為堆疊號，i=0表示左邊的堆疊s1，i=1表示右邊的堆疊s2，e為入堆疊元素，
typedef struct {
int stack[maxsize];
int top[2];
}stk;
stk s;
//入堆疊
int push1(int i, int e)
{
if (i < 0 || i>1)
{
printf("堆疊號輸入錯誤");
exit(0);
}
if (s.top[1] - s.top[0] == 1)
{
printf("堆疊以滿\n");
return 0;
}
switch (i)
{
case 0:s.stack[++s.top[0]] = e;
return 1;
break;
case 1:s.stack[--s.top[1]] = e;
return 1;
}
}
//出堆疊
int pop1(int i)
{
if (i < 0 || i>1)
{
printf("堆疊號輸入錯誤\N");
exit(0);
}
switch (i)
{
case 0:
if (s.top[0] == -1)
{
printf("堆疊空\n");
return -1;
}
else
{
return s.stack[s.top[0]--];
}
case 1:
if (s.top[1] == maxsize)
{
printf("堆疊空\n");
return -1;
}
else
{
return s.stack[s.top[1]++];
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198924.html
標籤：其他
上一篇：堆疊與佇列
下一篇：VMTools安裝