栈和队列也是线性表，栈和队列的进本操作是线性表操作的子集，它们是操作受限的线性表
栈：
限定仅在表尾进行插入或者删除操作的线性表，表尾端叫做栈顶，表头叫做栈底；栈的修改遵循后进先出(last in first out)。
1.栈的顺序表示法：
栈的数据结构：
typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //本栈已经分配的内存空间
}Sqstack;
初始时top=base；如果base=NULL说明栈空间不存在，每当栈中插入新元素时top+1，top指针永远在栈顶元素的上面(如果不这样的话无法判断栈中是否有元素)，下图是栈操作图：
栈的初始化：
#define STACK_INIT_SIZE 100; //栈空间初始分配量
#define STACKINCREMENT 10; //栈空间分配增量
Status InitStack(Sqstack &S){
S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
注意：当栈满之后要再追加内存
push和pop操作：
Status Push(Sqstack &S,SElemType e){
if(S.top-S.base>=S.stacksize){
S.base = (SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(overflow);
S.top = S.base+S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(Sqstack &S,SElemType &e){
if(S.top==S.base) return ERROR;
e = * --S.top;
return OK;
}
实例应用>数制转换 10进制转8进制，转换规则如下：
#define STACK_INIT_SIZE100
#define STACKINCREMENT10
typedef struct{
int *base;//栈底指针
int *top;//栈顶指针
int stacksize;//本栈已经分配的内存空间
}Sqstack;
int InitStack(Sqstack&S){ //空栈初始化
S.base= (int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S.base)exit(0);
S.top= S.base;
S.stacksize=100;
return 1;
}
int Push(Sqstack&S,int e){ //push操作
if(S.top-S.base>=S.stacksize){
S.base= (int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base)exit(0);
S.top= S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++ = e;
return 1;
}
int Pop(Sqstack&S,int &e){ //pop操作
if(S.top==S.base) return -1;
e = * --S.top;
return 1;
}
验证：
int main(int argc, constchar* argv[]) {
// insert code here...
std::cout<<"hello world"<<"\n";
Sqstack S;
InitStack(S);
int N =0;
int e =10;
scanf("%d",&N);
while (N) {
Push(S, N%8);
N = N/8;
}
while (S.top!=S.base) {
Pop(S, e);
printf("出：%d \n",e);
}
return 0;
}
结果：
队列：
允许删除的一端叫队头(front)，允许插入的一段叫队尾(rear)；队列的修改遵循先进先出(first in first out)。
队列链式实现的数据结构：
typedef struct QNode{ //队列的结点结构
QElemType data;
struct QNode*next;
}QNode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
队列的链式实现举例：
typedefstruct qnode{
int data;
qnode*next;
}QNode; //节点
typedefstruct Queue{ //链队定义
QNode*front;
QNode*rear;
}LiQueue;
int InitQueue(LiQueue*&q)//初始化 构造一个没有头节点的队列{
q = (LiQueue*)malloc(sizeof(Queue));
if(!q) return 0;
q->front=NULL;
q->rear=NULL;
return 1;
}
bool QueueEmpty(LiQueue*q){ //判断队列是否为空
return NULL== q->rear;
}
int InQueue(LiQueue*&q,int e)//入队{列
QNode*p = (QNode*)malloc(sizeof(QNode));
if(!p) return0;
p->data= e;
p->next=NULL;
if(QueueEmpty(q)){
q->front= p;
q->rear= p;
}
else{
q->rear->next= p;
q->rear= p;
}
return 1;
}
bool DeQueue(LiQueue*&q,int &e)//出队{
if(QueueEmpty(q))//队为空{
return false;
}
QNode*t = q->front;
if(q->front== q->rear)//队中只含一个数据元素{
q->front= q->rear=NULL;
}
else//队中含有两个及以上数据元素{
q->front= t->next;
}
e = t->data;
free(t);
t =NULL;
return true;
}
bool TraverseQueue(LiQueue*q)//遍历{
if(QueueEmpty(q))
{
return false;
}
QNode*p = q->front;
while(p !=NULL) {
std::cout<< p->data<
p = p->next;
}
return true;
}
验证：
int main(int argc, constchar* argv[]) {
// insert code here...
std::cout<<"hello world"<<"\n";
LiQueue *q;
InitQueue(q);
InQueue(q,1);
InQueue(q,2);
InQueue(q,3);
InQueue(q,4);
TraverseQueue(q);
int exitv =0;
DeQueue(q, exitv);
TraverseQueue(q);
return0;
}
输出为：
