WIKI使用導(dǎo)航
站長(zhǎng)百科導(dǎo)航
站長(zhǎng)專題
- 網(wǎng)站推廣
- 網(wǎng)站程序
- 網(wǎng)站賺錢
- 虛擬主機(jī)
- cPanel
- 網(wǎng)址導(dǎo)航專題
- 云計(jì)算
- 微博營(yíng)銷
- 虛擬主機(jī)管理系統(tǒng)
- 開放平臺(tái)
- WIKI程序與應(yīng)用
- 美國(guó)十大主機(jī)
堆棧
堆棧（英文：stack），也可直接稱棧。在計(jì)算機(jī)科學(xué)中，是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈結(jié)串行或陣列的一端（稱為堆棧頂端指標(biāo)，英文為top）進(jìn)行加入資料（push）和輸出資料（pop）的運(yùn)算。另外堆棧也可以用一維陣列或連結(jié)串行的形式來完成。堆棧的另外一個(gè)相對(duì)的操作方式稱為佇列。由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。它是一種存儲(chǔ)部件，即數(shù)據(jù)的寫入跟讀出不需要提供地址，而是根據(jù)寫入的順序決定讀出的順序。 堆棧數(shù)據(jù)結(jié)構(gòu)使用兩種基本操作：推入（push）和彈出（pop）
- 推入（push）：將數(shù)據(jù)放入堆棧的頂端（陣列形式或串行形式），堆棧頂端top指標(biāo)加一。
- 彈出（pop）：將頂端數(shù)據(jù)資料輸出（回傳），堆棧頂端資料減一。
堆棧簡(jiǎn)介[ ]
動(dòng)態(tài)數(shù)據(jù)區(qū)一般就是“堆?！??！皸?stack)”和“堆(heap)”是兩種不同的動(dòng)態(tài)數(shù)據(jù)區(qū)，棧是一種線性結(jié)構(gòu)，堆是一種鏈?zhǔn)浇Y(jié)構(gòu)。進(jìn)程的每個(gè)線程都有私有的“?！?，所以每個(gè)線程雖然代碼一樣，但本地變量的數(shù)據(jù)都是互不干擾。一個(gè)堆?？梢酝ㄟ^“基地址”和“棧頂”地址來描述。全局變量和靜態(tài)變量分配在靜態(tài)數(shù)據(jù)區(qū)，本地變量分配在動(dòng)態(tài)數(shù)據(jù)區(qū)，即堆棧中。程序通過堆棧的基地址和偏移量來訪問本地變量。
堆棧原理[ ]
堆棧是一種執(zhí)行“后進(jìn)先出”算法的數(shù)據(jù)結(jié)構(gòu)。 它是在內(nèi)存中開辟一個(gè)存儲(chǔ)區(qū)域，數(shù)據(jù)一個(gè)一個(gè)順序地存入（也就是“ 推入——push”）這個(gè)區(qū)域之中。有一個(gè)地址指針總指向最后一個(gè)壓入堆棧的數(shù)據(jù)所在的數(shù)據(jù)單元，存放這個(gè)地址指針的寄存器就叫做堆棧指示器。開始放入數(shù)據(jù)的單元叫做“棧底”。數(shù)據(jù)一個(gè)一個(gè)地存入，這個(gè)過程叫做“壓棧”。在壓棧的過程中，每有一個(gè)數(shù)據(jù)壓入堆棧，就放在和前一個(gè)單元相連的后面一個(gè)單元中，堆棧指示器中的地址自動(dòng)加1。讀取這些數(shù)據(jù)時(shí)，按照堆棧指示器中的地址讀取數(shù)據(jù)，堆棧指示器中的地址數(shù)自動(dòng)減1。這個(gè)過程叫做“彈出pop”。
堆棧分類[ ]
- 陣列堆棧
#include <stdio.h>
#include <stdlib.h>
/*堆疊資料結(jié)構(gòu)*/
struct Stack
{
int Array[10];//陣列空間
int Top;//堆疊頂端指標(biāo)
};
/*檢查堆疊是否為空*/
bool stack_empty(Stack *Stack1)
{
if(Stack1->Top==0)
{
return true;
}
else
{
return false;
}
}
/*推入資料*/
void push(Stack *Stack1,int x)
{
Stack1->Top=Stack1->Top+1;
Stack1->Array[Stack1->Top]=x;
}
/*彈出資料*/
int pop(Stack *Stack1)
{
if(stack_empty(Stack1))
{
printf("underflow");
}
else
{
Stack1->Top=Stack1->Top-1;
return Stack1->Array[Stack1->Top+1];
}
}
int main()
{
struct Stack *Stack1=(struct Stack *)malloc(sizeof(struct Stack));//宣告資料結(jié)構(gòu)空間
Stack1->Top=0;//初始化
push(Stack1,3);//推入3
push(Stack1,4);//推入4
push(Stack1,1);//推入1
push(Stack1,10);//推入10
printf("%d ",pop(Stack1));//彈出10
printf("%d ",pop(Stack1));//彈出1
printf("%d ",pop(Stack1));//彈出4
system("pause");
}
- 串行堆棧
/*鏈棧的結(jié)構(gòu)定義*/
typedef struct {
SLink top; // 棧頂指針
int length; // 棧中元素個(gè)數(shù)
}Stack;
void InitStack ( Stack &S )
{
// 構(gòu)造一個(gè)空棧 S
S.top = NULL; // 設(shè)棧頂指針的初值為"空"
S.length = 0; // 空棧中元素個(gè)數(shù)為0
} // InitStack
/*能否將鏈棧中的指針方向反過來，不行，如果反過來的話，刪除棧頂元素時(shí)，為修改其前驅(qū)指針，需要從棧底一直找到棧頂。*/
void Push ( Stack &S, ElemType e )
{
// 在棧頂之上插入元素 e 為新的棧頂元素
p = new LNode; // 建新的結(jié)點(diǎn)
if(!p) exit(1); // 存儲(chǔ)分配失敗
p -> data = e;
p -> next = S.top; // 鏈接到原來的棧頂
S.top = p; // 移動(dòng)棧頂指針
++S.length; // 棧的長(zhǎng)度增1
} // Push
/*在鏈棧的類型定義中設(shè)立"棧中元素個(gè)數(shù)"的成員是為了便于求得棧的長(zhǎng)度。*/
bool Pop ( Stack &S, SElemType &e )
{
// 若棧不空，則刪除S的棧頂元素，用 e 返回其值，
// 并返回 TRUE；否則返回 FALSE
if ( !S.top )
return FALSE;
else
{
e = S.top -> data; // 返回棧頂元素
q = S.top;
S.top = S.top -> next; // 修改棧頂指針
--S.length; // 棧的長(zhǎng)度減1
delete q; // 釋放被刪除的結(jié)點(diǎn)空間
return TRUE;
}
} // Pop