雙棧結構

要求

要求編寫雙棧初始化,判斷棧空、棧滿、進棧和出棧
已知的雙棧結構：

typedef struct {int top[2], bot[2]; //棧頂和棧底指針SElemType *V; //棧數組int m； //棧最大可容納元素 } DblStack;

算法思想

兩棧共享向量空間，把棧的棧底設置在左右兩端，初始時，左棧的棧底等于棧頂等于－1；右棧的棧底等于棧頂等于m;

兩棧的棧頂相鄰時棧滿(右棧頂－左棧頂 ＝ 1)

兩棧頂相向增長，棧頂指針指向棧頂元素。

左棧執行進棧操作時候，棧頂元素(右移)＋1；出棧時棧頂元素(左移)－1;

右棧執行進棧操作時候，棧頂元素(左移)－1；出棧時棧頂元素(右移)＋1；

算法實現

初始化雙棧Status InitStack(DblStack &S, int m){S.V = new SElemType[m];//初始化數組空間if(!S.V) return Error;S.bot[0] = -1;//左棧的棧底指針S.top[0] = -1;//左棧的棧頂指針S.bot[1] = m;//右棧的棧底指針S.top[1] = m;//右棧的棧頂指針return OK; }

判斷棧空int IsEmpty(DblStack S){return S.top[i] == S.bot[i]; }

判斷棧滿int IsFull(DblStack S) {if (S.top[1] - top[0] == 1) return 1;else return 0; }

指定棧插入元素Status DblPush(DblStack S, int i, SElemType x) {//判斷棧滿if (S.top[1] - top[0] == 1) return ERROR;if (i == 0) S.V[++S.top[0]] = x;else S.V[--S.top[1]] = x;return OK; }

指定棧刪除元素Status DblPop(DblStack &S, int i, SElemType &x) {//判斷棧空if (S.top[i] == S.bot[i]) return ERROR;if (i == 0) x = S.V[S.top[0]--];else x = S.V[S.top[1]++];return OK; }

總結

以上是生活随笔為你收集整理的[算法设计题] 双栈结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。