1.栈
栈是特殊的线性表，顺序储存
Typedef int ElemType;
struct Stack
{
ElemType data[MAXSIZE];
int top; // 存放栈顶指针
}
bool initStack(Stack *s) //初始化一个栈{ s->top = -1; //栈指针指向-1 return true;}
bool pushStack(Stack *s,ElemType e)
{
if(s->top == MAXSIZE - 1) //栈满
{
return false;
}
s->top++; //栈顶指针++ ，压栈压入栈底
s->data[s->top] = e;
return true;
}
bool popStack(Stack *s)
{
while(s->top != -1) //出栈，从栈顶出
{
printf("%d ", s->data[ s->top]);
s->top--;
}
return true;
}
入栈和出栈的时间复杂度均为O(1)，但栈需要开辟合适的空间来存放对应的数据
1.1栈的链式存储结构
栈顶指针作为头节点不改变，栈顶放在单链表的头部
struct Node{ ElemType data; Node *next;}; // 单链表的结构，存储链表栈中的数据
struct LinkStack{ Node *top; //存放链表栈的顶部指针 int count;};
bool initLinkStack(LinkStack *s) // 链栈需要初始化{ s->top = NULL; //栈顶指针指向为空
s->count = 0; // 计数值 return true;}
bool pushLinkStack(LinkStack *s,ElemType e)
{
Node *L= (struct Node*)malloc(sizeof(Node));
L->data = e;
L->next = s->top; //栈顶指针下移
s->top = L; //将栈顶指针赋值单链表的头指针
s->count++
return true;
}
bool popLinkStack(LinkStack *s)
{
Node *L;
while(s->top != NULL)
{
printf("%d ",s->top->data);
L = s->top; //栈顶节点赋值给L
s->top = s->top->next; //栈顶指针下移
free(L); //释放最上面的栈顶节点
s->count--;
}
}
2.队列（FIFO）
插入数据只能在队尾进行，删除数据在队头进行
队列需要指定长度
front指针指向队头指针，rear指针指向队尾的下一个位置
当front = rear时，此时队列为空
循环队列中，front = rear且计数count = 队列的大小，则为队满
front = rear且计数count =0，则为队空
typedef MAXSIZE 20; //队列的长度
struct Queue
{
ElemType data[MAXSIZE];
int front; //队头指针
int rear; //尾指针，指向尾元素的下一个位置
int cout; //队列中元素计数
}
bool initQueue(Queue *Q)
{
Q->front = Q->rear;
Q->count = 0; //计数值为0，队列为空
return true;
}
//入队
bool inputQueue(Queue *Q,ElemType e)
{
if((Q->front == Q->rear)&&Q->count == MAXSIZE)
{
return false; //队满
}
else
{
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1)%MAXSIZE; // 对队列长度取余数，在超过队列长度后，rear指向队列空的位置
Q->count++; //队列中元素个数++
return true;
}
}
bool outQueue(Queue *Q)
{
if((front == rear)&&Q->count == 0)
{
return false; //此时队列为空
}
else
{
printf("%d ",Q->data[Q->front]); // 从队头出元素
Q->front = （Q->front + 1）% MAXSIZE; // 队头往后移动
Q->count--;
return true;
}
}