栈和队列
2019-04-10 本文已影响0人
全村的卡密
栈和队列
本质上是稍加限制的线性表
栈和队列定义
栈
顺序栈定义
typedef struct
{
int data[maxSize];
int top;
}sqStack;
链栈结点定义
typedef struct sNode
{
int data;
struct sNode *next;
}sNode;
队列
顺序队列
typedef struct
{
int data[maxSize];
int front;
int rear;
}sqQueue;
链队列
链队类型定义
typedef struct qListNode
{
struct qListNode *front;
struct qListNode *rear;
}qListNode;
链队节点定义
typedef struct qNode
{
int dada;
struct qNode *next;
}qNode;
栈的四个操作
- 进栈 :实质就是头插法
- 出栈 :实质就是删除
- 栈空 :st.top == -1 or lst->next ==NULL
- 栈满:st.top ==maxSize-1 链表不存在栈满
顺序队列(队列的优化,克服了假溢出)
队的基本操作:
循环指针:front =(front+1)%maxSize;
队空:front ==rear;
队满:(rear+1)%maxSize ==front;
进队:qu.rear=(qu.rear+1)%maxSize;qu[qu.rear].data =x;
出队:qu.front =(qu.front+1)%maxSize;x = qu[qu.front].data;