数据结构辅导栈和队列1一、栈1.栈的定义栈(Stack)又称堆栈，它是一种运算受限的线性表，其限制是仅答应在表的一端进行插入和删除运算。
人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。
向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。
在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上，相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。
又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则为进栈；射击时子弹总是从顶部一个接一个地被射出，此为子弹出栈。
由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表(Last In First Out,简称LIFO)。
例如，假定一个栈S为(a,b,c)，其中字符c的一端为栈顶，字符c为栈顶元素。
若向S压入一个元素d，则S变为(a,b,c,d)，此时字符d为栈顶元素；若接着从栈S中依次删除两个元素，则首先删除的是元素d，接着删除的使元素c，栈S变为(a,b)，栈顶元素为b。
视频教程'css.shtml'target='_blank'title='div视频教程'div 2.栈的存储结构栈既然是一种线性表，所以线性表的顺序存储和链接存储结构同样适用于栈。
(1)栈的顺序存储结构栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现，利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。
假定栈数组用stack[StackMaxSize]表示，指示栈顶位置的整型变量用top表示，则元素类型为ElemType的栈的顺序存储类型可定义为：ElemType stack[StackMaxSize]；int top；其中，StackMaxSize为一个整型全局常量，需事先通过const语句定义，由它确定顺序栈(即顺序存储的栈)的最大深度，又称为长度，即栈最多能够存储的元素个数；由于top用来指示栈顶元素的位置，所以把它称为栈顶指针。
数据结构：线性表（栈和队列）1、栈和队列（1）栈只能在表的⼀端（栈顶）进⾏插⼊和删除运算的线性表是⼀种插⼊和删除只能在“端点”进⾏的线性表，栈只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则（叠盘⼦）（2）队列只能在表的⼀端（队尾）进⾏插⼊，在另⼀端（队头）进⾏删除运算的线性表先进先出（FIFO）例如：排队（3）运算规则顺序表：随机链表：顺序存取栈：后进先出队列：先进先出2、顺序栈（1）顺序栈的表⽰#define MAXSIZE 100typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;（2）初始化Status InitStack( SqStack &S ){S.base =new SElemType[MAXSIZE]；if( !S.base ) return OVERFLOW;S.top = S.base;S.stackSize = MAXSIZE;return OK;}分配空间并检查空间是否分配失败，若失败则返回错误设置栈底和栈顶指针：S.top = S.base;设置⼤⼩（3）判断是否为空bool StackEmpty( SqStack S ){if(S.top == S.base) return true;else return false;}（4）长度int StackLength( SqStack S ){return S.top – S.base;}（5）清空Status ClearStack( SqStack S ){if( S.base ) S.top = S.base;return OK;}（6）销毁Status DestroyStack( SqStack &S ){if( S.base ){delete S.base ;S.stacksize = 0;S.base = S.top = NULL;}return OK;}（7）进栈Status Push( SqStack &S, SElemType e){if( S.top - S.base== S.stacksize ) // 栈满return ERROR;*S.top++=e;return OK;}判断是否栈满，若满则出错元素e压⼊栈顶栈顶指针加1（8）出栈Status Pop( SqStack &S, SElemType &e){if( S.top == S.base ) // 栈空return ERROR;e＝*--S.top;return OK;}判断是否栈空，若空则出错获取栈顶元素e栈顶指针减1（9）取栈顶元素Status GetTop( SqStack S, SElemType &e){if( S.top == S.base ) return ERROR; // 栈空 e = *( S.top – 1 );return OK;}判断是否空栈，若空则返回错误否则通过栈顶指针获取栈顶元素3、链栈（1）链栈的表⽰typedef struct StackNode {SElemType data;struct StackNode *next;} StackNode, *LinkStack;LinkStack S;（2）初始化void InitStack(LinkStack &S ){S=NULL;}（3）判断是否为空Status StackEmpty(LinkStack S){if (S==NULL) return TRUE;else return FALSE;}（4）进栈Status Push(LinkStack &S , SElemType e){p=new StackNode; //⽣成新结点pif (!p) exit(OVERFLOW);p->data=e;p->next=S;S=p;return OK;}（5）出栈Status Pop (LinkStack &S,SElemType &e){if (S==NULL) return ERROR;e = S-> data; p = S; S = S-> next;delete p; return OK;}（6）取栈顶元素Teletype GetTop(LinkStack S){if (S==NULL) exit(1)；else return S–>data;}4、队列的顺序表⽰（1）定义#define M 100 //最⼤队列长度Typedef struct {QElemType *base; //初始化的动态分配存储空间int front; //头指针int rear; //尾指针}SqQueue;5、循环队列（1）定义#define MAXQSIZE 100 //最⼤长度Typedef struct {QElemType *base; //初始化的动态分配存储空间int front; //头指针int rear; //尾指针}SqQueue;（2）初始化Status InitQueue (SqQueue &Q){Q.base =new QElemType[MAXQSIZE]if(!Q.base) exit(OVERFLOW);Q.front=Q.rear=0;return OK;}（3）长度int QueueLength (SqQueue Q){return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }（4）⼊队Status EnQueue(SqQueue &Q,QElemType e){if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}（5）出队Status DeQueue (LinkQueue &Q,QElemType &e){if(Q.front==Q.rear) return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}6、链队列（1）定义typedef struct QNode{QElemType data;struct Qnode *next;}Qnode, *QueuePtr;typedef struct {QueuePtr front; //队头指针QueuePtr rear; //队尾指针}LinkQueue;（2）初始化Status InitQueue (LinkQueue &Q){Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW);Q.front->next=NULL;return OK;}（3）销毁Status DestroyQueue (LinkQueue &Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear; }return OK;}（4）是否为空Status QueueEmpty (LinkQueue Q){return (Q.front==Q.rear);}（5）求队头元素Status GetHead (LinkQueue Q, QElemType &e){if(Q.front==Q.rear) return ERROR;e=Q.front->next->data;return OK;}（6）⼊队Status EnQueue(LinkQueue &Q,QElemType e){p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW);p->data=e; p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;}（7）出队Status DeQueue (LinkQueue &Q,QElemType &e){if(Q.front==Q.rear) return ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;delete p;return OK;}。
数据结构--栈和队列基础知识⼀概述栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂章，做重点讲解。
既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。
使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。
⼆栈2.1 栈的基本概念同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。
从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。
因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。
通常，栈的开⼝端被称为栈顶；相应地，封⼝端被称为栈底。
因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下中的栈底元素为元素 1。
2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。
