概述

棧是一種限定僅在一端進(jìn)行插入和刪除的線性表。這一端被稱為棧頂（top），棧的另一端叫做棧底（bottom）。通常，最先被壓入棧中的元素會被放在棧底，后被壓入的元素處于棧頂，出棧時，取出棧頂元素，因此通常為后進(jìn)先出。

棧的經(jīng)典應(yīng)用有符號平衡的判斷，后綴表達(dá)式求值等等問題。具體代碼將在下一篇文章中給出。

基于棧的特性，一般常用的操作有：進(jìn)棧push、出棧pop、讀棧頂top、判斷棧是否為空isEmpty和判斷棧是否已滿isFull。以下為C++的抽象數(shù)據(jù)類型定義，包含基本操作。

棧類抽象數(shù)據(jù)類型定義

下面給出C++類模板，名字為Stack，模板參數(shù)為元素類型T。

template <class T>
class Stack{

public:
    void clear();
        bool push(const T item);
        bool pop(T & item);
        bool top(T & item);
        bool isEmpty();
        bool isFull();

基本操作

基本操作分為進(jìn)棧push、出棧pop、讀棧頂top等。

• push進(jìn)棧

首先判斷棧是否已滿，即top指針是否指向棧頂，判斷句為：

//判斷棧是否已滿
if(top == mSize - 1){
        cout << "stack is full, cannot push element!" << endl;

類似的，判斷棧是否為空，即top指針是否指向棧底下一位，一般為-1，判斷句為：

//判斷棧是否為空
if(top == -1){
            cout << "empty" << endl;

當(dāng)入棧時，將top指針的元素內(nèi)容設(shè)定為value，然后將top指針上移一位修改棧頂指針，實(shí)現(xiàn)代碼如下：

//入棧
void push(T item){
    if(top == mSize - 1){
        cout << "stack is full, cannot push element!" << endl;
        return;
    }
    else{
        st[++top]=item;
        cout<<"入棧："<<item<<endl;
    }
}

• pop出棧

出棧時，每次只能移出棧頂元素。首先設(shè)定棧頂元素為item=stack[top]，再將top指針向下移動一位，即top--。如果top=-1時（棧為空），則無法出棧，輸出empty。具體實(shí)現(xiàn)代碼如下：

void pop(int &m){
    // should be equal, not assignment
    if(top == -1){
        cout << "empty" << endl;
    }
    else{
        m=st[top--];
        cout<<"出棧："<<m<<endl;
    }
}

• top讀取棧頂元素

即讀取棧頂元素但不彈出。僅讓item=stack[top]，top不做改變。代碼 如下：

void getop(int &t){
    if(top ==-1){
        cout<<"empty!"<<endl;
    }
    else{
        t=st[top];
        cout<<"獲得棧頂元素："<<t<<endl;
    }
}

?？傮w程序

實(shí)現(xiàn)功能：
1.首先輸入棧長度。
2.輸入操作指令：1、入棧。2、出棧。3、查看棧頂元素。4、查看棧信息（最大長度與現(xiàn)在長度）。

#include <iostream>
#include <stdio.h>

using namespace std;

template <class T>

class arrStack{
private:
    int mSize;
    int top;
    T *st;

public:
    arrStack(int size){
        mSize=size;
        top=-1;
        st=new T[mSize];
    }

    ~arrStack(){
        delete[]st;
    }

    void clear(){
        top=-1;
    }

    void push(T item){
        if(top == mSize - 1){
            cout << "stack is full, cannot push element!" << endl;
            return;
        }
        else{
            st[++top]=item;
            cout<<"入棧："<<item<<endl;
        }
    }

    void pop(int &m){
        if(top == -1){
            cout << "empty" << endl；
        }
        else{
            m=st[top--];
            cout<<"出棧："<<m<<endl;
        }
    }

    void getop(int &t){
        if(top ==-1){
            cout<<"empty!"<<endl;
        }
        else{
            t=st[top];
            cout<<"獲得棧頂元素："<<t<<endl;
        }
    }

    int getMessage(int &m, int &n){
        m=mSize;
        n=top+1;
        cout<<"棧最大長度為："<<m<<"\n棧長為："<<n<<endl;
        return 0;
    }
};

int main(){
    int a;//length
    int e;//switch
    int i=0;
    int m;//message
    int n;//message
    int f;//pop
    int t;//getop
    int num;
    printf("請輸入棧長度：");
    cin>>a;
    arrStack<int> s(a);

    while(1){   
        cout<<"-----------------------------------------------\n"<<endl;
        cout<<"請輸入操作單位：\n1：入棧\n2：出棧\n3：獲取棧頂元素\n4：獲取棧信息\n"<<endl;
        cin>>e;
    switch(e){
        case(1):
            cout<<"請輸入入棧元素："<<endl;
            cin >>num;
            s.push(num);
            break;
        case(2):
            s.pop(f);
            break;
        case(3):
            s.getop(t);
            break;
        case(4):
            s.getMessage(m,n);
            break;
            }
    }
    system("pause");
    return 1;
}

結(jié)果：

Paste_Image.png

總結(jié)

新手上路，有缺陷的地方望指出，進(jìn)步你我他~
現(xiàn)在再從頭寫一遍棧的內(nèi)容，感覺老師講過的東西都能明白了，也能明白她為什么這么講。
一開始剛接觸算法，不知道如何將算法和main函數(shù)結(jié)合起來，感謝導(dǎo)師幫我寫了個簡單的push(1/2/3)例子，讓我能順?biāo)浦鄣陌颜麄€程序?qū)懲辍?br> 第二個遇到的是語法上的問題。比如說指針如何使用，int函數(shù)里返回值應(yīng)該寫什么，pop函數(shù)括號里為空時如何執(zhí)行，有具體數(shù)值時如何執(zhí)行。最后我把它們都弄懂了，也算是巨大的飛躍！估計下一個鏈?zhǔn)綉?yīng)該寫的更順一些。
這是我的第一篇簡書！也是我除了hellow world的第一個真正意義上自己動手寫的c++程序！！希望十年后可以再回頭來看看它。