多棧共享技術(shù)，雙端棧的初始化、進(jìn)棧、出棧操作

    棧的應(yīng)用非常廣泛，經(jīng)常會(huì)出現(xiàn)一個(gè)程序中需要同時(shí)使用多個(gè)棧的情況。若使用順序棧，會(huì)因?yàn)閷?duì)?？臻g大小難以準(zhǔn)確估計(jì)，從而產(chǎn)生有的棧溢出、有的?？臻g還很空閑的情況。為了解決這個(gè)問(wèn)題，可以讓多個(gè)棧共享一個(gè)足夠大的數(shù)組空間，通過(guò)利用棧的動(dòng)態(tài)特性來(lái)使其存儲(chǔ)空間互相補(bǔ)充，這就是多棧的共享技術(shù)。

    在順序棧的共享技術(shù)中，最常用的是兩個(gè)棧的共享技術(shù)，即雙端棧。它主要利用了棧的棧底位置不變，而棧頂位置動(dòng)態(tài)變化的特性。

實(shí)現(xiàn)代碼如下：

#include<iostream>

using namespace std;

#define  TRUE 1

#define  FALSE 0

#define M 100 

//雙端順序棧的存儲(chǔ)結(jié)構(gòu)

typedef struct

{

int Stack[M];//Stack[M]為棧區(qū)

int top[2];//top[0]和top[1]分別為兩個(gè)棧頂指示器

}DqStack;

//初始化雙端順序棧

void InitStack(DqStack *S)

{

S->top[0] = -1;

S->top[1] = M;

}

//雙端順序棧進(jìn)棧操作

int Push(DqStack *S,int x,int i)//把數(shù)據(jù)元素x壓入i號(hào)堆棧

{

if (S->top[0]+1 == S->top[1])//棧已滿

{

return FALSE;

}

switch (i)

{

case 0:   //0號(hào)棧

S->top[0]++;

S->Stack[S->top[0]] = x;

break;

case 1:   //1號(hào)棧

S->top[1]--;

S->Stack[S->top[1]] = x;

break;

default:    //參數(shù)錯(cuò)誤

return FALSE;

break;

}

return TRUE;

}

//雙端順序棧出棧操作

int Pop(DqStack *S, int *x, int i)//從i號(hào)堆棧中彈出棧頂元素并送到x中

{

switch (i)

{

case 0:   //0號(hào)棧出棧

if (S->top[0] ==-1)

{

return FALSE;

}

*x=S->Stack[S->top[0]] ;

S->top[0]--;

break;

case 1:   //1號(hào)棧出棧

if (S->top[1] == M)

{

return FALSE;

}

*x = S->Stack[S->top[1]];

S->top[1]++;

break;

default:    

return FALSE;

break;

}

return TRUE;

}