一亿鲜、棧的相關(guān)知識(shí)

棧的定義：

是限定僅在表尾進(jìn)行插入和刪除操作的線性表核蘸。
我們把允許插入和刪除的一端稱為棧頂（top）叔收，另一端稱為棧底（bottom）撤奸，不含任何數(shù)據(jù)元素的棧稱為空棧隔节。棧又稱為后進(jìn)先出（Last In First Out，LIFO）的線性表寂呛。

理解棧的定義需要注意：

• 首先他是一個(gè)線性表，元素具有線性關(guān)系瘾晃，即前驅(qū)后繼關(guān)系贷痪。
• 這里的表尾指的是棧定而不是棧底。
• 棧的插入操作叫做進(jìn)棧蹦误，或者壓棧劫拢，入棧肉津。棧的刪除動(dòng)作叫做出棧，也叫彈棧舱沧。

進(jìn)棧出棧變化形式：

問題：最先進(jìn)棧的元素妹沙，是不是就只能最后出棧呢？
答：不一定熟吏。因?yàn)闆]有對(duì)棧內(nèi)元素出入時(shí)間做限制距糖。在不是所有元素都進(jìn)棧的情況下，事先進(jìn)去的元素也可以出棧牵寺，只要保證是棧頂元素即可悍引。
舉例：有三個(gè)數(shù)字1,2,3依次進(jìn)棧，有哪些出棧次序呢帽氓？

• 第一種：1,2,3進(jìn)趣斤，3,2,1出。
• 第二種：1進(jìn)黎休，1出浓领，2進(jìn)，2出势腮，3進(jìn)联贩，3出。即1嫉鲸，2撑蒜，3出。
• 第三種：1,2進(jìn)玄渗，2出座菠，1出，3進(jìn)藤树，3出浴滴。即2,1,3出。
• 第四種：1進(jìn)岁钓，1升略，2，3進(jìn)屡限，3出品嚣，2出。即1,3,2出钧大。
• 第五種：1翰撑，2進(jìn)，2出啊央，3進(jìn)眶诈，3出涨醋，1出。即2,3,1出逝撬。
• 不可能為3,1,2出浴骂。因?yàn)?進(jìn)，1,2必然進(jìn)宪潮。2在1上面溯警，因此如果3出了，必先出2坎炼。

棧的順序存儲(chǔ)結(jié)構(gòu)

• 順序線性表用數(shù)組可以實(shí)現(xiàn)愧膀，下標(biāo)為0作為棧底。
• 定義一個(gè)top變量來指示棧頂元素在數(shù)組中的位置谣光。StackSize為存儲(chǔ)棧的長(zhǎng)度檩淋。因此棧頂位置top必須小徐StackSize。
• 當(dāng)棧存在一個(gè)元素時(shí)萄金，top等于0蟀悦，空棧時(shí)top=-1。

兩棧共享空間

提出思路：因?yàn)橛械臅r(shí)候?qū)τ趦蓚€(gè)棧氧敢，類型相同日戈，而其中一個(gè)利用率不高，另一個(gè)卻有快溢出跡象的時(shí)候孙乖，可以將兩個(gè)棧共享使用浙炼，使得利用率提高。
做法：數(shù)組有兩個(gè)端點(diǎn)唯袄，兩個(gè)棧有兩個(gè)棧底弯屈，讓一個(gè)棧底下標(biāo)為0，另一個(gè)棧底為數(shù)組的末端恋拷，即下標(biāo)為n-1资厉。這樣兩個(gè)棧增加元素就是兩端點(diǎn)向中間延伸。
由此可見蔬顾，top1和top2是棧1和棧2的棧頂指針宴偿，只要它們倆不見面，兩個(gè)棧就可以一直使用诀豁。
棧1為空時(shí)窄刘，top1=-1，棧2位空時(shí)舷胜，top2=n都哭。
問題：什么時(shí)候棧滿？
答：想想極端情況。

• 若棧2是空棧欺矫，棧1的top1=n-1時(shí)，棧1滿了展氓。反之穆趴，當(dāng)棧1為空棧，top2=0時(shí)遇汞，為棧2滿未妹。
• 但更多的情況，其實(shí)就是兩個(gè)棧見面之時(shí)空入，也就是兩個(gè)指針相差為1——top1+1=top2為棧滿络它。

使用條件：通常是兩個(gè)棧的空間需求有相反關(guān)系，也即一個(gè)棧增長(zhǎng)另一個(gè)椡嵊縮短化戳。像買股票一樣，一個(gè)人買入一定有一個(gè)你不知道的人在賣出埋凯。有人賺錢点楼，另一個(gè)人就賠錢。

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

• 規(guī)定棧頂放在單鏈表的頭部白对。
• 鏈棧的好處是不用過多考慮棧滿的情況掠廓，除非內(nèi)存已經(jīng)沒有可以使用的空間。如果真的發(fā)生甩恼，那此時(shí)計(jì)算機(jī)操作系統(tǒng)已經(jīng)面臨死機(jī)崩潰的情況蟀瞧，而不是這個(gè)鏈棧是否溢出的問題了。
• 對(duì)于空棧來說条摸，鏈表原定義是頭指針指向空悦污，那么鏈棧的空其實(shí)就是top==NULL的時(shí)候。

二屈溉、代碼實(shí)現(xiàn)

順序棧的代碼實(shí)現(xiàn)

//SeqStack.h
#ifndef SEQSTACK_H_
#define SEQSTACK_H_
const int StackSize = 40;
class SeqStack
{
private:
    int top;
    int num[StackSize];
public:
    SeqStack();
    ~SeqStack();
    void Push(int e);
    void Pop();
    bool isempty();
    bool isfull();
    void clear();
    void Print();
};
#endif

頭文件SeqStack.h塞关，包含了入棧出棧判斷里面是否是滿的以及清空等功能。
這個(gè)棧存儲(chǔ)了一個(gè)int數(shù)組子巾。

#include<iostream>
#include"SeqStack.h"
using std::cout;
using std::endl;
SeqStack::SeqStack():top(-1){}
SeqStack::~SeqStack(){}
void SeqStack::Push(int e)
{
    if(isfull())
    {
        cout << "Stack is Full!Push failed." << endl;
        return;
    }
    num[++top] = e;
}
void SeqStack::Pop()
{
    if(isempty())
    {
        cout << "Stack is Empty!Pop failed." << endl;
        return;
    }
    top--;
}
bool SeqStack::isempty()
{
    if(top == -1)
    {
        cout << "Stack is empty!" << endl;
        return true;
    }
    return false;
}
bool SeqStack::isfull()
{
    if(top == StackSize - 1)
    {
        cout << "Stack is full!" << endl;
        return true;
    }
    return false;
}
void SeqStack::clear()
{
    if(isempty())
        cout << "SeqStack is already empty!" << endl;
    while(top!=-1)
    {
        Pop();
        top--;
    }
}
void SeqStack::Print()
{
    if(isempty())
        cout << "No elements printed." << endl;
    for(int i=0;i<top;i++)
        cout << num[i] << " ";
    cout << endl;
}

函數(shù)實(shí)現(xiàn)SeqStack.cpp帆赢，可以自己建立一個(gè)簡(jiǎn)單的程序驗(yàn)證一下，這里不再贅述线梗。

鏈棧的代碼實(shí)現(xiàn)

//LinkStack.h
#ifndef LINKSTACK_H_
#define LINKSTACK_H_
class LinkStack
{
private:
    struct StackNode
    {
        int num;//存儲(chǔ)數(shù)據(jù)
        StackNode * next;//next指針
    };
    StackNode * top;
    int length;
public:
    LinkStack();
    ~LinkStack();
    void Push(int e);
    void Pop();
    bool isempty();
    void clear();
    void Print();
};
#endif

鏈棧頭文件椰于，存儲(chǔ)變量和方法。

//LinkStack.cpp
#include<iostream>
#include"LinkStack.h"
using std::cout;
using std::endl;
LinkStack::LinkStack()
{
    top = NULL;
    length = 0;
}
LinkStack::~LinkStack()
{
}
void LinkStack::Push(int e)
{
    StackNode * p = new StackNode;
    p->num=e;
    p->next=top;
    top=p;
    length++;
}
void LinkStack::Pop()
{
    StackNode * p = new StackNode;
    if(top == NULL)
    {
        cout << "The LinkStack is empty!Cannot pop!" << endl;
        return;
    }
    p=top;
    top=top->next;
    delete p;
    length--;
}
void LinkStack::clear()
{
    while(top)
    {
        StackNode * temp = top;
        top = top->next;
        delete temp;
        length--;
    }
}
void LinkStack::Print()
{
    if(top == NULL)
    {
        cout << "No elements!" << endl;
        return;
    }
    StackNode * temp = top;
    while(temp)
    {
        cout << temp->num << " ";
        temp = temp->next;
    }
    cout << endl;
}