C++ 棧和隊列的介紹與使用

C++ 棧和隊列的介紹與使用

使用標准庫的棧和隊列時，先包含相關的頭文件

#include

#include

定義棧如下：

stack stk;

定義隊列如下：

queue q;

棧提供了如下的操作

s.empty()               如果棧為空返回true，否則返回false
s.size()                返回棧中元素的個數
s.pop()                 刪除棧頂元素但不返回其值
s.top()                 返回棧頂的元素，但不刪除該元素
s.push()                在棧頂壓入新元素

隊列提供了下面的操作

q.empty()               如果隊列為空返回true，否則返回false
q.size()                返回隊列中元素的個數
q.pop()                 刪除隊列首元素但不返回其值
q.front()               返回隊首元素的值，但不刪除該元素
q.push()                在隊尾壓入新元素
q.back()                返回隊列尾元素的值，但不刪除該元素

c++stack(堆棧）

它是一個容器的改編，它實現了一個先進後出的數據結構（FILO）

使用該容器時需要包含#include頭文件；

定義stack對象的示例代碼如下：

stacks1;

stacks2;

stack的基本操作有：

1.入棧：如s.push(x);

2.出棧:如 s.pop().注意：出棧操作只是刪除棧頂的元素，並不返回該元素。

3.訪問棧頂：如s.top();

4.判斷棧空：如s.empty().當棧空時返回true。

5.訪問棧中的元素個數，如s.size（）;

下面舉一個簡單的例子：

    #include  
    #include  
    using namespace std;  
    int main(void)  
    {  
        stacks;//定義一個棧  
        for(int i=0;i<10;i++)  
            s.push(i);  
        while(!s.empty())  
        {  
            printf("%lf\n",s.top());  
            s.pop();  
        }  
        cout<<"棧內的元素的個數為："<
棧的定義：
棧是限定僅在表尾進行插入或刪除操作的線性表，因此表尾端成為棧頂，相應的，表頭端成為棧底，不含有任何元素的棧稱為空棧。
棧的修改遵循後進先出的原則，因此棧又稱為後進先出的線性表，簡稱LIFO結構。
棧一般采用數組作為其存儲結構，這樣做可以避免使用指針，簡化程序，當然數組需要預先聲明靜態數據區的大小，但這不是問題，因為即便是頻繁進出入棧操作，任何時刻棧元素的實際個數也不會很多，為棧預留一個足夠大但又不占用太多空間並不是很困難，如果不能做到這一點，那麼節省內存的方法就是使用鏈表存儲棧。

線性表實現棧的基本操作
    #include  
    #include  
    using namespace std;  
    typedef struct Stacknode//定義鏈式棧的結構體  
    {  
        int data;//數據域  
        Stacknode *next;//下一節點的指針域  
    }Stacknode,*Stack;  
    //初始化一個鏈式棧（返回一個鏈式棧的頭節點）  
    Stack InitStack()  
    {  
        Stack stack=(Stack)malloc(sizeof(Stacknode));  
        stack->next=NULL;  
        return stack;  
    }  
    //入棧  
    void Push(Stack stack,int newData)  
    {  
        //判斷是否為空  
        if(stack==NULL)  
        {  
            printf("棧未初始化，請初始化以後再使用\n");  
            return;  
        }  
        //找到最後一個節點  
       Stacknode *lastnode=stack;  
       while(lastnode->next)  
        {  
        lastnode=lastnode->next;  
        }  
       lastnode->next=(Stacknode*)malloc(sizeof(Stacknode*));  
       lastnode->next->data=newData;  
       lastnode->next->next=NULL;  
       printf("入棧成功！\n");  
    }  
    //出棧  
    int Pop(Stack stack)  
    {  
        //判斷棧是否為空  
        if(!stack->next)  
        {  
            printf("棧為空，無法出棧\n");  
            return -1;//-1只是一個自定義的錯誤代碼  
        }  
        //找到最後一個節點的錢一個節點  
        //tempNode:最後一個節點的前一個節點  
        Stacknode *tempNode=stack;  
        while(tempNode->next->next)  
        {  
            tempNode=tempNode->next;  
        }  
        int data=tempNode->next->data;  
        free(tempNode->next);  
        tempNode->next=NULL;  
        return data;  
    }  
      
    int main()  
    {  
        Stack stack=InitStack();  
        Push(stack,3);//3進棧  
        Push(stack,4);//4進棧  
        Push(stack,5);//5進棧  
        printf("%d\n",Pop(stack));  
        printf("%d\n",Pop(stack));  
        printf("%d\n",Pop(stack));  
        printf("%d\n",Pop(stack));//第4次出棧，應該出錯  
        return 0;  
    }  
 
C++ Queue（隊列）
 
queue模版類的定義在頭文件中。
queue與stack模版非常類似，queue模版也需要定義兩個模版參數，一個是元素類型，一個是容器類型，元素類型是必要的，容器類型是可選的，默認為dqueue類型。
定義queue對象的示例代碼如下：
queueq1;
queueq2;
queue的基本操作有：
1.入隊：如q.push(x):將x元素接到隊列的末端；
2.出隊：如q.pop() 彈出隊列的第一個元素，並不會返回元素的值；
3,訪問隊首元素：如q.front()
4,訪問隊尾元素，如q.back();
5,訪問隊中的元素個數，如q.size();
二.優先隊列
在頭文件中，還定義了一個非常有用的模版類priority_queue(優先隊列），優先隊列與隊列的差別在於優先隊列不是按照入隊的順序出隊，而是按照隊列中元素的優先權順序出隊（默認為大者優先，也可以通過指定算子來指定自己的優先順序）默認是一個大根堆。
priority_queue模版類有三個模版參數，元素類型，容器類型，比較算子。其中後兩個都可以省略，默認容器為vector，默認算子為less，即小的往前排，大的往後排（出隊時序列尾的元素出隊）。
定義priority_queue對象的示例代碼如下：
priority_queueq1;
priority_queue >q2;
priority_queue，greater >q3;//定義小的先出隊
priority_queue的基本操作均與queue相同
初學者在使用priority_queue時，最困難的可能就是如何定義比較算子了。如果是基本數據類型，或已定義了比較運算符的類，可以直接用STL的less算子和greater算子——默認為使用less算子，即小的往前排，大的先出隊。如果要定義自己的比較算子，方法有多種，這裡介紹其中的一種：重載比較運算符。優先隊列試圖將兩個元素x和y代入比較運算符(對less算子，調用xy)，若結果為真，則x排在y前面，y將先於x出隊，反之，則將y排在x前面，x將先出隊。
看下面這個簡單的示例：
    #include  
    #include  
    #include  
    using namespace std;  
    class T  
    {  
    public:  
        int x,y,z;  
        T(int a,int b,int c):x(a),y(b),z(c)  
        {  
        }  
    };  
    bool operator<(const T&t1,const T&t2)  
    {  
        return t1.zq;  
        q.push(T(4,4,3));  
        q.push(T(2,2,5));  
        q.push(T(1,5,4));  
        q.push(T(3,3,6));  
        while(!q.empty())  
        {  
            T t=q.top();  
            q.pop();  
            cout<