3387人阅读
数据结构与算法（11）
栈本质上是一个线性表，只不过对线性表的操作进行了限制，只可以在表的一端进行操作（插入、删除元素）。栈是一种是一种实现数据“先进后出”的存储结构，分为静态栈和动态栈，静态栈就是以数组的方式存储数据，动态栈是以链表的方式存储数据；对栈的操作算法，常用的就是压栈和出；下面将以链式的方式创建栈，并对用c语言实现栈的压栈和出栈的算法：
1.栈的创建
& & 在创建一个数据结构之前，必须知道这种数据结构由哪些参数组成，栈的本质既然是个链表，它必然由很多节点组成；为了实现“先进后出”这种数据结构，我们需要引进两个参数，一个是栈顶指针（pTop），始终指向栈顶元素。一个参数是栈底指针（pBottom），始终指向栈底元素。我们知道为了方便描述链表的各种操作，引进了头节点的概念，即为每个链表前面加一个头节点，但并存放有效数据；同样，为了实现栈的操作，我们同样需要一个不存放任何有效数据的节点，并且栈底指针始终指向该节点；
//定义一个节点
typedef struct Node
struct Node *pN
}NODE,*PNODE;//
//构造一个栈
typedef struct stack
PNODE pT //栈顶指针
PNODE pB//栈底指针
}STACK,*PSTACK;其中，使用了typedef关键词，typedef只是给一个数据类型提供一个别名；因此这里的NODE=struct Node ，PNODE=struct Node *；同样，STACK=struct stack ，PSTACK=struct Node *;
此时，数据类型构造出来了，接下来要创建一个空栈，这样我们才能进行栈的操作，创建栈，无非就是分配内存，内存分配有三种方式，静态存储区，栈，堆；
//创建一个空栈，里面没有任何有效数据；
void Create_Stack(PSTACK S)
S-&pBottom=(struct Node *)malloc(sizeof(struct Node));
if(NULL==S-&pBottom)
printf(&Memory allocation failure&);
S-&pTop=S-&pB
S-&pTop-&data=0;
S-&pTop-&pNext=NULL;
//防止出现野指针
图1 空栈示意图
2.压栈算法
图2 压栈算法示意图
压栈的伪算法：
（1）.创建一个节点p，并修改节点的指针域使其指向栈顶数据元素；p-&pNext=pTop；
（2）修改栈顶指针，使其指向栈顶元素，pTop=p；
程序代码：
void Push_Stack(PSTACK S,int val)
PNODE p=(struct Node *)malloc(sizeof(struct Node));
if(NULL==p)
printf(&Memory allocation failure&);
p-&pNext=S-&pT
//让p的指针域指向上一个节点
S-&pTop=p;
//让pTop指针指向栈顶元素
3.出栈算法
图3.出栈算法示意图
出栈伪算法：
（1）.先用P指针保存要删除数据的地址，用于便于释放此节点的内存，即p=pTop；
（2）.修改栈顶指针的指向，使其指向栈顶元素；pTop=pTop-&pN
附录：程序代码
stack.h文件代码：
#ifndef __STACK_H_
#define __STACK_H_
//定义一个节点
typedef struct Node
struct Node *pN
}NODE,*PNODE;//
//构造一个栈
typedef struct stack
PNODE pT //栈顶指针
PNODE pB//栈底指针
}STACK,*PSTACK;
//函数声明区
void Create_Stack(PSTACK S);
void Push_Stack(PSTACK S,int val);
bool Pop_Stack(PSTACK S,int *val);
void Traverse_Stack(PSTACK S);
void Clear_Stack(PSTACK S);
stack.c文件代码：
#include&stdio.h&
#include&stdlib.h&
#include&stack.h&
//创建一个空栈，里面没有任何有效数据；
void Create_Stack(PSTACK S)
S-&pBottom=(struct Node *)malloc(sizeof(struct Node));
if(NULL==S-&pBottom)
printf(&Memory allocation failure&);
S-&pTop=S-&pB
S-&pTop-&data=0;
S-&pTop-&pNext=NULL;
//防止出现野指针
void Push_Stack(PSTACK S,int val)
PNODE p=(struct Node *)malloc(sizeof(struct Node));
if(NULL==p)
printf(&Memory allocation failure&);
p-&pNext=S-&pT
//让p的指针域指向上一个节点
S-&pTop=p;
//让pTop指针指向栈顶元素
//打印出栈里面的元素
void Traverse_Stack(PSTACK S)
PNODE p=S-&pT
printf(&栈中的元素是：\n&);
while(p!=S-&pBottom)
printf(&%d &,p-&data);
printf(&\n&);
bool Is_Empty(PSTACK pS)
if (pS-&pTop == pS-&pBottom)
bool Pop_Stack(PSTACK S,int *val)
if(Is_Empty(S))
PNODE p=S-&pT
*val=S-&pTop-&
S-&pTop=S-&pTop-&pN
//使pTop指针指向栈顶元素；
//释放p指针所指向的那个节点的内存；
//要养成好的习惯；
void Clear_Stack(PSTACK S)
if(Is_Empty(S))
PNODE p=NULL;
//养成一好习惯，定义指针记得初始化；
while(S-&pTop!=S-&pBottom)
S-&pTop=S-&pTop-&pN
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：269369次
积分：2058
积分：2058
排名：第16126名
原创：25篇
转载：33篇
评论：53条
文章：14篇
阅读：70242
文章：10篇
阅读：86390
(1)(1)(3)(1)(2)(6)(15)(1)(9)(11)(3)(5)君，已阅读到文档的结尾了呢~~
堆栈的应用及操作
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构，栈与栈的应用实例
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口53466人阅读
c/c++（22）
数据结构与算法（28）
1.1&栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：
结论：后进先出（Last
In First Out），简称为LIFO线性表。
栈的基本运算有六种：
构造空栈：InitStack(S)、
判栈空: StackEmpty(S)、
判栈满：&StackFull(S)、
进栈：&Push(S,x)、可形象地理解为压入，这时栈中会多一个元素
退栈：&Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。
取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。
& 由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。
我们要了解的是，在顺序栈中有&上溢&和&下溢&的概念。顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是&上溢&,&上溢&也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是&下溢&。&下溢&本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。
链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
栈的顺序存储
使用c++的面向对象封装：
// Test.cpp : Defines the entry point for the console application.
#include &stdafx.h&
#include &iostream&
#define MAX 10 // MAXIMUM STACK CONTENT
class stack
int arr[MAX];
inItStack();
/************************************************************************/
/* 初始化栈
/************************************************************************/
void inItStack()
/************************************************************************/
/************************************************************************/
void push(int a)
if(top & MAX)
arr[top]=a;
cout&&&STACK FULL!!&&&
/************************************************************************/
/************************************************************************/
if(isEmpty())
cout&&&STACK IS EMPTY &;
return NULL;
int data=arr[top];
arr[top]=NULL;
/************************************************************************/
/* 是否为空
/************************************************************************/
bool isEmpty()
if(top == -1)
int main()
a.push(3);
a.push(10);
a.push(1);
cout&&&Pop:&&&a.pop();
结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
1.3 栈的链式存储
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作&链栈&。链栈通常用一个无头结点的单链表表示。如图所示：
栈的操作是线性表操作的特例。
简单用c实现：
// Test.cpp : Defines the entry point for the console application.
#include &stdafx.h&
#include &stdio.h&
#include &stdlib.h&
#include &iostream&
#define TRUE
#define FALSE
#define OK
#define ERROR
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACKEMPTY -3
#define LT(a,b)
#define N = 100
typedef int S
typedef int ElemT
typedef struct LNode{
struct LNode
}LNode, *LinkL
typedef struct stack{
/************************************************************************/
/************************************************************************/
void InitStack(STACK &S);
void Push(STACK &S,ElemType e);
void Pop(STACK &S, ElemType *e);
ElemType GetTop(STACK S,ElemType *e);
int StackEmpty(STACK S);
/************************************************************************/
/************************************************************************/
void InitStack(STACK &S)
S.top=NULL;
/************************************************************************/
/************************************************************************/
void Push(STACK &S,ElemType e)
p = (LinkList )malloc(sizeof(LNode));
if (!p) exit(OVERFLOW);
p-&next = S.
/************************************************************************/
/************************************************************************/
void Pop(STACK &S, ElemType *e)
if(StackEmpty(S)) exit(STACKEMPTY);
*e = S.top-&
S.top = p-&
/************************************************************************/
/* 获取栈顶元素内容
/************************************************************************/
ElemType GetTop(STACK S, ElemType *e)
if(StackEmpty(S)) exit(STACKEMPTY);
*e = S.top-&
/************************************************************************/
/* 判断栈S是否空
/************************************************************************/
int StackEmpty(STACK S)
if(S.top==NULL) return TRUE;
void main()
InitStack( S);
Push(S, 3);
Push(S, 4);
Pop(S,&e);
cout&&&Pop elem:&&&e;
1.4 栈的应用
1) &数制转换
2）语法词法分析
3）表达式求值等
1.5 栈的递归和实现
汉诺塔的问题：
1）如果有一个盘子，直接从X移到Z即可。
2）如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。
完整实现代码，包括栈的实现：
// Test.cpp : Defines the entry point for the console application.
#include &stdafx.h&
#include &stdio.h&
#include &stdlib.h&
#include &iostream&
#define TRUE
#define FALSE
#define OK
#define ERROR
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACKEMPTY -3
#define LT(a,b)
#define N = 100
typedef int S
typedef int ElemT
typedef struct LNode{
struct LNode
}LNode, *LinkL
typedef struct stack{
/************************************************************************/
/************************************************************************/
void InitStack(STACK &S);
void Push(STACK &S,ElemType e);
void Pop(STACK &S, ElemType *e);
ElemType GetTop(STACK S,ElemType *e);
int StackEmpty(STACK S);
/************************************************************************/
/************************************************************************/
void InitStack(STACK &S)
S.top=NULL;
/************************************************************************/
/************************************************************************/
void Push(STACK &S,ElemType e)
p = (LinkList )malloc(sizeof(LNode));
if (!p) exit(OVERFLOW);
p-&next = S.
/************************************************************************/
/************************************************************************/
void Pop(STACK &S, ElemType *e)
if(StackEmpty(S)) exit(STACKEMPTY);
*e = S.top-&
S.top = p-&
/************************************************************************/
/* 获取栈顶元素内容
/************************************************************************/
ElemType GetTop(STACK S, ElemType *e)
if(StackEmpty(S)) exit(STACKEMPTY);
*e = S.top-&
void printStack(STACK S){
printf(&栈： &);
while (p) {
printf(&%d &, p-&data);
/************************************************************************/
/* 如果有一个盘子，直接从X移到Z即可。
如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。
/************************************************************************/
void move(STACK &Sa,STACK &Sb)
Pop(Sa,&e);
Push(Sb, e);
void hanoi(int n,STACK
&X,STACK &Y,STACK &Z)
if(n==1) return move(X, Z);
//将圆盘1号直接移到z
hanoi(n-1,X,Z,Y);
//将x上的1大n-1圆盘移到y，z做辅助塔
move(X, Z);
//将编号为n的圆盘移z
hanoi(n-1,Y,X,Z);
//将y上的1大n-1圆盘移到z，x做辅助塔
/************************************************************************/
/* 判断栈S是否空
/************************************************************************/
int StackEmpty(STACK S)
if(S.top==NULL) return TRUE;
void main()
STACK Sx, Sy,Sz;
InitStack( Sx);
InitStack( Sy);
InitStack( Sz);
int i, n = 10;
for (i = 10 ; i&=1 ;i--) {
Push(Sx, i);
printStack(Sx);
Sx,Sy,Sz);
printStack(Sz);
1.1 队列定义&
队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头&(Front)
,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)
队列的基本运算也有六种：
置空队 ：InitQueue(Q)
判队空：&QueueEmpty(Q)
判队满：&QueueFull(Q)
入队 ：&EnQueue(Q,x)
出队 ：&DeQueue(Q)
取队头元素：&QueueFront(Q),不同与出队，队头元素仍然保留。
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
对于顺序队列，我们要理解&假上溢&的现象。
我们现实中的队列比如人群排队买票，队伍中的人是可以一边进去从另一头出来的，除非地方不够，总不会有&溢出&的现象，相似地，当队列中元素完全充满这个向量空间时，再入队自然就会上溢，如果队列中已没有元素，那么再要出队也会下溢。
那么&假上溢&就是怎么回事呢?
因为在这里，我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部)增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却产生了&上溢&现象，这就是假上溢。
为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。
通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少有三种，一种是另设一个布尔变量来判断(就是请别人看着，是空还是满由他说了算)，第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。
2.2 队列的顺序存储
顺序存储如图：
由于是顺序存储结构的存储空间是静态分配的，所以在添加数据的时，有可能没有剩余空间的情况。
解决这种“假溢出”情况，使用循环队列。在c语言中，不能用动态分配的一维数组来实现循环队列。若使用循环队列，必须设置最大队列长度，若无法估计最大长度，就使用链式队列。
// Test.cpp : Defines the entry point for the console application.
#include &stdafx.h&
#include &stdio.h&
#include &stdlib.h&
#include &iostream&
#define TRUE
#define FALSE
#define OK
#define ERROR
#define INFEASIBLE -1
#define OVERFLOW -2
#define QUEUEEMPTY
#define MAX_QUEUE 10 //队列的最大数据元素数目
typedef int S
typedef int ElemT
typedef struct queue{
elem[MAX_QUEUE] ;
///假设当数组只剩下一个单元时认为队满
//队头指针
//队尾指针
/************************************************************************/
各项基本操作算法。
/************************************************************************/
void InitQueue(QUEUE *&Q);
void EnQueue(QUEUE *Q,ElemType elem);
void DeQueue(QUEUE *Q,ElemType *elem);
int QueueEmpty(QUEUE Q);
/************************************************************************/
直接使用结构体指针变量，必须先分配内存地址，即地址的指针
/************************************************************************/
void InitQueue(QUEUE *&Q)
Q = (QUEUE *) malloc (sizeof(QUEUE));
Q-&front = Q-&rear = -1;
/************************************************************************/
/************************************************************************/
void EnQueue(QUEUE *Q, ElemType elem)
if((Q-&rear+1)% MAX_QUEUE == Q-&front) exit(OVERFLOW);
Q-&rear = (Q-&rear + 1)%MAX_QUEUE;
Q-&elem[Q-&rear] =
/************************************************************************/
/************************************************************************/
void DeQueue(QUEUE *Q,ElemType *elem)
if (QueueEmpty(*Q))
exit(QUEUEEMPTY);
Q-&front =
(Q-&front+1) % MAX_QUEUE;
*elem=Q-&elem[Q-&front];
/************************************************************************/
获取队头元素内容
/************************************************************************/
void GetFront(QUEUE Q,ElemType *elem)
if ( QueueEmpty(Q) )
exit(QUEUEEMPTY);
*elem = Q.elem[ (Q.front+1) % MAX_QUEUE ];
/************************************************************************/
判断队列Q是否为空
/************************************************************************/
int QueueEmpty(QUEUE Q)
if(Q.front==Q.rear) return TRUE;
else return FALSE;
void main()
InitQueue( Q);
EnQueue( Q, 1);
EnQueue( Q, 2);
DeQueue( Q,&e);
cout&&&De queue:&&&e;
注意：InitQueue(QUEUE *&Q) 传的是指针的地址。
2.3 链式队列：
// Test.cpp : Defines the entry point for the console application.
#include &stdafx.h&
#include &stdio.h&
#include &stdlib.h&
#include &iostream&
#define TRUE
#define FALSE
#define OK
#define ERROR
#define INFEASIBLE -1
#define OVERFLOW -2
#define QUEUEEMPTY
typedef int S
typedef int ElemT
typedef struct LNode {
//链式队列的结点结构
//队列的数据元素类型
struct LNode *
//指向后继结点的指针
}LNode, *LinkL
typedef struct queue{ //链式队列
//队头指针
//队尾指针
/************************************************************************/
各项基本操作算法。
/************************************************************************/
void InitQueue(QUEUE *Q);
void EnQueue(QUEUE *Q,ElemType elem);
void DeQueue(QUEUE *Q,ElemType *elem);
void GetFront(QUEUE Q,ElemType *elem) ;
bool QueueEmpty(QUEUE Q);
/************************************************************************/
/*初始化队列Q
void InitQueue(QUEUE *Q)
Q-&front = (LinkList)malloc(sizeof(LNode));
if (Q-&front==NULL) exit(ERROR);
Q-&rear= Q-&
void EnQueue(QUEUE *Q,ElemType elem)
s = (LinkList)malloc(sizeof(LNode));
if(!s) exit(ERROR);
s-&next = NULL;
Q-&rear-&next =
void DeQueue(QUEUE *Q,ElemType *elem)
if(QueueEmpty(*Q)) exit(ERROR);
*elem = Q-&front-&next-&
s = Q-&front-&
Q-&front-&next = s-&
/*获取队头元素内容
void GetFront(QUEUE Q,ElemType *elem)
if(QueueEmpty(Q)) exit(ERROR);
*elem = Q.front-&next-&
/*判断队列Q是否为空
bool QueueEmpty(QUEUE Q)
if(Q.front == Q.rear) return TRUE;
return FALSE;
void main()
InitQueue( &Q);
EnQueue( &Q, 1);
EnQueue( &Q, 2);
DeQueue( &Q,&e);
cout&&&De queue:&&&e;
2. 4．队列的应用
【举例1】银行排队
【举例2】模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【举例3】CPU分时系统
在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：5446442次
积分：29731
积分：29731
排名：第145名
原创：216篇
评论：1399条
扫码打赏,你说多少就多少
(1)(2)(3)(2)(4)(2)(1)(2)(1)(1)(2)(1)(1)(1)(1)(1)(2)(2)(1)(2)(3)(3)(2)(2)(2)(4)(3)(2)(15)(6)(8)(14)(29)(26)(27)(18)(7)(8)(6)(2)