資料結構——順序棧

棧

• 定義：隻能在表的一端（棧頂）進行插入和删除運算的線性表
• 邏輯結構：一對一關系
• 存儲結構
  • 順序棧
  • 鍊棧
• 運算規則：隻能在棧頂運算，且通路結點時依照後進先出（LIFO）或先進後出（FILO）的原則
• 實作方式
  • 入棧
  • 出棧
  • 讀棧頂元素值
  • 建棧
  • 判斷棧空
  • 判斷棧慢
  • 清空棧
  • 銷毀棧

棧的表示和操作的實作

順序棧的C++代碼實作

#include<iostream>
using namespace std;

#define OVERFLOW -2 
#define OK 1
#define NULL 0
#define ERROR -1

#define MAXSIZE 100  // 最大空間

typedef int SElemType;
typedef int Status;

typedef struct {
    SElemType* base;
    SElemType* top;
    int stacksize;
}SqStack;

// 順序棧初始化
Status InitStack(SqStack& S) {
    S.base = new SElemType[MAXSIZE];
    if (!S.base) return OVERFLOW;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

// 判斷順序棧是否為空
bool StackEmpty(SqStack S) {
    if (S.top == S.base) return true;
    else return false;
}

// 判斷是否為滿棧
bool StackFull(SqStack S) {
    if (S.top - S.base >= S.stacksize) 
        return true;
    else return false;
}

// 順序棧的長度
int StackLength(SqStack S) {
    return S.top - S.base;
}

// 輸出棧頂元素
Status Gettop(SqStack S, SElemType& e) {
    // SElemType* p;
    if (StackEmpty(S))  // 棧空
        return ERROR;
    // p = S.top - 1;
    // e = *p;
    e = *(S.top - 1);
    return OK;
}

// 入棧
Status Push(SqStack& S, SElemType e) {
    if (StackFull(S))  // 滿棧 
        return ERROR;
    *S.top++ = e;
    // *S.top = e;
    // S.top ++;
    return OK;
}

// 出棧
Status Pop(SqStack& S, SElemType& e) {
    if (StackEmpty(S))  // 棧空
        return ERROR;
    e = *--S.top;
    // S.top --;
    // e = *S.top;
    return OK;
}

// 清空順序棧
Status ClearStack(SqStack& S) {
    // S.stacksize = 0;
    if(S.base) S.top = S.base;
    cout << "清空成功！" << endl;
    return OK;
}

// 銷毀順序棧
Status DestroyStack(SqStack& S) {
    if (S.base) {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    cout << "銷毀成功！" << endl;
    return OK;
}

// 輸入
void Creat(SqStack& S, int m) {
    int i;
    SElemType x;
    for (i = 1; i < m + 1; i++) {
        cout << "請輸入第" << i << "個元素: ";
        cin >> x;
        Push(S, x);
    //    S.stacksize++;
    }
}

// 輸出
void OutPut(SqStack S) {
    SElemType* p;
    p = S.base;
    while (p < S.top)
        cout << *p++ << " ";
    cout << endl;
}

int main()
{
    int m;
    SElemType e;
    SqStack S;

    /*---------------測試--------------*/
    InitStack(S);

    cout << "請輸入棧的長度: ";
    cin >> m;
    Creat(S, m);
    cout << "棧中元素為: ";
    OutPut(S);

    cout << "順序棧的長度為: ";
    cout << StackLength(S) << endl;

    // 入棧測試
    cout << "請輸入入棧元素: ";
    cin >> e;
    Push(S, e);
    cout << "棧中元素為: ";
    OutPut(S);

    cout << "順序棧的長度為: ";
    cout << StackLength(S) << endl;

    // 擷取棧頂元素測試
    Gettop(S, e);
    cout << "棧頂元素為: " << e <<endl;

    cout << "順序棧的長度為: ";
    cout << StackLength(S) << endl;

    // 出棧測試
    Pop(S, e);
    cout << "彈出的元素為: " << e << endl;

    cout << "棧中元素為: ";
    OutPut(S);

    cout << "順序棧的長度為: ";
    cout << StackLength(S) << endl;

    // 清空測試
    ClearStack(S);
    cout << "順序棧的長度為: ";
    cout << StackLength(S) << endl;

    // 銷毀測試
    DestroyStack(S);
    return 0;
}           

請輸入棧的長度: 3
請輸入第1個元素: 1
請輸入第2個元素: 2
請輸入第3個元素: 3
棧中元素為: 1 2 3
順序棧的長度為: 3
請輸入入棧元素: 7
棧中元素為: 1 2 3 7
順序棧的長度為: 4
棧頂元素為: 7
順序棧的長度為: 4
彈出的元素為: 7
棧中元素為: 1 2 3
順序棧的長度為: 3
清空成功！
順序棧的長度為: 0
銷毀成功！