- 线性表包含：顺序表，链表，栈，队列等
- 顺序表（就是类似数组那样来存储数据）：静态顺序表（指定存储多少）和动态顺序表（就是不指定存储个数）
一.顺序表
下面主要对动态顺序表接口的实现：
#ifndef _TEST_H__
#define _TEST_H__
#include <stdlib.h>
#include <stdio.h>
typedef int SLDateType;
typedef struct SeQlistF{
SLDateType *arry;
int size;
int capicity;
}SeQlist;
//初始化顺序表
void SeQlistInit(SeQlist *ps1);
//对顺序表进行扩容
void CheckCapacity(SeQlist *ps1);
//顺序表尾插
void SeQlistPushBack(SeQlist *ps1,SLDateType x);
//顺序表尾删
void SeQlistPopBack(SeQlist *ps1);
//顺序表头插
void SeQlistPushFront(SeQlist *ps1,SLDateType x);
//顺序表头删
void SeQlistPopFront(SeQlist *ps1);
//顺序表查找
void SeQlistFind(SeQlist *ps1,SLDateType x);
//顺序表在pos位置插入x
void SeQlistInsert(SeQlist *ps1,size_t pos,SLDateType x);
//顺序表在pos位置删除x
void SeQlistErase(SeQlist *ps1,size_t pos);
//顺序表销毁
void SeQlistDestory(SeQlist *ps1);
//顺序表打印
void SeQlistPrint(SeQlist *ps1);
#endif- 初始化顺序表（把数组置为空数组，数组大小和容量都置为0）
//顺序表初始化
void SeQlistInit(SeQlist *ps1){
ps1->arry =NULL;
ps1->size = ps1->capicity = 0;
}2.销毁顺序表（释放数组空间，然后也是数组数组置为空数组，数组大小和容量都置为0）
//顺序表销毁
void SeQlistDestory(SeQlist *ps1){
free(ps1->arry);
ps1->arry =NULL;
ps1->size = ps1->capicity = 0;
}3. 顺序表打印（定义i，然后遍历一遍数组）
void SeQlistPrint(SeQlist *ps1){
for(int i=0 ;i < ps1->size;++i){
printf("%d",ps1->arry[i]);
printf("\n");
}
}4.对顺序表的扩容（当数组内容和容量一样大时需要扩容；当容量为0时就是没有创建数组，给他4个字节容量；当容量不是0时，扩容两倍容量赋值给newCapicity；重新给数组创建一个空间赋给tmp；然后重新把tmp，newCapicity给数组和容量，完成扩容）
//对顺序表进行扩容
void CheckCapacity(SeQlist *ps1){
if(ps1->size == ps1->capicity){
int newCapicity = ps1->capicity == 0? 4 : ps1->capicity*2;
SLDateType* tmp =(SLDateType *)realloc(ps1->arry,newCapicity * sizeof(SLDateType));
if(tmp==NULL){
perror("realloc error\n");
return ;
}
ps1->arry = tmp;
ps1->capicity = newCapicity;
}
}5.元素删除步骤
(1).顺序表尾删（直接方法就是：数组大小减1）
//顺序表尾删
void SeQlistPopBack(SeQlist *ps1){
ps1->size--;
}(2).顺序表头删（后一个数往前挪一个，然后减小元素数量，如果不减小，后面会随机给原来位置分配一个数）
//顺序表头删
void SeQlistPopFront(SeQlist *ps1){
if (ps1->size > 0) { // 检查顺序表是否为空
int begin = 0;
while (begin < ps1->size - 1) {
ps1->arry[begin] = ps1->arry[begin + 1];
++begin;
}
ps1->size--; // 减少元素数量
}
}6.元素插入步骤：
(1)顺序表尾插（防止容量不够，先扩容一下；然后对数组最后一个数赋值x，然后最后一位往后挪一位）
//顺序表尾插
void SeQlistPushBack(SeQlist *ps1,SLDateType x){
CheckCapacity(ps1);
ps1->arry[ps1->size] = x;
ps1->size++;
}(2).顺序表头插（同样怕没有空间，先扩容一下，先用end指向最后一位数索引，然后元素后移，最后在头部添加新数和更新元素数量）
//顺序表头插
void SeQlistPushFront(SeQlist *ps1,SLDateType x){
CheckCapacity(ps1);
int end = ps1->size-1;
while(end >= 0){
ps1->arry[end+1] = ps1->arry[end];
end--;}
ps1->arry[0]=x;
ps1->size++;
}7.元素查找步骤：
8.元素修改：
顺序表函数全部的实现
#include <iostream>
using namespace std;
#define SLDataType int
struct Sequlist{
SLDataType* array;
int size;
int capacity;
};
//********************顺序表初始化***********/
void InitSequlist(Sequlist* sl, int capacity) {
sl->array = new SLDataType[capacity];
sl->size = 0;
sl->capacity = capacity;
}
//********************顺序表销毁************/
void DestorySequlist(Sequlist* sl) {
delete[] sl->array;
}
//**********************获取顺序表长度******//
int GetSequlistLength(Sequlist* sl) {
return sl->size;
}
//**********************判断顺序表是否为空***//
bool SequlistEmpty(Sequlist* sl) {
return sl->size == 0;
}
//***************顺序表的插入********** */
void insertSequlist(Sequlist* sl, int pos, SLDataType x) {
//判断pos是否合法
if(pos < 0 || pos > sl->size){
printf("插入位置不合法\n");
}
//判断是否需要增容
if(sl->size == sl->capacity){
int newCapacity = sl->capacity * 2;
SLDataType* newArry = new SLDataType[newCapacity];
for(int i = 0;i < sl->size;i++){
newArry[i] = sl->array[i];
}
delete[] sl->array;
sl->array = newArry;
sl->capacity = newCapacity;
}
//往后挪数据
for (int i = sl->size; i > pos; i--)
{
sl->array[i] = sl->array[i-1];
}
//插入数据
sl->array[pos] = x;
//更新大小
sl->size++;
}
//***************************顺序表的删除元素 */
void deleteSequlist(Sequlist* sl, int pos){
//判断pos是否合法
if(pos < 0 || pos > sl->size){
printf("插入位置不合法\n");
}
//删除元素
for(int i = pos;i < sl->size;i++){
sl->array[i] = sl->array[i+1];
}
//更新大小
sl->size--;
}
//**************************顺序表查找元素下标索引 */
int findSequlistIndex(Sequlist* sl, int x){
for (int i = 0; i < sl->size; i++)
{
if (sl->array[i] == x)
{
return i;
}
}
return -1;
}
//************************顺序表查找元素 */
int getSequlist(Sequlist* sl, int pos){
//判断pos是否合法
if(pos < 0 || pos > sl->size){
printf("插入位置不合法\n");
}
//得到元素
return sl->array[pos];
}
//***********************更新数据********//
void updateSequlist(Sequlist* sl, int pos, SLDataType x){
//判断pos是否合法
if(pos < 0 || pos > sl->size){
printf("插入位置不合法\n");
}
//更新元素
sl->array[pos] = x;
}
int main()
{
Sequlist sl;
//初始化顺序表
InitSequlist(&sl,10);
//顺序表的长度
cout<<GetSequlistLength(&sl)<<endl;
//向顺序表内增加元素
for (int i = 0; i < 10; i++)
{
insertSequlist(&sl,i,i * 10);
}
//判断顺序表是否为空
cout<<"Is empty :"<<SequlistEmpty(&sl)<<endl;
//打印顺序表
for (int i = 0; i < sl.size; i++)
{
cout<<getSequlist(&sl,i)<<" ";
}
//查找值20的下标
cout << "值20的下标为:%d"<<findSequlistIndex(&sl , 20)<<endl;
//删除元素并打印出删除后的元素
deleteSequlist(&sl,5);
for (int i = 0; i < sl.size; i++)
{
cout<<getSequlist(&sl,i)<<" ";
}
cout<<endl;
//更新元素并打印出更新后的元素
updateSequlist(&sl,2,1314);
for (int i = 0; i < sl.size; i++)
{
cout<<getSequlist(&sl,i)<<" ";
}
//销毁顺序表
DestorySequlist(&sl);
return 0;
}二.链表
1.元素删除步骤：
2.元素查找步骤：
3.元素索引步骤：
4.元素插入步骤：
5.元素修改步骤：
单向链表函数全部的实现：
#include <stdio.h>
#include <stdlib.h>
//创建一个链表
struct Test
{
int data;
struct Test *next;
};
//遍历链表函数的思想：从头开始遍历，直到最后一个节点
void printList(struct Test *head)
{
struct Test *p = head;
while(p != NULL)
{
printf("%d ",p->data);
p = p->next;//指针后移
}
printf("\n");
}
//计算链表的长度函数的思想：从头开始遍历，每遍历一个节点，长度加1
int getLength(struct Test *head)
{
struct Test *p = head;
int len = 0;
while(p != NULL)
{
len++;
p = p->next;
}
return len;
}
//链表查找函数的思想：从头开始遍历，找到就返回，找不到就返回NULL
struct Test *find(struct Test *head,int data)
{
struct Test *p = head;
while(p != NULL)
{
if(p->data == data)
{
return p;
}
p = p->next;
}
return NULL;
}
//链表从任意位置后面插入的思想：将new的next指向原来p的next，也就是指向原来p的下一个节点，然后将p的next指向new
int insert(struct Test *head,int data,struct Test *new)
{
struct Test *p = head;
while(p != NULL)
{
if(p->data == data)
{
new->next = p->next;//将new的next指向原来p的next，也就是指向原来p的下一个节点
p->next = new; //将p的next指向new，也就是将new插入到p的后面，然后p指向new
return 1;
}
p = p->next;
}
return 0;
}
//链表从任意位置前面插入函数的思想：将new的next指向原来p的next，也就是指向原来p的下一个节点，然后将p的next指向new
struct Test *insertBefore(struct Test *head,int data,struct Test *new)
{
struct Test *p = head;
if(p->data == data)
{
new->next = p;
return new;
}
while(p->next != NULL)
{
if(p->next->data == data)
{
new->next = p->next;//将new的next指向原来p的next，也就是指向原来p的下一个节点
p->next = new;//将p的next指向new，也就是将new插入到p的后面，然后p指向new
return head;
}
p = p->next;
}
return head;
}
//链表任意位置删除函数的思想：将p的next指向原来p的next的next，也就是跳过data这个值的节点，链接下一个节点
int delete(struct Test *head,int data)
{
struct Test *p = head;
while(p->next != NULL)
{
if(p->next->data == data)
{
p->next = p->next->next;
return 1;
}
p = p->next;
}
return 0;
}
//动态链表头插入函数的思想：先创建一个链表空间，然后输入添加的数，如果输入-1，说明结束添加；然后链表是空的，就将添加的设为头，否则就将new的next指向头，然后将new设置为头
struct Test *insertHead(struct Test *head)
{
struct Test *new;
while (1)
{
new = (struct Test *)malloc(sizeof(struct Test));
printf("请输入数据：\n");
scanf("%d",&new->data);
if(new->data == -1)
{
break;
}
if (head == NULL)
{
head = new;
}else{
new->next = head;
head = new;
}
}
return head;
}
//动态链表尾插入函数的思想：遍历一遍链表，如果空，就将new设置为链表头；如果不是空，就一直往下遍历，直到为空，说明到尾部了； 然后尾部p的next指向new
struct Test *insertTail(struct Test *head,struct Test *new)
{
struct Test *p = head;
if( p == NULL)
{
head = new;
return head;
}
while(p->next != NULL)
{
p = p->next;
}
p->next = new;
return head;
}
int main()
{
struct Test *head = NULL;
//初始化链表
struct Test t1 ={1,NULL};
struct Test t2 ={2,NULL};
struct Test t3 ={3,NULL};
struct Test t4 ={4,NULL};
struct Test t5 ={5,NULL};
struct Test t6 ={6,NULL};
//关联链表
t1.next = &t2;
t2.next = &t3;
t3.next = &t4;
t4.next = &t5;
t5.next = &t6;
head = &t1;
//遍历链表
printList(&t1);
//计算链表长度
printf("链表的长度为：%d\n",getLength(&t1));
//查找链表中的元素
struct Test *p = find(&t1,3);
if(p != NULL)
{
printf("找到了，值为：%d\n",p->data);
}else
{
printf("没找到\n");
}
struct Test *b = find(&t1,8);
if(b != NULL)
{
printf("找到了，值为：%d\n",b->data);
}else
{
printf("没找到\n");
}
//从任意位置后面插入元素
struct Test t7 ={7,NULL};
insert(&t1,2,&t7);
printList(&t1);
//从任意位置前面插入元素
struct Test t8 ={8,NULL};
insertBefore(&t1,2,&t8);
printList(&t1);
//从任意位置删除元素
delete(&t1,3);
printList(&t1);
//动态链表尾插
struct Test t9 ={9,NULL};
head = insertTail(head,&t9);
printList(head);
//动态链头插
head = insertHead(head);
printList(head);
return 0;
}三.栈
1.概念：
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。可以先进去几个数，然后出来，再进去数，并不是全部进去，再全部出来。数组实现最好。
2.作用
用于有后进先出数据需求的场景。
3.实现
#include<stdio.h>
#include<stdlib.h>
//***********************各个接口的实现*************************//
//创建栈的接口
typedef struct Stack
{
int *a;//栈的数组
int top;//栈顶指针
int capacity;//栈的容量
}ST;
//栈的初始化
void InitStack(ST *S)
{
S->a = (int *)malloc(sizeof(int)*4);//开辟4个int大小的空间
S->top = 0;//栈顶指针置为0
S->capacity = 4;//栈的容量置为4
}
//栈的销毁
void DestroyStack(ST *S)
{
free(S->a);
S->a = NULL;
S->top = S->capacity = 0;
}
//栈的入栈
void Push(ST *S,int x)
{
//判断栈是否满
if(S->top == S->capacity)
{
S->a = (int *)realloc(S->a,sizeof(int)*S->capacity*2);//扩容
S->capacity *= 2;//更新栈的容量
}
S->a[S->top] = x;//入栈
S->top++;
}
//栈的出栈
void Pop(ST *S)
{
//判断栈是否为空
if(S->top == 0)
{
printf("栈为空\n");
return;
}
S->top--;
}
//获取栈顶元素
int Top(ST *S)
{
//判断栈是否为空
if(S->top == 0)
{
printf("栈为空\n");
return -1;
}
return S->a[S->top-1];//S->top指向栈顶元素的下一个位置,所以返回S->top-1是栈顶元素
}
//判断栈是否为空
int IsEmpty(ST *S)
{
return S->top == 0;
}
//判断栈是否满
int IsFull(ST *S)
{
return S->top == S->capacity;
}
//获取栈里有还有多少元素
int StackSize(ST *S)
{
return S->top;
}
int main()
{
ST S;
//初始化栈
InitStack(&S);
//入栈
Push(&S,1);
Push(&S,2);
Push(&S,3);
Push(&S,4);
Push(&S,5);
Push(&S,6);
Push(&S,7);
//打印所有元素
while(!IsEmpty(&S))
{
printf("%d\n",Top(&S));
Pop(&S);
}
Push(&S,8);
Push(&S,9);
Push(&S,10);
//获取栈顶元素
printf("%d\n",Top(&S));
//出栈
Pop(&S);
//获取栈的容量
StackSize(&S);
//打印栈顶元素
printf("%d\n",Top(&S));
//出栈
Pop(&S);
//获取栈的容量
StackSize(&S);
//销毁栈
DestroyStack(&S);
return 0;
}三.队列
1.概念
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 。入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。最好用链表实现。
2.作用
用于先进先出场景：列如：排队，银行取票。
3.实现
#include<stdio.h>
#include<stdlib.h>
//*********************创建队列***************************//
//以链表的形式创建队列，所有先创建链表单个节点
typedef struct Node
{
int data;
struct Node *next;
}Node;
//定义队列实列
typedef struct Queue
{
Node* head;//头指针
Node* rear;//尾指针
int size;
}Queue;
//初始化队列
Queue *initQueue(Queue *q)
{
q->head = NULL;
q->rear = NULL;
q->size = 0;
}
//销毁队列的思想：先检查队列是否为空，若为空则释放队列；若不为空则 创建一个指针p指向头节点，然后循环遍历链表，再创建一个链表节点temp保存当前节点，然后将p指向下一个节点，使链表链接起来，最后释放当前节点，直到p为空；最后面队列全部置为空
void destroyQueue(Queue *q)
{
if (q->size == 0)
{
free(q);
}
Node *p = q->head;//指向头节点
while(p != NULL)
{
Node *temp = p;//保存当前节点
p = p->next;//指向下一个节点
free(temp);//释放当前节点
}
q->head = q->rear = NULL;
q->size = 0;
}
//插入队列的思想：先判断队列是否为空，为空则头尾指针指向新节点，否则尾指针指向新节点，新节点就是尾节点，然后size++
void insertQueue(Queue *q, int data)
{
Node *node = (Node*)malloc(sizeof(Node));
if (node == NULL)
{
printf("内存分配失败\n");
exit(1);
}
else
{
node->data = data;
node->next = NULL;
}
if(q->size == 0)
{
q->head = node;
q->rear = node;
}
else
{
q->rear->next = node;
q->rear = node;
}
q->size++;
}
//出队列的思想：先判断队列是否为空，为空则返回-1；否则头指针指向下一个节点，并释放当前节点，size--
void deleteQueue(Queue *q)
{
if (q->size == 0)
{
printf("Queue is empty\n");
return;
}
else
{
Node *p = q->head;//保存头节点
q->head = q->head->next;//指向下一个节点
free(p);//释放头节点
}
q->size--;//队列长度减一
}
//获取头数据
int getHead(Queue *q)
{
return q->head->data;
}
//获取尾数据
int getRear(Queue *q)
{
return q->rear->data;
}
//判断队列是否为空
int isEmpty(Queue *q)
{
return q->size == 0;
}
int main()
{
//初始化队列
Queue q;
initQueue(&q);
//插入数据
insertQueue(&q, 1);
insertQueue(&q, 2);
insertQueue(&q, 3);
//获取头数据
printf("Head data: %d\n", getHead(&q));
//获取尾数据
printf("Rear data: %d\n", getRear(&q));
//删除一个队列
deleteQueue(&q);
//获取头数据
printf("Head data: %d\n", getHead(&q));
//销毁队列
destroyQueue(&q);
return 0;
}用C++顺序表实现队列
#include <iostream>
using namespace std;
template<typename T>
class Queue
{
private:
T *data;
int front;
int rear;
int capacity;
void resize();
public:
Queue():data(new T[10]),front(0),rear(0),capacity(10){};
~Queue();
void enqueue(T element);
T dequeue();
T getfront() const;
int getsize() const;
};
//扩容
template<typename T>
void Queue<T>::resize(){
T *newdata = new T[capacity*2];
for (int i = 0; i < rear; i++)
{
newdata[i] = data[i];
}
delete[] data;
data = newdata;
capacity *= 2;
}
//析构，释放内存
template<typename T>
Queue<T>::~Queue(){
delete[] data;
}
//入队
template<typename T>
void Queue<T>::enqueue(T element){
if (rear == capacity)
{
resize();
}
data[rear++] = element;
}
//出队
template<typename T>
T Queue<T>::dequeue(){
if (front == rear)
{
cout<<"错误使用"<<endl;
}
T element = data[front++];
return element;
}
//获取首元素
template<typename T>
T Queue<T>::getfront() const{
if (front == rear)
{
cout<<"错误使用"<<endl;
}
return data[front];
}
//获取队列大小
template<typename T>
int Queue<T>::getsize() const{
return rear - front;
}
int main(){
Queue<int> q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
cout<<q.getfront()<<" "<<q.getsize()<<endl;
q.dequeue();
cout<<q.getfront()<<" "<<q.getsize()<<endl;
return 0;
}C++链表形式实现队列
#include <iostream>
using namespace std;
template<typename T>
class Queue{
private:
struct Node
{
T data;
Node *next;
Node(T d):data(d),next(NULL){}
};
Node *front;
Node *rear;
int size;
public:
Queue():front(NULL),rear(NULL),size(0){};
~Queue();
void enqueue(T element);
T dequeue();
T getfront() const;
int getsize() const;
};
//析构，释放内存
template<typename T>
Queue<T>::~Queue(){
while (front)
{
Node *temp = front;
front = front->next;
delete temp;
}
}
//入队
template<typename T>
void Queue<T>::enqueue(T element){
if (rear == NULL)
{
rear = new Node(element);
front = rear;
}else{
rear->next = new Node(element);
rear = rear->next;
}
size++;
}
//出队
template<typename T>
T Queue<T>::dequeue(){
if (front == rear)
{
cout<<"出队错误"<<endl;
}
T element = front->data;
Node *temp = front;
front = front->next;
delete temp;
size--;
if(size == 0) rear == NULL;
return element;
}
//获取首元素
template<typename T>
T Queue<T>::getfront() const{
return front->data;
}
//获取队列大小
template<typename T>
int Queue<T>::getsize() const{
return size;
}
int main(){
Queue<int> q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
cout<<q.getfront()<<" "<<q.getsize()<<endl;
q.dequeue();
cout<<q.getfront()<<" "<<q.getsize()<<endl;
return 0;
}四.用两个栈实现队列
用两个栈S1(入队栈)，S2(出对栈)，如果想入队：就把元素全部插入到S1里面；如果想出队：先判断S2是不是空的，然后就把S1栈顶元素逐渐放到S2里面，然后S2再往外出元素。从而实现先进先出原则
#include <iostream>
using namespace std;
template<typename T>
class Stack {
private:
T* data;
int size;
int capacity;
void resize();
public:
Stack() : data(new T[10]), size(0), capacity(10) {}
~Stack();
void push(T element);
T pop();
T top() const;
int getSize() const;
bool empty() const;
};
//扩容
template<typename T>
void Stack<T>::resize() {
int newCapacity = capacity * 2;
T* newData = new T[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
delete[] data;
data = newData;
capacity = newCapacity;
}
//析构函数，释放内存
template<typename T>
Stack<T>::~Stack() {
delete[] data;
}
//入栈
template<typename T>
void Stack<T>::push(T element) {
if (size == capacity) {
resize();
}
data[size++] = element;
}
//出栈
template<typename T>
T Stack<T>::pop() {
if (size == 0) {
throw std::underflow_error("Stack is empty");
}
return data[--size];
}
//获得栈顶元素
template<typename T>
T Stack<T>::top() const {
if (size == 0) {
throw std::underflow_error("Stack is empty");
}
return data[size - 1];
}
//获得栈里有多少元素
template<typename T>
int Stack<T>::getSize() const {
return size;
}
//判断是否为空
template<typename T>
bool Stack<T>::empty() const {
return size == 0;
}
class MyQueue {
private:
Stack<int> s1; // 入队栈
Stack<int> s2; // 出队栈
public:
MyQueue() {}
//入队
void push(int x) {
s1.push(x);
}
//出队
int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
int result = s2.top();
s2.pop();
return result;
}
//获得队顶元素
int peek() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
//判断是否为空
bool empty() {
return s1.empty() && s2.empty();
}
};
int main() {
return 0;
}五.两个队列实现栈
两个队列Q1,Q2实现栈 入栈：就是元素直接入队到队列Q1；出栈：Q1出到Q2里面，Q1最后出来的就是出栈元素，然后再把Q2元素全部入队到Q1里面；从而实现栈，后进先出原则
#include <iostream>
using namespace std;
template<typename T>
class Queue {
private:
T* data;
int front;
int rear;
int capacity;
void resize();
public:
Queue() : data(new T[10]), front(0), rear(0), capacity(10) {}
~Queue();
void enqueue(T element);
T dequeue();
T getFront() const;
int getSize() const;
bool empty() const;
};
//队列扩容
template<typename T>
void Queue<T>::resize() {
T* newData = new T[capacity * 2];
for (int i = 0; i < rear; i++) {
newData[i] = data[i];
}
delete[] data;
data = newData;
capacity *= 2;
}
//析构函数，释放内存
template<typename T>
Queue<T>::~Queue() {
delete[] data;
}
//入队
template<typename T>
void Queue<T>::enqueue(T element) {
if (rear == capacity) {
resize();
}
data[rear++] = element;
}
//出队
template<typename T>
T Queue<T>::dequeue() {
if (front == rear) {
throw std::underflow_error("Queue is empty");
}
T element = data[front++];
return element;
}
//获得队首元素
template<typename T>
T Queue<T>::getFront() const {
if (front == rear) {
throw std::underflow_error("Queue is empty");
}
return data[front];
}
//获得队列多少元素
template<typename T>
int Queue<T>::getSize() const {
return rear - front;
}
//判断是否为空
template<typename T>
bool Queue<T>::empty() const {
return getSize() == 0;
}
class MyStack {
private:
Queue<int> q1;
Queue<int> q2;
public:
MyStack() {}
//入栈
void push(int x) {
q1.enqueue(x);
}
//出栈
int pop() {
while (q1.getSize() > 1) {
q2.enqueue(q1.dequeue());
}
int result = q1.dequeue();
while (!q2.empty()) {
q1.enqueue(q2.dequeue());
}
return result;
}
//获得栈顶元素
int top() {
while (q1.getSize() > 1) {
q2.enqueue(q1.dequeue());
}
int result = q1.dequeue();
q2.enqueue(result);
while (!q2.empty()) {
q1.enqueue(q2.dequeue());
}
return result;
}
//判断栈是否为空
bool empty() {
return q1.empty();
}
};
int main() {
return 0;
}