棧：限定只能在表尾進(jìn)行插入和刪除的線性表鼻种。
兩棧共享空間結(jié)構(gòu)：使用數(shù)組同時(shí)實(shí)現(xiàn)兩個(gè)棧，即棧1和棧2沙热；棧1為空時(shí)叉钥，棧1的棧頂指針指向-1届吁；棧2為空時(shí)捧存，棧2 的棧頂指針指向MAXSIZE扭倾；棧1和棧2添加元素時(shí)甲馋，都會(huì)向數(shù)據(jù)中間靠攏屉凯，當(dāng)棧1的指針+1等于棧2的指針的時(shí)候躺率，棧滿材部。
兩棧共享空間結(jié)構(gòu)特性：
- 在一個(gè)數(shù)據(jù)中同時(shí)存在兩個(gè)棧妒峦，棧頂指針分別為top1寝贡、top2扒披。
- 只能分別在對(duì)應(yīng)的棧頂插入和刪除元素。
- 后進(jìn)先出（Last In First Out）的線性表圃泡，后進(jìn)入的元素先出棧碟案，剩下的元素才能出棧。
優(yōu)點(diǎn)：
- 具有記憶功能颇蜡，可用于表達(dá)式求值等操作价说。
- 添加和刪除元素不需要移動(dòng)大量元素，只需要移動(dòng)棧頂指針风秤。
- 可有效利用剩下的棻钅浚空間。
缺點(diǎn)：
- 只適用于類型相同的兩個(gè)棧缤弦。
- 兩個(gè)棧是此消彼長(zhǎng)的關(guān)系领迈，導(dǎo)致兩個(gè)棧分別的棧長(zhǎng)是動(dòng)態(tài)變化的，無法確定。
時(shí)間復(fù)雜度
- 讀取時(shí)的時(shí)間復(fù)雜度為O(1)狸捅。
- 插入兵迅、刪除時(shí)的時(shí)間復(fù)雜度為O(1)。
空棧示意圖
棧1插入元素示意圖
棧2插入元素示意圖
棧1刪除元素示意圖
棧2刪除元素示意圖
實(shí)現(xiàn)代碼如下：
// 兩棧共享空間
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define OK 1 // 執(zhí)行成功
#define ERROR 0 // 執(zhí)行失敗
#define TRUE 1 // 返回值為真
#define FALSE 0 // 返回值為假
#define MAXSIZE 20 // 存儲(chǔ)空間初始分配大小
typedef int Status; // 函數(shù)返回結(jié)果類型
typedef int ElemType; // 元素類型
// 兩棧共享結(jié)構(gòu)
typedef struct {
ElemType data[MAXSIZE]; // 用于存儲(chǔ)元素值
int top1; // 用于指示棧1的棧頂指針
int top2; // 用于指示棧2的棧頂指針
}SqStack;
/**
* 初始化棧
* @param S 棧
* @return 執(zhí)行狀態(tài)
*/
Status InitStack(SqStack *S) {
S->top1 = -1; // 棧1的棧頂指針指向-1薪贫，此時(shí)棧1為空
S->top2 = MAXSIZE; // 棧2的棧頂指針指向MAXSIZE，此時(shí)棧2為空
return OK;
}
/**
* 清空棧中元素
* @param S 棧
* @return 執(zhí)行狀態(tài)
*/
Status ClearStack(SqStack *S) {
S->top1 = -1; // 棧1的棧頂指針指向-1刻恭，此時(shí)棧1為空
S->top2 = MAXSIZE; // 棧2的棧頂指針指向MAXSIZE瞧省，此時(shí)棧2為空
return OK;
}
/**
* 判斷棧是否為空
* @param S 棧
* @return 執(zhí)行狀態(tài)
*/
Status StackEmpty(SqStack *S) {
// 棧1和棧2都為空時(shí)，棧才為空
if (S->top1 == -1 && S->top2 == MAXSIZE) {
return TRUE;
} else {
return FALSE;
}
}
/**
* 獲取棧中元素個(gè)數(shù)（棧1和棧2的元素總數(shù)）
* @param S 棧
* @return 執(zhí)行狀態(tài)
*/
int StackLength(SqStack *S) {
return (S->top1 + 1) + (MAXSIZE - S->top2);
}
/**
* 獲取棧頂元素的值鳍贾，存到元素e中
* @param S 棧
* @param e 用于存儲(chǔ)棧頂元素的值
* @param stackNumber 棧號(hào)
* @return 執(zhí)行狀態(tài)
*/
Status GetTop(SqStack *S, ElemType *e, int stackNumber) {
// 獲取棧1的棧頂元素值
if (stackNumber == 1) {
// 棧1為空時(shí)鞍匾，獲取棧頂元素失敗
if (S->top1 == -1) {
return ERROR;
}
// 將棧1的棧頂元素的值賦值給e元素
*e = S->data[S->top1];
} else { // 獲取棧2的棧頂元素值
// 棧2為空，獲取棧頂元素失敗
if (S->top2 == MAXSIZE) {
return ERROR;
}
// 將棧2的棧頂元素的值賦值給e元素
*e = S->data[S->top2];
}
return OK;
}
/**
* 添加新元素e到棧頂
* @param S 棧
* @param e 新元素
* @param stackNumber 棧號(hào)
* @return 執(zhí)行狀態(tài)
*/
Status Push(SqStack *S, ElemType e, int stackNumber) {
// 棧滿時(shí)骑科，添加失敗
if (S->top1 + 1 == S->top2) {
return ERROR;
}
// 給棧1添加新元素
if (stackNumber == 1) {
S->data[++S->top1] = e; // 將新元素添加到棧1的棧頂
} else { // 給棧2添加新元素
S->data[--S->top2] = e; // 將新元素添加到棧2的棧頂
}
return OK;
}
/**
* 彈出棧頂元素
* @param S 棧
* @param e 彈出元素
* @param stackNumber 棧號(hào)
* @return 執(zhí)行狀態(tài)
*/
Status Pop(SqStack *S, ElemType *e, int stackNumber) {
// 棧1彈出元素
if (stackNumber == 1) {
// 棧為空時(shí)橡淑，彈出元素失敗
if (S->top1 == -1) {
return ERROR;
}
*e = S->data[S->top1--]; // 將棧頂元素的值賦給e元素，棧1的棧頂指針減1
} else { // 棧2彈出元素
if (S->top2 == MAXSIZE) {
return ERROR;
}
*e = S->data[S->top2++]; // 將棧頂元素的值賦給e元素咆爽，棧2的棧頂指針加1
}
return OK;
}
/**
* 打印單個(gè)元素的值
* @param e 元素
* @return 執(zhí)行狀態(tài)
*/
Status visit(ElemType e) {
printf("%d ", e);
return OK;
}
/**
* 從棧底開始遍歷棧中元素
* @param S 棧
* @return 執(zhí)行狀態(tài)
*/
Status StackTraverse(SqStack S) {
int i = 0; // 指示器梁棠，用于指示棧頂指針的位置
printf("棧1中的元素為：[ ");
// 指示器位置小于棧1的棧頂指針
while (i <= S.top1) {
visit(S.data[i++]); // 打印i位置元素，i向下一個(gè)元素移動(dòng)
}
printf("]\n");
i = MAXSIZE - 1;
printf("棧2中的元素為：[ ");
while (i >= S.top2) {
visit(S.data[i--]);
}
printf("]\n");
return OK;
}
int main() {
int j; // 用于遍歷
SqStack s; // 棧
ElemType e; // 元素
// 如果初始化成功
if (InitStack(&s) == OK) {
// 向棧1中插入5個(gè)元素
for (j = 1; j <= 5; j++) {
Push(&s, j, 1); // 向棧1的棧頂插入元素j
}
// 向棧2中插入5個(gè)元素
for (j = MAXSIZE; j > MAXSIZE - 5; j--) {
Push(&s, j, 2); // 向棧2的棧頂插入元素j
}
}
printf("棧中的元素如下：\n");
StackTraverse(s); // 遍歷棧中元素
Pop(&s, &e, 1); // 彈出棧1的棧頂元素
printf("彈出的棧頂元素為：e = %d\n", e);
printf("彈出一個(gè)元素之后斗埂，棧是否為空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");
GetTop(&s, &e, 1); // 獲取棧1的棧頂元素的值
printf("棧1的棧頂元素的值為：e = %d\n", e);
GetTop(&s, &e, 2); // 獲取棧1的棧頂元素的值
printf("棧2的棧頂元素的值為：e = %d\n", e);
printf("棧的長(zhǎng)度為：%d\n", StackLength(&s)); // 獲取棧的長(zhǎng)度
ClearStack(&s); // 清空棧中元素
printf("清空棧后符糊，棧是否為空：%s\n", StackEmpty(&s) == TRUE ? "是" : "否");
return 0;
}
運(yùn)行結(jié)果
