数据结构之栈和队列




数据结构学习继续向前推进,之前对线性表进行了学习,现在我们进入栈和队列的学习。同样我们先学习一些基本概念以及堆栈的ADT.

栈和队列是两种中重要的线性结构。从数据结构角度看,栈和队列也是线性表,只不过是受限的线性表。因此可以称为限定性数据结构。但从数据类型来看,他们是和线性表大不相同的两类重要的抽象数据类型。

栈:(stack)是限定仅在表尾进行相应插入和删除操作的线性表。因此,对栈来说,表尾有其特殊含义,称为栈顶,表头称为栈底,不含元素的空表称为空栈。栈一个重要特性就是后进先出.OK,我们来看一下栈的结构:





ADT Stack

{

数据对象:D = {ai| ai属于ElemSet,i = 1,2,……,n, n >= 0 }

约定an端为栈顶,a1端为栈底。

基本操作:

Status Init_SeqStack(SeqStack *s)

初始化栈,构造一个空栈。

Status Destory(SeqStack *s)

摧毁栈

Status Clear(SeqStack *s)

清空栈

int IsEmpty(SeqStack *s)

判断是否为空栈,是空栈返回1,不是空栈返回0

int IsFull(SeqStack *s )

判断栈是否满,栈满返回1,没有满返回0

int  GetLength(SeqStack s)

返回栈中元素的个数

Status PushStack(SeqStack *s,ElemType x)

插入元素e为新的栈顶元素

Status GetTop(SeqStack *s,ElemType *value)

获取栈顶元素,用value带回

Status  PopStack(SeqStack *s)

删除栈顶元素

Status Show_Stack(SeqStack s)

打印输出栈中元素

}




以上就是栈的抽象数据类型,好了我们接下来用C语言实现栈结构,既然栈受限的线性表,线性表有链式存储结构和顺序存储结构,那么栈也同样有两种,顺序栈和链栈。依然沿袭过去先弄清结构再通过代码解释。开篇已经讲了栈是受限的线性表,那么我们就要类比着看栈的操作:顺序栈,就类比顺序表。链栈就类比单链表。ok,我们先来看顺序栈:




顺序栈



顺序栈,即就是栈的顺序存储结构,是利用一组连续的存储单元一次依次存放自栈底到栈顶的数据元素,同时附设top指示栈顶元素在顺序表中的位置,通常的习惯做法以top=0表示空栈,鉴于以C语言作为描述语言时,如此设定会带来很大不便;另一方面,由于栈在使用过程中所需的最大空间大小无法估计。因此一般来说,先为初始化空栈时不应设定栈的最大空间容量。一个较合理的做法是:先为栈分配一个基本容量,然后在应用过程中,当栈的空间不够时再逐段扩大。为此,可以设定两个常 STACK_INIT_SIZE(存储空间初始分配量)和STACK_INC_SIZE(存储空间分配增量)



 ok我们先定义顺序栈的结构:



#define ElemType char

#define Status    int

#define FALSE     0

#define TRUE      1

#define STACK_INIT_SIZE  8               存储空间初始分配量

#define STACK_INC_SIZE   20              存储空间分配增量

typedef struct  SeqStack

{

ElemType *bace;

int capacity;

int top;

}SeqStack;




//判断是否为空栈,栈结构中的top也就记录了顺序栈中的状态,栈空返回1,非空返回0

int  IsEmpty(SeqStack *s)

{

return s->top == 0;

}

//判断是否栈满,栈满返回1,非满返回0

int  IsFull(SeqStack *s )

{

return s->top >= s->capacity;

}



//此函数解决,上面提到的,当基空间不够时,增加空间。增加成功放回TRUE,也就是1,增加失败返回FALSE

Status IncSize(SeqStack *s)

{

ElemType *newbase = (ElemType *)realloc(s->bace,sizeof(ElemType) * (s->capacity + STACK_INC_SIZE));

if(NULL == newbase)

{

printf("out of memory\n");

return FALSE;

}

s->bace = newbase;

s->capacity += STACK_INC_SIZE;

return TRUE;

}





顺序栈的初始化



//初始化栈,就是为栈分配一个基空间,修改结构中top让其等于0,表示空栈。

//初始化成功返回TRUE,初始化失败返回FALSE;

Status Init_SeqStack(SeqStack *s)

{

s->bace = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);

if(NULL == s->bace )

{

printf("out of memory,filed Init_SeqStack\n");

return FALSE;

}

s->top = 0;

s->capacity = STACK_INIT_SIZE;

return TRUE;

}




   顺序栈的压栈出栈



这里一直强调栈是受限的线性表,那么,初始化,等其他的基本类同,主要区别就是在栈中的压栈和出栈,压栈出栈,对顺序栈就是对顺序表的尾插、尾删,ok我们继续用图理一下结构。





//入栈(压栈)成功返回TRUE,失败返回FALSE

Status PushStack(SeqStack *s,ElemType x)

{

/*

这里就是解决栈的基空间不够会满的情况,需要调用前边定义的函数再次为其增加空间。这里的

if条件需要注意,IsFull(s) 函数,当栈已满是返回1结果为真,IncSize(s)函数返回值,当开辟

成功后返回1结果为真,所以当开辟成功后取反就为价所以&&操作后为假,if模块就不执

行了,就继续执行后边的代码模块

*/

if(IsFull(s) && !IncSize(s))

{

printf("栈空间已满,%d不能入栈\n",x);

return FALSE;

}

s->bace[s->top++] = x;

//s->top++;                         简化代码

return TRUE;

}

//出栈

Status  PopStack(SeqStack *s)

{

if(IsEmpty(s))

{

printf("栈已空,不能出栈\n");

return FALSE;

}

s->top--;

return TRUE;

}




顺序栈的获取栈顶元素



继续看上一张图,中的那段话,在C语言中,由于数组下标是从0开始的,top中保存栈中元素个数,所以base[top]是指向栈顶元素的上一个空间,所以获取栈顶元素时就需要减去1.



//获取栈顶元素,

Status GetTop(SeqStack *s,ElemType *value)

{

if(IsEmpty(s))

{

printf("栈空间已空,不能取栈顶元素\n");

return FALSE;

}

*value = s->bace[s->top - 1];

return TRUE;

}




顺序栈的的长度



top中保存的就是栈中的元素个数,所以获取栈中元素个数直接返回top的值就可以。

//获取栈长度

int  GetLength(SeqStack s)

{

return s.top;

}




顺序栈的清空栈



//清空栈,清空栈就是让栈为空,所以只需要把top修改为0即可。

Status Clear(SeqStack *s)

{

s->top = 0;

return TRUE;

}




顺序栈的摧毁栈




//摧毁栈,摧毁栈,意味着,不仅要top修改为0,更要释放掉栈的空间。

Status Destory(SeqStack *s)

{

free(s->bace);

s->bace = NULL;

s->top = 0;

return TRUE;

}




顺序栈的输出




//输出栈中的元素,既然栈是从栈顶出,那么全部打印的输出的时候,就需要从数组的尾输出。

Status Show_Stack(SeqStack s)

{

if(s.top == 0)

{

printf("栈已空\n");

return FALSE;

}

for(int i = s.top-1; i >= 0; i--)

{

printf("%d",s.bace[i]);

}

printf("\n");

return TRUE;

}




顺序栈的操作的基本操作就总结到这里,我们接着看栈的另一种存储结构——链栈。




栈之链栈



链栈也是栈,所以就不在介绍它的ADT,我们直接看链栈的结构。顺序栈我们类比顺序表,那么链栈我们类比链表,链表的种类那么多,我们选用那种呢?看栈的定义,我们不难得出是单链表,至于是带头结点还是不带头结点,由于栈操作是从栈顶操作也就是线性表的表尾,所以这里也不用考虑带头结点或者不带头结点,都一样,也就不需要用带头结点了。

之前说顺序栈的时候我们谈到,栈会满,我们采用了一种结构处理这种情况,为其增开辟空间,解决栈满的情况。那么对于链栈,只要内存不满,就可以一直压栈存储元素。(系统内存耗尽除外,当发生这种情况时,系统已经瘫痪,所以程序的崩溃也已经无所谓了。),所以也不需要顺序栈中判断栈是否为满的情况这个函数。

ok我们继续先看一下链栈的结构和结构定义:




栈的结构





#define ElemType int

#define TRUE     1

#define FALSE    0

#define Status   int

typedef struct StackNode

{

ElemType data;

struct StackNode *next;

}StackNode;

typedef StackNode* LinkStack;    // 这里需要注意后边LinkStack  定义的变量就是指针类型的。

Status InitLinkStack(LinkStack *ls)

{

*ls = NULL;

return TRUE;

}




 链栈的压栈出栈




顺序栈时已经说过,压栈出栈对于栈是最重要的结构,那么其他操作类比一下不带头结点单链表的操作,OK,压栈就是对不带头结点的头插,头插!对就是头插,不再是顺序表中说的尾插,没有搞错,我们退回去看链栈的结构图,当插入元素时,指向栈顶的指针指向新的元素,那么当通过指向栈顶的指针访问链表的时候,不就是后进先出,不就是符合栈的定义吗?其实顺序表也一定意义上头插,我们通过栈顶看,不就是头插吗?说顺序栈是尾插,是由于顺序栈是通过数组实现的,数组名是指向数组的第一个元素的,我们要通过数组名操作存储数据,所以才说是尾插。我们继续看结构图:





结构弄清了链栈的压栈只是一个没有不带头结点的头插;ok我们看具体C语言代码实现:



压栈



//压栈,压栈成功返回TRUE,失败返回FALSE; 

Status PushStack(LinkStack *ls,ElemType x)

{

StackNode  *s = (StackNode *)malloc(sizeof(StackNode));

if(NULL == s)

{

printf("out of memory\n");

return FALSE;

}

s->data = x;

if(NULL == *ls)

{

*ls = s;

s->next = NULL;

}

else

{

s->next = *ls;

*ls = s;

}

return TRUE;

}



出栈



对于链栈的出栈要注意释放结点空间,防止内存泄露



//出栈,出栈成功返回TRUE,失败返回FALSE

Status PopLinkStack(LinkStack *ls)

{

StackNode *p = *ls;

if(NULL == p)

{

printf("栈已空,出栈失败\n");

return FALSE;

}

*ls = p->next;

free(p);

p = NULL;

return TRUE;

}   




链栈的清空



    这里由于不带头结点,所以这里只给出了清空链栈的操作,但是,需要强调意义不一样。



//清空链表,清空成功返回TRUE,失败返回FALSE

Status ClearLinkStack(LinkStack *ls)

{

StackNode *p = *ls;

while(NULL != p)

{

*ls = p->next;

free(p);

p = *ls;

}

*ls = NULL;

return TRUE;

}




链栈的获取栈顶元素



//获取栈顶元素,即就是栈不空的条件下,获取栈的首元素。

Status GetTop(LinkStack *ls,ElemType *value)

{

StackNode *p = *ls;

if(NULL == p)

{

printf("栈已空,获取栈顶元素失败\n");

return FALSE;

}

*value = p->data;

return TRUE;

}





链栈的获取栈的长度



    链栈不像顺序栈,通过top可以直接获得栈中元素个数,需要遍历所以元素统计栈的元素个数。



//获取链表长度

int  GetLength(LinkStack *ls)

{

StackNode *p = *ls;

int length = 0;

while(NULL != p)

{

length++;

p = p->next;

}

return p;

}




链栈的输出



Status  Show_LinkStack(LinkStack *s)

{

StackNode *p = *s;

if(NULL == s)

{

printf("栈已空\n");

return FALSE;

}

while(NULL != p->next)

{

printf("%d  ",p->data);

p = p->next;

}

printf("\n");

}




ok栈的基本操作就总结到这里,写道这里线性表,栈的基本操作我们都讲完了,会有人说,堆,线性表就只能进行这些基本操作吗?那岂不是很没有用,下一篇我将对线性表的应用简单总结一下。



时间: 05-09

数据结构之栈和队列的相关文章

【数据结构】栈和队列

栈和队列 容器数据结构是指一些包含了若干个其他相同或不同的数据结构的数据结构,被包含的这些每一个独立的数据结构都被称为一个元素,在一个容器中的元素往往支持相同的操作,具有类似的性质.之前说到过的线性表其实就是一种容器数据结构,本文中介绍的两种最常用的容器数据结构是栈和队列. 从功能上看,栈和队列大多用于计算过程中保存临时数据,这些数据是在计算过程中发现或产生的.在而后的计算中可能会用到这些数据.如果这些数据是固定的个数以及大小的话,可以构建几个变量来储存它们,但是如果这些数据不确定的话,就需要一

二、数据结构之栈、队列、循环队列

二.数据结构之栈.队列.循环队列 顺序栈 Stack.h 结构类型,函数声明: #ifndef _STACK_H_ #define _STACK_H_ typedef int SElementType; ///顺序栈 #define STACK_INIT_SIZE 20 #define STACK_INCREMENT 10 typedef struct { SElementType * base; SElementType * top; int stackSize;///当前栈的大小 }SqSt

数据结构之栈与队列

数据结构的有一个重要结构栈,栈这种数据结构就是满足先进后出的这种规则的数据结构就是栈,引用<大话数据结构>中的一个形象例子就是,子弹的弹夹,最先压入弹夹的子弹最后一个出弹夹,正好往一个栈里添加一个元素叫压栈.入栈,从栈里出来一个元素叫弹栈,出栈.指示器就叫栈帧. 栈图 现在就贴上代码: 栈的几个基本操作: #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node{

数组拷贝、数组函数、通过数组函数来模拟数据结构的栈和队列、回调的意义、数组函数的排序问题、算法以及寻找素数的筛选法

1.数组的拷贝数组拷贝时指针的指向问题. 数组在拷贝时,指针的位置随之复制[这一点拷贝是完全一样]但是如果拷贝的数组的指针是非法的,那么拷贝出新指针的位置进行初始化<?php$arr1=array('123');end($arr1);next($arr1);//这个指针非法$arr2 = $arr1;//这里进行数组的拷贝var_dump(current($arr2));//得到指向‘123’元素的指针var_dump(current($arr1));//此时这个数组的指针有问题?> 但是拷贝

[ACM训练] 算法初级 之 数据结构 之 栈stack+队列queue (基础+进阶+POJ 2442+1442)

再次面对像栈和队列这样的相当基础的数据结构的学习,应该从多个方面,多维度去学习. 首先,这两个数据结构都是比较常用的,在标准库中都有对应的结构能够直接使用,所以第一个阶段应该是先学习直接来使用,下一个阶段再去探究具体的实现,以及对基本结构的改造! C++标准库中 这里记录一个经典的关于栈和队列的面试题目: 题目:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法.要保证这三个方法的时间复杂度都是O(1). 思路:重点是getMin()函数的设计,普通思路是设计一

浅谈数据结构系列 栈和队列

计算机程序离不开算法和数据结构,在数据结构算法应用中,栈和队列应用你比较广泛,因为两者在数据存放和读取方面效率比较高,本章节重点讲解两者的基本概念和实现. 基本概念 栈:是一种先进后出,后进先出的数据结构,本质上是线性表,只是限制仅允许在表的一段进行插入和删除工作.此端为栈顶,这是在栈中应用很关键的概念.所有数据的处理都是在栈顶进行的,进栈时,栈中元素增加,栈顶上移一位,出栈时栈顶下移一位.应用中比如:洗碗,每次洗干净的碗放在上面-进栈,取碗,从顶上取出一个-出栈:装子弹-进栈,开枪-出栈. 队

数据结构入门——栈与队列

栈与队列是两种重要的数据结构,有着广泛的应用,他们可以通过对链表功能加以限制改造而来.栈是一种先进后出(FILO)的数据结构,只能在一头进行加入删除,而队列是一种先进先出(FIFO)的数据结构,一头只能加入,另一头只能删除. 栈的实现: # include <stdio.h> # include <malloc.h> # include <stdlib.h> typedef struct Node { int data; struct Node * pNext; }NO

python——python数据结构之栈、队列的实现

这个在官网中list支持,有实现. 补充一下栈,队列的特性: 1.栈(stacks)是一种只能通过访问其一端来实现数据存储与检索的线性数据结构,具有后进先出(last in first out,LIFO)的特征 2.队列(queue)是一种具有先进先出特征的线性数据结构,元素的增加只能在一端进行,元素的删除只能在另一端进行.能够增加元素的队列一端称为队尾,可以删除元素的队列一端则称为队首. 地址在 http://docs.python.org/2/tutorial/datastructures.

数据结构之栈和队列及其Java实现

栈和队列是数据结构中非常常见又非常基础的线性表,在某些场合栈和队列使用很多,因此本篇主要介绍栈和队列,并用Java实现基本的栈和队列,同时用两个栈实现队列和用两个队列实现栈. 栈:栈是一种基于"后进先出"策略的线性表.在插入时(入栈),最先插入的元素在栈尾,最后插入的元素在栈顶:在删除时(出栈),最后插入的元素先出栈,最先插入的元素最后出栈.由此可见,对栈的插入和删除操作都是在栈顶位置进行的. 在Java中,提供了一个类Stack<E>来实现栈的这些特性,并提供了一些常用的