使用標准庫的棧和隊列時,先包含相關的頭文件
#include
#include
定義棧如下:
stack
定義隊列如下:
queue
棧提供了如下的操作
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() 返回隊列尾元素的值,但不刪除該元素
它是一個容器的改編,它實現了一個先進後出的數據結構(FILO)
使用該容器時需要包含#include
定義stack對象的示例代碼如下:
stack
stack
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) { stack s;//定義一個棧 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對象的示例代碼如下:
queue
q1; queue
q2; 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_queue
q1; priority_queue
>q2; priority_queue
,greater >q3;//定義小的先出隊 priority_queue的基本操作均與queue相同
初學者在使用priority_queue時,最困難的可能就是如何定義比較算子了。如果是基本數據類型,或已定義了比較運算符的類,可以直接用STL的less算子和greater算子——默認為使用less算子,即小的往前排,大的先出隊。如果要定義自己的比較算子,方法有多種,這裡介紹其中的一種:重載比較運算符。優先隊列試圖將兩個元素x和y代入比較運算符(對less算子,調用x
y),若結果為真,則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.z q; 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<