基本数据结构的实现-顺序栈、循环队列、链栈

面试突然让我手写栈和队列，一下给我整懵了，整合了一下发上来。

顺序栈

#include <iostream>
using namespace std;
#define MAXSIZE 100

typedef char ElemType;//这里用int非常慢
typedef struct
{
	ElemType* base;//栈底指针
	ElemType* top;//栈顶指针
	int stacksize;//栈可用的最大容量
} SqStack;

void InitStack(SqStack& S)
{
	//构造一个空栈S
	S.base = new ElemType[MAXSIZE];
	if (!S.base)
		return ;
	S.top = S.base;
	S.stacksize = MAXSIZE;
}
int StackEmpty(SqStack& S)  //判断栈是否为空
{
	if (S.top == S.base)
		return -1;
	else
		return 0;
}

bool Push(SqStack& S, ElemType e)   //顺序栈进栈
{
	if (S.top - S.base == S.stacksize)
		return false;
	*S.top++ = e;
	return true;
}

bool Pop(SqStack& S, ElemType& e)  //顺序栈出栈
{
	if (S.top == S.base)
		return false;
	e = *--S.top;
	return true;
}

void DestroyStack(SqStack& S)  //销毁
{

	free(S.base);
}

bool GetTop(SqStack& S)  //取栈顶元素
{
	if (S.top != S.base)
		return *(S.top - 1);
}

int main()
{
	SqStack S;
	ElemType e;
	int n;
	InitStack(S);
	cout << "请输入要入栈的元素个数："; cin >> n;
	for (int i = 0; i < n;i++)
	{
		cin >> e;
		Push(S, e);
	}

	while (!StackEmpty(S))
	{
		Pop(S, e);
		cout << e;
	}
}

队列

一般是循环队列，链式队列太浪费内存了

1 循环队列的顺序存储
判断队空q.rear == q.front

入队：if(q.rear+1)%maxsize == q.front) return false;

q.data[q.rear] = x;

q.rear = (q.rear+1)%maxsize;

2循环队列的链式存储

判断队空：q.front == q.rear

判断队满：q.front == (q.rear+1)%n

 入队：LinkNode*s = (LinkNode*)malloc(sizeof(LinkNode));

s->data=x; s->next=null;

q.rear->next =s;

q.rear = s;

#include<iostream>
using namespace std;
#define maxsize 3    

typedef struct
{
	int data[maxsize];     //注意 int* data;
	int front;
	int rear;
}squeue;
void init(squeue& q)
{
	q.front = 0;
	q.rear = 0;
}
int enqueue(squeue& q, int e)
{
	if (q.front == q.rear % maxsize)//队满标志 (rear+1)%MAXQSIZE==front
		return 0;
	q.data[q.rear] = e;
	q.rear = (q.rear + 1) % maxsize;
	return 1;
}
int dequeue(squeue& q, int& e)
{
	if (q.rear == q.front)
		return 0;
	e = q.data[q.front];
	q.front = q.front + 1 % maxsize;
	return 1;
}
int length(squeue q)               //求不了长度  待解决
{
	return (q.rear - q.front + maxsize) % maxsize;
}
int GetHead(squeue Q)          //待解决
{
	if (Q.front != Q.rear)              //队列不为空
		return Q.data[Q.front];         //返回队头指针元素的值，队头指针不变
}
int main()
{
	squeue haha;
	init(haha);
	int n;
	int e;
	cout << "队列个数:"; cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> e;
		enqueue(haha, e);
		dequeue(haha, e);
		cout << e << " ";

	}
	cout << length(haha);

}

链栈（了解）

#include<iostream>
using namespace std;
//#define SElemType int
#define SElemType char
/*链栈用不带头结点的单链表实现，栈顶指针就是链表的头指针
1.链表的头指针就是栈顶。
2.不要头结点。
3..基本不存在栈满的情况。
4.空栈相当于头指针指向空。
5.插入和删除仅在栈顶处执行。*/
typedef struct stacknode
{
	SElemType data;
	stacknode* next;
}stacknode, * linkstack;
int initstack(linkstack& s)
{
	s = NULL;
	return 1;
}
int stackempty(linkstack s)
{
	if (s == NULL)return 1;
	else return 0;
}
void push(linkstack& s, SElemType e)
{
	stacknode* p;
	p = new stacknode;
	p->data = e;
	p->next = s;
	s = p;
}
int pop(linkstack& s, SElemType& e)
{
	linkstack p;
	if (s == NULL)
		return 0;
	e = s->data;
	p = s;
	s = s->next;
	delete p;
	return 1;
}
int main()
{
	linkstack haha;
	initstack(haha);
	SElemType e;
	int n;
	cout << "要入栈的元素个数："; cin >> n;
	for (int i = n; i > 0; i--)
	{
		cin >> e;
		push(haha, e);
	}
	while (!stackempty(haha))
	{
		pop(haha, e);
		cout << e << " ";
	}
}