数据结构实现-栈和队列

news/2024/7/27 16:10:14/文章来源:https://blog.csdn.net/qq_61249949/article/details/136440266

顺序栈

#include <iostream>
using namespace std;
#define MaxSize 50//顺序栈
template<typename ElemType>
struct SqStack{ElemType data[MaxSize];int top;
};//初始化
template<typename ElemType>
void InitStack(SqStack<ElemType>&s){s.top=-1;
}//判断栈空
template<typename ElemType>
bool StackEmpty(SqStack<ElemType>&s){return s.top==-1;
}//进栈
template<typename ElemType>
bool Push(SqStack<ElemType>&s,ElemType x){if (s.top==MaxSize-1){return false;}s.data[++s.top]=x;return true;
}//出栈
template<typename ElemType>
bool Pop(SqStack<ElemType>&s,ElemType&x){if (s.top==-1){return false;}x=s.data[s.top--];return true;
}//读栈顶元素
template<typename ElemType>
bool GetTop(SqStack<ElemType>&s,ElemType&x){if (s.top==-1)return false;x=s.data[s.top];return true;
}

链栈

#include <iostream>
using namespace std;
template<typename ElemType>
struct LinkNode{ElemType data;LinkNode<ElemType>*next;
};
template<typename ElemType>
struct LinkStack{LinkNode<ElemType>*front,*rear;
};//初始化
template<typename ElemType>
void InitStack(LinkStack<ElemType> &S){S.front = S.rear = new LinkNode<ElemType>;
}//判栈空
template<typename ElemType>
bool StackEmpty(LinkStack<ElemType>S){return S.front==S.rear;
}//进栈
template<typename ElemType>
void Push(LinkStack<ElemType>&s,ElemType x){LinkNode<ElemType>*newNode = new LinkNode<ElemType>;newNode->data=x;newNode->next=s.rear;s.rear=newNode;
}//出栈
template<typename ElemType>
bool Pop(LinkStack<ElemType>&s,ElemType&x){if (StackEmpty(s)){return false;}LinkNode<ElemType>*temp = s.rear;x = temp->data;s.rear = s.rear->next;delete temp;return true;
}//读栈顶元素
template<typename ElemType>
bool GetTop(LinkStack<ElemType>&s,ElemType&x){if (StackEmpty(s))return false;x = s.rear->data;return true;
}

顺序队列

#include <iostream>
using namespace std;
#define MaxSize 10
template<typename ElemType>
struct SqQueue{ElemType data[MaxSize];int front,rear;
};//初始化
template<typename ElemType>
void InitQueue(SqQueue<ElemType>&Q){Q.front=Q.rear=0;//默认队列的头指针指向对头,尾指针指向尾部元素的下一个。
}//判队空
template<typename ElemType>
bool isEmpty(SqQueue<ElemType>&Q){return Q.front==Q.rear;
}//入队
template<typename ElemType>
bool EnQueue(SqQueue<ElemType>&Q,ElemType x){if ((Q.rear+1)%MaxSize==Q.front){return false;}Q.data[Q.rear] = x;Q.rear = (Q.rear+1)%MaxSize;return true;
}//出队
template<typename ElemType>
bool DeQueue(SqQueue<ElemType>&Q,ElemType&x){if (Q.rear==Q.front)return false;x=Q.data[Q.front];Q.front = (Q.front+1)%MaxSize;return true;
}int main(){SqQueue<int>sq;InitQueue(sq);for (int i = 0; i < 8; ++i) {EnQueue(sq,i);}int x;for (int i = 0; i < 3; ++i) {DeQueue(sq,x);}for (int i = 8; i < 10; ++i) {EnQueue(sq,i);}cout<<endl;
}

链队列

#include <iostream>
using namespace std;
template<typename ElemType>
struct LinkNode{ElemType data;LinkNode<ElemType>* next;
};
template<typename ElemType>
struct LinkQueue{LinkNode<ElemType>*rear,*front;
};//初始化
template<typename ElemType>
void InitQueue(LinkQueue<ElemType>&Q){Q.front = Q.rear = new LinkNode<ElemType>;Q.front->next = nullptr;
}template<typename ElemType>
bool IsEmpty(LinkQueue<ElemType>&Q){return Q.front==Q.rear;
}template<typename ElemType>
void EnQueue(LinkQueue<ElemType>&Q,ElemType x){LinkNode<ElemType>*s = new LinkNode<ElemType>;s->data = x;s->next= nullptr;Q.rear->next=s;Q.rear = s;
}template<typename ElemType>
bool DeQueue(LinkQueue<ElemType>&Q,ElemType&x){if (Q.front==Q.rear)return false;LinkNode<ElemType>*p=Q.front->next;x=p->data;Q.front->next=p->next;if (Q.rear==p)Q.rear=Q.front;delete p;return true;
}