C++中棧結(jié)構(gòu)建立與操作詳細(xì)解析

更新時間：2013年10月14日 09:44:11 作者：

我們可以把棧理解成一個大倉庫，放在倉庫門口（棧頂）的貨物會優(yōu)先被取出，然后再取出里面的貨物。而從數(shù)據(jù)的邏輯結(jié)構(gòu)來看，棧結(jié)構(gòu)起始就是一種線性結(jié)構(gòu)

什么是棧結(jié)構(gòu)

棧結(jié)構(gòu)是從數(shù)據(jù)的運算來分類的，也就是說棧結(jié)構(gòu)具有特殊的運算規(guī)則，即：后進(jìn)先出。

我們可以把棧理解成一個大倉庫，放在倉庫門口（棧頂）的貨物會優(yōu)先被取出，然后再取出里面的貨物。

而從數(shù)據(jù)的邏輯結(jié)構(gòu)來看，棧結(jié)構(gòu)起始就是一種線性結(jié)構(gòu)。

如果從數(shù)據(jù)的存儲結(jié)構(gòu)來進(jìn)一步劃分，棧結(jié)構(gòu)包括兩類：
順序棧結(jié)構(gòu)：

即使用一組地址連續(xù)的內(nèi)存單元依次保存棧中的數(shù)據(jù)。在程序中，可以定義一個指定大小的結(jié)構(gòu)數(shù)組來作為棧，序號為0的元素就是棧低，再定義一個變量top保存棧頂?shù)男蛱柤纯伞?BR>鏈?zhǔn)綏＝Y(jié)構(gòu)：

即使用鏈表的的形式保存棧中各元素的值。鏈表首部（head指針?biāo)赶蛟兀闂ｍ敚湵砦膊浚ㄖ赶虻刂窞镹ULL）為棧底。

在棧結(jié)構(gòu)中只能在一端進(jìn)行操作，該操作端稱為棧頂，另一端稱為棧底。也就是說，保存和取出的數(shù)據(jù)都只能從棧結(jié)構(gòu)的一端進(jìn)行。從數(shù)據(jù)的運算角度來分析，棧結(jié)構(gòu)是按照“后進(jìn)先出”的原則處理結(jié)點數(shù)據(jù)的。

在棧結(jié)構(gòu)中，只有棧頂元素是可以訪問的，棧結(jié)構(gòu)的數(shù)據(jù)運算也是非常簡單。一般棧結(jié)構(gòu)的基本操作只有兩個：

入棧（Push）：將數(shù)據(jù)保存到棧頂?shù)牟僮鳌＿M(jìn)行入棧操作前，先修改棧頂指針，使其向上移一個元素位置，然后將數(shù)據(jù)保存到棧頂指針?biāo)傅奈恢谩?/P>

出棧（Pop）：將棧頂數(shù)據(jù)彈出的操作。通過修改棧頂指針，使其指向棧中的下一個元素。

接下來，我們使用C++語言建立順序棧，并完成順序棧結(jié)構(gòu)的基本運算
準(zhǔn)備數(shù)據(jù)

準(zhǔn)備在棧操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等。

復(fù)制代碼代碼如下:

#define MAXLEN 50
struct DATA
{
string name;
int age;
};
struct StackType
{
DATA data[MAXLEN+1];
int top;
};

定義棧結(jié)構(gòu)的長度MAXLEN，棧結(jié)構(gòu)的數(shù)據(jù)元素類型DATA，以及棧結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)StackType。在數(shù)據(jù)結(jié)構(gòu)StackType中，data為數(shù)據(jù)元素，top為棧頂?shù)男蛱枴．?dāng)top=0時，表示棧為空，當(dāng)top=MAXLEN時表示棧滿。

數(shù)組元素都是充下標(biāo)0開始的，這里為了講述和理解方便，我們從下標(biāo)1開始記錄數(shù)據(jù)結(jié)點，下標(biāo)0的位置不用。
初始化棧結(jié)構(gòu)

在使用棧結(jié)構(gòu)之前，首先需要創(chuàng)建一個空的順序棧，也就是初始化順序棧。順序棧的初始化操作如下：

（1）按照符號常量MAXLEN指定大小申請一片內(nèi)存空間，用來保存棧中的數(shù)據(jù)

（2）設(shè)置棧頂指針的值為0，表示一個空棧。

示例代碼如下：

復(fù)制代碼代碼如下:

StackType *STInit()
{
 StackType *p;
 if(p=new StackType)   //申請?？臻g 
 {
  p->top=0;     //設(shè)置棧頂為0
  return p;     //返回棧頂指針 
 } 
 return NULL; 
}

首先用new申請內(nèi)存，然后設(shè)置棧頂為0，然后返回申請內(nèi)存的首地址，申請失敗返回NULL;

判斷空棧

判斷棧結(jié)構(gòu)是否為空，如果是空棧，則表示該棧結(jié)構(gòu)中沒有數(shù)據(jù)，此時可以進(jìn)行入棧操作，但是不可以進(jìn)行出棧操作。

示例代碼如下：

復(fù)制代碼代碼如下:

int STIsEmpty(StackType *s)
{
 int t;
 t=(s->top==0);     //通過棧頂?shù)闹颠M(jìn)行判斷
 return t; 
}

輸入?yún)?shù)s為一個指向操作的棧的指針。根據(jù)棧頂指針top判斷是否為0，判斷棧是否為空。

判斷滿棧

判斷棧結(jié)構(gòu)是否為滿。如果是滿棧，則表示該棧結(jié)構(gòu)中沒有多余的空間來保存額外數(shù)據(jù)。此時不可以進(jìn)行入棧操作，但是可以進(jìn)行進(jìn)棧操作。

示例代碼如下：

復(fù)制代碼代碼如下:

int STIsFull(StackType *s)
{
 int t;
 t=(s->top==MAXLEN);
 return t; 
} 

輸入?yún)?shù)s為一個指向操作的棧的指針。根據(jù)棧頂指針top判斷是否和MAXLEN相等，判斷棧是否已滿。

清空棧

清空棧就是棧中所有的數(shù)據(jù)被清除。示例代碼如下：

復(fù)制代碼代碼如下:

void STClear(StackType *s)
{
 s->top=0;
} 

將棧頂指針top設(shè)置為0，表示執(zhí)行清空棧操作。（這里只是邏輯上將棧中數(shù)據(jù)清空，實際上只是將top設(shè)置為0，以后再添加數(shù)據(jù)會覆蓋原來的數(shù)據(jù)）

釋放空間

釋放空間是釋放棧結(jié)構(gòu)所占用的內(nèi)存單元，使用delete釋放用new運算符申請的內(nèi)存空間。

示例代碼如下：

復(fù)制代碼代碼如下:

void STFree(StackType *s)
{
 delete s;
} 

在程序中直接調(diào)用delete運算符釋放已分配的內(nèi)存空間。一般在不需要使用棧結(jié)構(gòu)時調(diào)用該函數(shù)，特別是在程序結(jié)束的時候。

入棧

入棧（Push）是棧結(jié)構(gòu)的基本操作，主要操作是將數(shù)據(jù)元素保存到棧結(jié)構(gòu)。入棧操作的具體步驟如下：

（1）首先判斷棧頂top，如果top大于等于MAXLEN，則表示溢出，進(jìn)行出錯處理。否則執(zhí)行以下操作。

（2）設(shè)置top=top+1(棧頂指針加1，指向入棧地址)

（3）將入棧呀U尿素保存到top指向的位置。

示例代碼如下:

復(fù)制代碼代碼如下:

int PushST(StackType *s,DATA data)
{
 if((s->top+1)>MAXLEN)
 {
  cout<<"棧溢出"<<endl;
  return 0;
 }
 s->data[++s->top]=data;     //將元素壓入棧 
 return 1;
}

輸入?yún)?shù)s為一個指向操作的棧的指針，輸入?yún)?shù)data是需要入棧的數(shù)據(jù)元素。程序首先判斷棧是否溢出，如果溢出就給出警告，不進(jìn)行入棧操作，否則修改棧頂指針，即top先加1，然后將data放到top現(xiàn)在指向的數(shù)據(jù)單元。

出棧

出棧（Pop）是占據(jù)誒狗的基本操作，主要操作與入棧相反，它是從棧頂彈出一個數(shù)據(jù)元素，出棧操作的具體步驟如下：

（1）首先判斷棧頂top，如果top等于0，則表示為恐慌在哪，進(jìn)行出錯處理。否則執(zhí)行下面的操作。

（2）將棧頂指針top所指向的位置的元素返回（實際是返回的指針）

（3）將top的減1，指向棧的下一個元素，原來棧頂?shù)脑乇粡棾觥?BR>

復(fù)制代碼代碼如下:

DATA * PopST(StackType *s)
{
 if(s->top==0)
 {
  cout<<"棧為空，不能再輸出！"<<endl;
  exit(0);
 }
 return &(s->data[s->top--]);
} 

當(dāng)棧中有數(shù)據(jù)時，該函數(shù)返回值是一個指向DATA類型數(shù)據(jù)的指針。

讀取點結(jié)構(gòu)

讀取點結(jié)構(gòu)也就是讀取棧結(jié)構(gòu)中結(jié)點的數(shù)據(jù)。由于棧結(jié)構(gòu)只能在一端進(jìn)行操作，因此這里的讀操作其實就是讀站點的數(shù)據(jù)。

需要注意的是，讀節(jié)點數(shù)據(jù)的操作和出棧操作不同。讀結(jié)點操作僅僅是顯示棧頂結(jié)點數(shù)據(jù)的內(nèi)容，而出棧操作則將棧頂數(shù)據(jù)彈出。

示例代碼如下：

復(fù)制代碼代碼如下:

DATA *PeekST(StackType *s)
{
 if(s->top==0)
 {
  cout<<"棧已空"<<endl;
  exit(0);
 }
 return &(s->data[s->top]);
}

對比出棧的示例代碼，不難發(fā)現(xiàn)讀取點結(jié)構(gòu)同樣返回了棧頂結(jié)點的地址，但是卻沒有使top減1.

完整示例

下面是棧的基本操作的完整示例：

程序代碼：

復(fù)制代碼代碼如下:

#include<iostream>
#include<string>
using namespace std;
#define MAXLEN 50
struct DATA
{
string name;
int age;
};
struct StackType
{
DATA data[MAXLEN+1];
int top;
};
/******************初始化棧結(jié)構(gòu)****************/
StackType *STInit()
{
StackType *p;
if(p=new StackType)   //申請?？臻g
{
  p->top=0;     //設(shè)置棧頂為0
  return p;     //返回棧頂指針
}
return NULL;
}
/****************判斷空棧**********************/
int STIsEmpty(StackType *s)
{
int t;
t=(s->top==0);     //通過棧頂?shù)闹颠M(jìn)行判斷
return t;
}
/**********************判斷滿棧****************/
int STIsFull(StackType *s)
{
int t;
t=(s->top==MAXLEN);
return t;
}
/**********************清空棧**********************/
void STClear(StackType *s)
{
s->top=0;
}
/********************釋放空間********************/
void STFree(StackType *s)
{
delete s;
}
/**********************入棧***********************/
int PushST(StackType *s,DATA data)
{
if((s->top+1)>MAXLEN)
{
  cout<<"棧溢出"<<endl;
  return 0;
}
s->data[++s->top]=data;     //將元素壓入棧
return 1;
}
/************************出棧***********************/
DATA * PopST(StackType *s)
{
if(s->top==0)
{
  cout<<"棧為空，不能再輸出！"<<endl;
  exit(0);
}
return &(s->data[s->top--]);
}
/**********************讀取點結(jié)構(gòu)*******************/
DATA *PeekST(StackType *s)
{
if(s->top==0)
{
  cout<<"棧已空"<<endl;
  exit(0);
}
return &(s->data[s->top]);
}
/*****************進(jìn)入主函數(shù)**********************/
int main()
{
StackType *stack;
DATA data,*p_data;
stack=STInit();
cout<<"===============入棧操作：============="<<endl;
cout<<"輸入姓名，年齡進(jìn)行入棧操作："<<endl;
//執(zhí)行入棧操作
while(1)
{
  cin>>data.name>>data.age;
  if(data.name=="0")
  {
   break;      //當(dāng)姓名和年齡都是0的時候退出輸入
  }else
  {
   PushST(stack,data);
  }

}
p_data=PopST(stack);
cout<<"彈出棧頂元素"<<endl;
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
p_data=PeekST(stack);
cout<<"輸出棧頂元素"<<endl;
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
cout<<"================將所有的的數(shù)據(jù)出棧：============="<<endl;
while(1)
{
  p_data=PopST(stack);
  cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
}
STFree(stack);
return 0;
}

程序運行界面：