关键词：
栈与队列
栈是限定尽在表尾进行插入和删除操作的线性表
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
栈的定义：
栈(Stack)是限定仅在表尾进行插入和删除操作的线性表
其中允许插入的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为先进后出(Last In First Out)的线性表，简称为LIFO结构。
特殊之处在与限制了这个线性表的插入和删除位置只能是在栈顶。
栈的插入操作，叫做进栈，也称为压栈、入栈。
栈的删除操作，叫做出栈，也有的叫做弹栈。
栈的抽象数据类型：
ADT 栈(Stack) Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation InitStatic(*S):初始操作，建立一个空栈S DestroyStack(*S):若栈存在则销毁它。 ClearStack(*S):将栈清空 StackEmpty(S):若栈为空，则返回true,否则返回false GetTop(S,*s):若栈存在且非空，用e返回S的栈顶元素 Push(*S,e)：若栈S存在，插入新的元素e到 Pop(*S,*e):删除栈S中栈顶元素，并用e返回其值 StackLength(S):返回栈S的元素个数。 endADT
栈的顺序存储结构及实现：
栈的顺序存储结构
定义：
typedef int SElemType; typedef struct { SElemType data[MAXSIZE]; int top; }SqStack;
Status Push(SqStack *s,SElemType e) { if(S->top==MAXSIZE-1) return ERROR; S->top++; s->data[S->top] = e; return OK; }
Status Pop(SqStack *S,SElemType *e) { if(S->top==-1) return ERROR; *e = S->data[S->top]; S->top--; return OK; }
两栈共享空间
两栈共享空间的结构的代码如下：
typedef struct { SElemType data[MAXSIZE]; int top1; int top2; }SqDoubleStack; Status Push(SqDoubleStack *S,SElemType e,stackNumber) { if(S->top+=S->top2)//栈满 return ERROR; if(stackNumber==1) S->data[++S->top1] = e; else if(stackNumber==2) S->data[--S->top2] = e; return OK; } Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber) { if(stackNumber==1) { if(S->top1==-1) return ERROR; *e=S->data[S->top1--]; } else if(stackNumber==2) { if(S-top2==MAXSIZE) return ERROR; *e=S->data[S->top2++]; } return OK; }
栈的链式存储结构及实现
对于链栈来说基本不存在栈满的情况，除非内存已经没有可以使用的空间。
链栈的结构代码如下：
typedef struct StackNode { SElemType data; struct StackNode *next; }StackNode,*LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack;
Status Push(LinkStack *S,SElemType e) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode))； s->data = e; s->next = S->top; s->top = s; S->count++; return OK; }
Status Pop(LinkStack *S,SElemType *e) { LinkStackPtr p; if(StackEmpty(*S)) return ERROR; *e=S->top->data; p = S->top; S->top = S->top->next; free(p); S->count--; return OK; }
注：关于顺序栈和链栈的讨论
如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是使用链栈，反之，如果它的变化在可控的范围内，建议使用顺序栈会更好一些。
栈的作用：栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。
栈的应用--递归
斐波那契数列(Fibonacci)
//直接计算 int main() { int i; int a[40]; a[0] = 0; a[1] = 1; printf("%d",a[0]); printf("%d",a[1]); for(i=2;i<40;i++) { a[i] = a[i-1]+a[i-2]; printf("%d\n",a[i]); } return 0; }
//使用递归计算，测试后知道，使用递归会急剧增加运算时间 int Fbi(int i) { if(i<0) return 0; else if(i==0) return 0; else if(i==1) return 1; else return Fbi(i-1)+Fbi(i-2); } int main() { int i; for(i=0;i<40;i++) printf("%d\n",Fbi(i)); return 0; }
对递归的定义
把一个直接调用自己活通过一系列的调用语句间接的调用自己的函数，称做递归函数。
每个递归定义至少必须有一个条件，满足递归时不再进行，即不再引用自身而是返回值退出。
栈的应用--四则运算表达式求值：
后缀(逆波兰)表示法定义:不需要括号的后缀表示法，我们也把它称为逆波兰(Reverse Polish Notation,RPN)表示。
后缀表达式计算结果：
此处为了表达方便，应有配图
中缀表达式转后缀表达式：
此处为了表达方便，应有配图
队列的定义：
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。
队列是一种先进先出(First in First Out)的线性表，简称为FIFO.允许插入的一端称为队尾，允许删除的一端称为队头。
队列的抽象数据类型：
ADT 队列(Queue) Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation InitQueue(*Q)：初始化操作，建立一个空队列Q. DestroyQueue(*Q):若队列Q存在则销毁它。 ClearQueue(*Q):将队列清空 QueueEmpty(Q):若队列为空则返回true,否则返回false GetHead(Q,*e):若队列存在且非空，用e返回队列Q的队头元素。 EnQueue(*Q,e):若队列Q存在，插入新元素e到队列Q中并成为队尾元素 DeQueue(*Q,*e):删除队列Q的队头元素，并且用e返回其值 QueueLength(Q):返回队列Q的元素个数 endADT
循环队列
队列也存在顺序存储和链式存储
队列顺序存储的不足：队头指针和队尾指针的问题，如果不循环，那么就可能造成位置空缺的问题。
循环队列的定义：队列的头尾相接的顺序存储结构称为循环队列。
队列满的条件是：
(rear+1)%QueueSize == front
(取模“%”的目的就是为了整合rear与front大小为一个问题)
通用的计算队列长度的公式：
(rear-front+QueueSize)%QueueSize
定义：
typedef int QElemType; typedef struct { QElemType data[MAXSIZE]; int front; int rear; }SqQueue;
操作：
//初始化空队列Q Status InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; return OK； } //返回Q的元素个数 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } //若队列未满，则插入元素e为Q新的队尾元素 Status EnQueue(SqQueue *Q,QElemType e) { if((Q->rear+1)%MAXSIZE==Q->front) return ERROR; Q->data[Q->rear] = e; Q->rear = (Q->rear+1)%MAXSIZE; return OK; } //出队列 Status DeQueue(SqQueue *Q,QElemType *e) { if(Q->front = Q->rear) //队列为空 return ERROR; *e=Q->data[Q->front]; Q->front = (Q->front+1)%MAXSIZE; return OK; }
队列的链式存储结构及实现
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
链队列的结构为：
typedef int QElemType; typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front,rear; }LinkQueue;
//入队操作 Status EnQueue(LinkQueue *Q,QElemType e) { QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if(!s) //存储分配失败 exit(OVERFLOW); s->data = e; s->next = NULL; Q->rear->next = s; Q->rear = s; return OK; }
//出队操作 Status DeQueue(LinkQueue *Q,QElemType *e) { QueuePtr p; 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; free(p); return OK; }
本章内容
栈
顺序栈
两栈共享空间
链栈
队列
顺序队列
循环队列
链队列
《大话数据结构》笔记（4-1）--栈与队列：栈
栈的Java实现代码：https://github.com/Lyu0709/data-structure/blob/master/src/com/coding/basic/stack/Stack.java逆波兰算法实现：https://github.com/Lyu0709/data-structure/blob/master/src/com/coding/basic/stack/RPN.java& 查看详情
数据结构之栈与队列
...offer》总结笔记，供学习使用） 栈是一种常见的数据结构，在操作系统中会给每个进程创建一个栈来存储函数调用时各个函数的参数、返回地址以及临时变量等。栈的特点是后进先出。 队列是另外一种很重要的... 查看详情
数据结构之栈与队列(代码片段)
...列 栈与队列是程序设计中广泛使用的两种重要的线性数据结构。 栈是LIFO（LastInFirstOut），先存进去的数据只能最后被取出来，进出顺序逆序，即先进后出，后进先出。 队列是FIFO（FirstInFirstOut... 查看详情
栈与队列
...数据元素，在表头删除数据元素,满足“FirstInFirstOut”。栈与队列的相同点：1.都是线性结构。2.插入操作都是限定在表尾进行。3.都可以通过顺序结构和链式结构实现。、4.插入与删 查看详情
算法-栈与队列（c语言实现）
目标：理解栈与队列这两种数据结构，并且知道如何应用。 算法+数据结构=程序 一、堆栈堆栈是一组元素的集合，类似于数组，但数组可以按下标访问，堆栈的访问规则只能为push与pop两种操作。堆栈只能访问或者移出栈... 查看详情
数据结构系列栈与队列
栈定义栈是一种特殊的线性表 操作 存储结构从存储结构来看，分为顺序栈和链栈，同线性表的划分 应用递归-菲波那切数列后缀表达式-逆波兰表示 队列定义队列也是一种特殊的线性表 操作队列... 查看详情
数据结构与算法--栈与队列
栈和队列栈和队列都是比较常用的数据结构。栈的应用非常的广泛，比如说，递归函数的实现就是借助于栈保存相关的数据。操作系统中每个线程也会使用栈来保存函数调用涉及到的一些参数和其他变量等。栈最大的一个特点就... 查看详情
栈与队列的区别
...的一端进行插入和在另一端进行删除操作的线性表。从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"... 查看详情
小猪的数据结构辅助教程——3.1栈与队列中的顺序栈
小猪的数据结构辅助教程——3.1栈与队列中的顺序栈标签（空格分隔）：数据结构本节学习路线图与学习要点学习要点1.栈与队列的介绍。栈顶，栈底，入栈，出栈的概念2.熟悉顺序栈的特点以及存储结构3.掌握顺序栈的基本操作... 查看详情
数据结构第八章：栈与队列
一、栈 1、概念 数据的插入和删除都是在同一端，不能在其他任何位置，这种逻辑结构称之为栈。 2、特性 后进先出。或者说先进后出 3、分类 ... 查看详情
栈与队列(代码片段)
最近一直在看数据结构与算法，下面是对有线性结构的栈与队列的总结：栈相关的内容定义：栈是限定仅在表尾进行插入和删除操作的线性表。（后进先出的线性表）操作：在可以插入与删除的一端称为栈顶，另外一端称为栈底... 查看详情
数据结构栈与队列的实现(代码片段)
基础结构typedefintSTDataType;typedefstructStackSTDataType*_a;inttop;//栈顶intcapacity;//容量Stack;申请空间voidListCapacity(Stack*ps)if(ps->top==ps->capacity)intnewcapacity=ps->capacity 查看详情
第4章栈与队列-----队列
队列（queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出（FirstINFirstOut)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为对头。 队列的抽象数据类型&nbs... 查看详情
数据结构与算法知识点总结队列栈与散列表
1.队列队列是一种FIFO的数据结构，它有两个出口，限定只能在表的一端进行插入(队尾插入)和在另一端进行删除(队头删除)操作，同样的它也没有遍历行为。由于在队列的顺序存储中无法判断队列满的条件，一般地如果用数组实... 查看详情
数据结构习题--栈与队列(代码片段)
双栈模拟队列基本思路：队列是先进先出，栈是先进后出。用一个输入栈存进队元素，用一个输出栈将输出栈中的元素倒置，再出栈。这就实现了队列的先进先出。注意：队满的条件为输入栈S1满且输出栈S2非空。并非输入栈满... 查看详情
3）数据结构之线性表（栈与队列）(代码片段)
目录栈与队列的本质栈的基本概念栈的物理结构栈的顺序存储结构（用数组实现）静态栈的实现： Stack.h中Test/c中Stack.c中输出结果动态栈的实现 Stac.h中Test.c中Stack.c中栈的链式存储结构（使用链表实现） Stack... 查看详情
图解堆算法链表栈与队列（mark）
...与队列（多图预警） 堆（heap），是一类特殊的数据结构的统称。它通常被看作一棵树的数组对象。在队列中，调度程序反复提取队列中的第一个作业并运行，因为实际情况中某些时间较短的任务却可能需要等待很长时... 查看详情
数据结构与算法栈与队列c语言版(代码片段)
目录3.1栈和队列的定义和特点3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的... 查看详情