前言

應用：瀏覽器的前進、后退功能

一、棧的概述

棧（stack）是限定僅在表尾（棧頂）進行插入和刪除操作的線性表。
棧頂（top）：允許插入和刪除的一端，另一端成為棧底（bottom）

后進先出（Last In First Out，LIFO），先進后出
==》只允許在一端插入和刪除數據。

棧主要包含兩個操作：進棧和出棧 ，也就是在棧頂插入一個數據和從棧頂刪除一個數據。
其中，入棧也稱壓棧、入棧；出棧也稱彈棧。

二、C++棧的方法

push()——向棧內壓入一個成員；

pop()——從棧頂彈出一個成員；

empty()——如果棧為空返回true，否則返回false；

top()——返回棧頂，但不刪除成員；

size()——返回棧內元素的大小；

#include<iostream> #include<stack> using namespace std;int main() { stack <int>stk;//入棧for(int i = 0; i < 50; i++){stk.push(i);}cout<<"棧的大小："<<stk.size()<<endl;while(!stk.empty()){cout<<stk.top()<<endl;stk.pop();}cout<<"棧的大小："<<stk.size()<<endl;return 0; }

三、造輪子

?？梢杂?strong>數組來實現，也可以用鏈表來實現

1、基于數組的實現

用到c++中的模板類(template)

#include <iostream> #include <stdlib.h> using namespace std;#define MAXSIZE 0xffff// 類模板聲明的寫法 // template <class T> class 類名{}; template<class type> class my_stack {int top;type* my_s;int maxsize;public:// 構造函數,創建默認大小的棧my_stack():top(-1),maxsize(MAXSIZE){my_s = new type[maxsize];if(my_s==NULL){// 輸出到標準錯誤的ostream對象，常用于程序錯誤信息；// 默認情況下被關聯到標準輸出流，但它不被緩沖，// 也就說錯誤消息可以直接發送到顯示器，而無需等到緩沖區或者新的換行符時，才被顯示cerr<<"動態存儲分配失敗！"<<endl;exit(1);}}// 構造函數，創建指定大小的棧my_stack(int size):top(-1),maxsize(size){my_s = new type[size];if(my_s == NULL){cerr<<"動態存儲分配失敗！"<<endl;exit(1);}}// 析構函數~my_stack(){delete[] my_s;}// 判斷棧是否為空bool Empty();// 壓棧void Push(type tp);// 返回棧頂元素type Top();// 出棧void Pop();// 棧的大小int Size(); };template<class type> bool my_stack<type>::Empty() {if(top == -1)return true;elsereturn false; }template<class type> void my_stack<type>::Push(type tp) {if(top+1 < maxsize){my_s[++top]=tp;}else {cout<<"滿棧"<<endl;exit(1);} }template<class type> type my_stack<type>::Top() {if(top != -1)return my_s[top];else{cout<<"空棧"<<endl;exit(1);} }template<class type> void my_stack<type>::Pop() {if(top >= 0){top--;}else{cout<<"空棧"<<endl;exit(1);} }template<class type> int my_stack<type>::Size() {return top+1; }// 對比測試程序 int main(int argc, char *argv[]) {my_stack<int> stk;for(int i=0; i<50; i++){stk.Push(i);}cout<<"棧的大小:"<<sizeof(stk)<<endl;w/hile(!stk.Empty()){cout<<stk.Top()<<endl;stk.Pop();}cout<<"棧的大小:"<<sizeof(stk)<<endl;return 0; }

2、基于鏈表的實現

用到c++中的模板類(template)

#include <iostream> using namespace std;template<class T> class LinkedListStack { public:LinkedListStack();~LinkedListStack();// 入棧void Push(const T & data);// 只返回棧頂元素，但不刪除棧頂元素T Top();// 出棧T Pop();// 返回棧的大小int size() const;private:// 存放棧的大小，因為單鏈表所以這里不規定棧的最大可承載量int count;struct LinkedNode{T data;LinkedNode * next;};LinkedNode * head; //單鏈表的頭指針，不帶頭結點 };// 構造函數 template<class T> LinkedListStack<T>::LinkedListStack() {this->count = 0;this->head = new LinkedNode;this->head->next = NULL; }// 析構函數，清空棧 template<class T> LinkedListStack<T>::~LinkedListStack() {LinkedNode *ptr, *temp;ptr = head;while (ptr->next != NULL) {temp = ptr->next;ptr->next = temp->next;delete temp;}delete head;//刪除頭結點this->head = NULL;this->count = 0; }// 入棧 template<class T> void LinkedListStack<T>::Push(const T &data) {LinkedNode * insertPtr = new LinkedNode;insertPtr->data = data;insertPtr->next = this->head->next;head->next = insertPtr;this->count++;cout<<"Push data:"<<this->head->next->data<<endl; } // 返回棧頂元素，即出棧，但不刪除棧頂元素 template<class T> T LinkedListStack<T>::Top() {if(this->count == 0 || this->head->next == NULL){cout<<"Stack is empty, Top fail"<<endl;return NULL;}else {LinkedNode * temp = this->head->next;T data = temp->data;return data;} } // 出棧 template<class T> T LinkedListStack<T>::Pop() {if(this->count == 0 || this->head->next == NULL){cout<<"stack is empty, Pop is fail"<<endl;return NULL;}else {LinkedNode * temp = this->head->next;this->head->next = temp->next;T data = temp->data;delete temp;this->count--;return data;} } // 返回棧的大小 template<class T> int LinkedListStack<T>::size() const {return this->count; }int main(int argc, char *argv[]) {cout << " === StackBasedOnLinkedList test begin ===" << endl;LinkedListStack <float> stack;cout << "size==="<<stack.size()<<endl;stack.Push(10.1);stack.Push(20.2);stack.Push(30.);stack.Push(40.4);stack.Push(50.5);stack.Push(60.6);cout << "size==="<<stack.size()<<endl;cout << "stack Top " << stack.Top() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "size==="<<stack.size()<<endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "size==="<<stack.size()<<endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Top " << stack.Top() << endl;stack.Push(110.1);stack.Push(120.2);stack.Push(130.3);stack.Push(140.4);stack.Push(150.5);stack.Push(160.6);cout << "size==="<<stack.size()<<endl;cout << "stack Top " << stack.Top() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Top " << stack.Top() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "stack Pop " << stack.Pop() << endl;cout << "size==="<<stack.size()<<endl;cout << "stack Top " << stack.Top() << endl;cout << "stack Pop " << stack.Pop() << endl;system("pause");return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的四、栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。