C++ 实现栈和队列：链式存储与顺序存储

#include using namespace std; #define MAXSIZE 100 //定义顺序栈和顺序队列的最大长度

//链式栈结构体 typedef struct node{ int data; struct node* next; }Node, *Stack;

//链式栈初始化 void initStack(Stack &s){ s = NULL; }

//链式栈入栈 void push(Stack &s, int x){ Node* p = new Node; p->data = x; p->next = s; s = p; }

//链式栈出栈 void pop(Stack &s){ if(s == NULL) cout<'栈已空！'<endl; else{ Node* p = s; s = s->next; cout<'出栈元素为：'data<<endl; delete p; } }

//顺序栈结构体 typedef struct{ int data[MAXSIZE]; int top; }SqStack;

//顺序栈初始化 void initSqStack(SqStack &s){ s.top = -1; }

//顺序栈入栈 void push(SqStack &s, int x){ if(s.top == MAXSIZE-1) cout<'栈已满！'<endl; else{ s.top++; s.data[s.top] = x; } }

//顺序栈出栈 void pop(SqStack &s){ if(s.top == -1) cout<'栈已空！'<endl; else{ cout<'出栈元素为：'<s.data[s.top]<<endl; s.top--; } }

//链式队列结构体 typedef struct qnode{ int data; struct qnode* next; }QNode, *Queue;

//链式队列初始化 void initQueue(Queue &q){ q = NULL; }

//链式队列入队 void enqueue(Queue &q, int x){ Queue p = new QNode; p->data = x; p->next = NULL; if(q == NULL) q = p; else{ Queue rear = q; while(rear->next != NULL) rear = rear->next; rear->next = p; } }

//链式队列出队 void dequeue(Queue &q){ if(q == NULL) cout<'队列已空！'<endl; else{ Queue p = q; q = q->next; cout<'出队元素为：'data<<endl; delete p; } }

//顺序队列结构体 typedef struct{ int data[MAXSIZE]; int front, rear; }SqQueue;

//顺序队列初始化 void initSqQueue(SqQueue &q){ q.front = q.rear = 0; }

//顺序队列入队 void enqueue(SqQueue &q, int x){ if((q.rear+1)%MAXSIZE == q.front) cout<'队列已满！'<endl; else{ q.data[q.rear] = x; q.rear = (q.rear+1)%MAXSIZE; } }

//顺序队列出队 void dequeue(SqQueue &q){ if(q.front == q.rear) cout<'队列已空！'<endl; else{ cout<'出队元素为：'<q.data[q.front]<<endl; q.front = (q.front+1)%MAXSIZE; } }

int main(){ int choice, x; Stack s; SqStack ss; Queue q; SqQueue sq; initStack(s); initSqStack(ss); initQueue(q); initSqQueue(sq); while(1){ cout<<' 1.链式栈入栈 2.链式栈出栈 3.顺序栈入栈 4.顺序栈出栈 5.链式队列入队 6.链式队列出队 7.顺序队列入队 8.顺序队列出队 9.退出'<endl; cout<<'请输入要执行的操作：'; cin>>choice; switch(choice){ case 1: cout<<'请输入入栈元素：'; cin>>x; push(s, x); break; case 2: pop(s); break; case 3: cout<<'请输入入栈元素：'; cin>>x; push(ss, x); break; case 4: pop(ss); break; case 5: cout<<'请输入入队元素：'; cin>>x; enqueue(q, x); break; case 6: dequeue(q); break; case 7: cout<<'请输入入队元素：'; cin>>x; enqueue(sq, x); break; case 8: dequeue(sq); break; case 9: exit(0); default: cout<<'输入错误，请重新输入！'<<endl; } } return 0;