栈和队列是比较简单且常见的数据结构，你可以使用C++ STL中的stack和queue容器来实现栈和队列，当然，如果你比较有追求，也可以手搓栈和队列(虽然这个搓起来不是特别麻烦)，本文重点讲解如何实现双链表实现栈和队列。
栈和队列介绍
一句话带过吧
栈：先进后出，可乐瓶见过吧，你把东西放进去以后，必须把上面的拿完你才可以拿到你想要的
队列：先进先出，就是食堂排队，先排进去的先出来
栈的代码实现
C++STL容器
#include<iostream> #include<stdio.h> #include<stack> using namespace std; // struct Node{ // Node* pre; // Node* next; // int data; // }; int main(){ stack <int> t; // 创建栈 t.push(1); //压栈 t.pop(); //出栈 for(int i = 0 ; i < 10 ; i++){ t.push(i); //循环入栈 } int temp = t.top(); //取栈顶元素 cout << temp << endl; }对这个操作不熟悉的也可以去这个网站看一下,一看就懂了
C++ 容器类 | 菜鸟教程https://www.runoob.com/cplusplus/cpp-libs-stack.html
双链表实现栈
双链表因为可以从尾向头查找，所以在实现栈和队列上会有较低的复杂度
#include<iostream> #include<stdio.h> using namespace std; struct Node{ Node* pre; Node* next; int data; }; Node* Tail = NULL; //定义尾节点 void push(int data){//压栈操作 data为你想压入的元素 Node* top = new Node(); top -> data = data; top -> next = NULL; top -> pre = Tail; Tail -> next = top; Tail = top; } int pop(){//出栈操作，同时返回栈顶元素 int data; data = Tail -> data; Node* newtop = Tail -> pre; delete Tail; Tail = newtop; return data; } int main(){ Node* A = new Node(); A -> data = 1; A -> next = Tail; A -> pre = NULL; Tail = A; push(2); push(3); push(4); int temp = pop(); cout << temp << endl; cout << Tail -> data << endl; }队列的代码实现
C++STL容器实现
#include<iostream> #include<stdio.h> #include<queue> using namespace std; // struct Node{ // Node* pre; // Node* next; // int data; // }; int main(){ queue <int> q; for(int i = 0 ; i < 10 ; i++){ q.push(i); //循环入队 } for(int i = 0 ; i < 10 ; i++){ int tail = q.back(); //获取队尾元素 int head = q.front(); //获取队首元素 q.pop(); //出队操作 cout << head << ' ' << tail << endl; } }同样的，不熟悉的可以去看看这个网站C++ 容器类 | 菜鸟教程https://www.runoob.com/cplusplus/cpp-libs-queue.html
双链表实现队列
#include<iostream> #include<stdio.h> #include<queue> using namespace std; struct Node{ Node* pre; Node* next; int data; }; Node* Tail = NULL; //定义尾节点 Node* Head = NULL; void push(int data){ Node* back = new Node(); back -> data = data; back -> next = NULL; back -> pre = Tail; Tail -> next = back; Tail = Tail -> next; } void pop(){ Node* newfront = Head -> next; delete Head; Head = newfront; } int main(){ Node* A = new Node(); A -> data = 10086; A -> next = NULL; A -> pre = NULL; Head = A; Tail = A; for(int i = 0 ; i < 10 ; i++){ push(i); cout << Head -> data << ' ' << Tail -> data << endl; } printf("----------------------------\n"); for(int i = 0 ; i < 10 ; i++){ cout << Head -> data << ' ' << Tail -> data << endl; pop(); } }这样就实现了手搓 stack 和 queue
