堆栈问题详解介绍
堆栈是一种执行“后进先出”算法的数据结构。堆栈
堆栈是一种执行“后进先出”算法的数据结构。
设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球，小球的直径比竹筒的直径略校现在把不同编号的小球放到竹筒里面，可以发现一种规律：先放进去的小球只能后拿出来，反之，后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的特点。
堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域，数据一个一个顺序地存入（也就是“压入——push”）这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元，存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。数据一个一个地存入，这个过程叫做“压栈”。在压栈的过程中，每有一个数据压入堆栈，就放在和前一个单元相连的后面一个单元中，堆栈指示器中的地址自动加1。读取这些数据时，按照堆栈指示器中的地址读取数据，堆栈指示器中的地址数自动减 1。这个过程叫做“弹出pop”。如此就实现了后进先出的原则。
堆栈是计算机中最常用的一种数据结构，比如函数的调用在计算机中是用堆栈实现的。
堆栈可以用数组存储，也可以用以后会介绍的链表存储。
下面是一个堆栈的结构体定义，包括一个栈顶指针，一个数据项数组。栈顶指针最开始指向-1,然后存入数据时，栈顶指针加1，取出数据后，栈顶指针减1。
#define MAX_SIZE 100
typedef int DATA_TYPE;
struct stack
{
DATA_TYPE data[MAX_SIZE];
int top;
};
empty()函数是将堆栈清空的函数，push()函数是压入堆栈的函数，pop()函数是将数据取出的函数。peek()函数是读栈顶元素的函数。
isEmpty()是判断堆栈是否为空的函数,为空则返回真,否则返回假.
其中DATA_TYPE是堆栈中数据的类型,依据你的问题而定义.比如如果堆栈中存入char型元素,那就定义typedef char DATA_TYPE
typedef int BOOL是在定义一个类似逻辑类型的数据类型,由于c语言中没有逻辑类型, 而且
以下是堆栈全部程序：
#include<stdio.h>
#define MAX_SIZE 100
#define TRUE 1
#define FALSE 0
typedef int DATA_TYPE;
typedef int BOOL;
struct stack
{
DATA_TYPE data[MAX_SIZE];
int top;
};
DATA_TYPE peek(struct stack *sta)
{
return (*sta).data[(*sta).top];
}
void empty(struct stack *sta)
{
(*sta).top = -1;
}
BOOL isEmpty(struct stack *sta)
{
if((*sta).top == -1)
return TRUE;
else
return FALSE;
}
void push(struct stack *sta,DATA_TYPE data)
{
if((*sta).top==MAX_SIZE-1)
printf("堆栈已经满n");
else
(*sta).data[++(*sta).top] = data;
}
DATA_TYPE pop(struct stack *sta)
{
if((*sta).top == -1)
{
printf("堆栈已经空了n");
return -1;
}
else
return (*sta).data[(*sta).top--];
}
void main()
{
struct stack st;
empty(&st);
push(&st,3);
push(&st,5);
push(&st,7);
printf("%dn",pop(&st));
printf("%dn",pop(&st));
printf("%dn",pop(&st));
}
思考题：
堆栈通常用于解析某字符串.请用堆栈来检查某字符串中的括号是否匹配,如果不匹配,输出该不匹配的位置.
比如字符串:a{b(c[d]e)f}就是匹配的,而{99]就是不匹配的.
思路:从字符串中从左到右读取字符,每次读取一个字符,如果发现它是左括号(是"[{("中的一个),就压入堆栈中.当从输入中读到右分隔符(是")}]"中的一个)时,就弹出栈顶的左分隔符,看一看是否匹配,如果它们不匹配(如一个是小括号,另一个是中括号),就报错,输出错误的列是几.如果读到末尾,还一直存在没有被匹配的分隔符,程序也报错.分隔符没有被匹配,表现为把整个字符串都读入后,堆栈中仍有分隔符.
本文地址：http://www.45fan.com/a/question/70511.html