共享棧為空的狀態，左右兩棧的棧頂指針都在兩端，也就是各自棧的棧底

代碼當中測試棧滿的時候的狀態圖

?共享棧的數據結構

typedef struct{int elem[maxSize];int top[2]; }SqStack;

入共享棧的操作，因為共享棧是由兩個棧組成的，因此我們在入棧的時候需要選擇入棧的編號，也就是stNo，同時要注意棧滿的特殊情況

int push(SqStack &st, int stNo, int x){if (st.top[0]+1<st.top[1]){ //先判斷棧是否是滿的if (stNo==0){++(st.top[0]);st.elem[st.top[0]]=x;return 1; //入棧成功}else if (stNo==1){--(st.top[1]);st.elem[st.top[1]]=x;return 1;}elsereturn -1;}elsereturn 0; //入棧失敗 }

出棧操作，同樣需要指定出棧的編號，同時還需要處理指定的棧棧中元素是否為空的特殊情況

int pop(SqStack &st, int stNo, int &x){if (stNo==0){if (st.top[0]!=-1){ //驗證棧是否為空x=st.elem[st.top[0]];--(st.top[0]);return 1; //出棧成功}elsereturn 0; //出棧失敗}else if (stNo==1){if (st.top[1]!=maxSize){x=st.elem[st.top[1]];++(st.top[1]);return 1;}elsereturn 0; //出棧失敗}elsereturn -1; //棧編號輸入錯誤 }

判斷共享棧是否是滿的

int isEmpty(SqStack st){if (st.top[0]+1==st.top[1])return 1;elsereturn 0; }

我只寫了這三種基本操作，此外還可以自行添加返回棧頂元素的操作

下為完整的代碼，可直接運行

#include <stdio.h>#define maxSize 5typedef struct{int elem[maxSize];int top[2]; }SqStack;//初始化 void init(SqStack &st){st.top[0]=-1;st.top[1]=maxSize; }//入棧操作 //stNo是棧的編號，x是入棧元素 int push(SqStack &st, int stNo, int x){if (st.top[0]+1<st.top[1]){ //先判斷棧是否是滿的if (stNo==0){++(st.top[0]);st.elem[st.top[0]]=x;return 1; //入棧成功}else if (stNo==1){--(st.top[1]);st.elem[st.top[1]]=x;return 1;}elsereturn -1;}elsereturn 0; //入棧失敗 }//出棧 int pop(SqStack &st, int stNo, int &x){if (stNo==0){if (st.top[0]!=-1){ //驗證棧是否為空x=st.elem[st.top[0]];--(st.top[0]);return 1; //出棧成功}elsereturn 0; //出棧失敗}else if (stNo==1){if (st.top[1]!=maxSize){x=st.elem[st.top[1]];++(st.top[1]);return 1;}elsereturn 0; //出棧失敗}elsereturn -1; //棧編號輸入錯誤 }//判斷是否棧滿，1為滿，0為不滿 int isEmpty(SqStack st){if (st.top[0]+1==st.top[1])return 1;elsereturn 0; }//打印棧 void printStack(SqStack st){printf ("當前棧中元素是：");for (int i=0; i<=st.top[0]; i++){printf ("%d ", st.elem[i]);}for (int i=st.top[1]; i<maxSize; i++){printf ("%d ", st.elem[i]);}printf ("\n"); }int main(){SqStack st;init(st);push(st, 0, 5);push(st, 0, 2);push(st, 0, 3);push(st, 1, 6);push(st, 1, 9);push(st, 1, 8);if (isEmpty(st)){printf ("棧滿！\n");}int x;pop(st, 1, x);printf ("出棧元素是：%d\n", x);printStack(st);return 0; }

?

總結

以上是生活随笔為你收集整理的《天勤数据结构》笔记——使用两个栈实现共享栈实现（C/C++）的全部內容，希望文章能夠幫你解決所遇到的問題。

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