栈的基本运算程序

#include<stdlibh>

typedef struct node

{

int num;

struct node next;

}link,LINK;

void empty(link top)

{

top=NULL;

}

int pd(link top)

{

if(top==NULL)

{

return 0;

}

else

{

return 1;

}

}

link create(link top,int n)

{

link s;

s=(link)malloc(sizeof(LINK));//分配时要分配一个结构体的空间，而不是仅仅一个指针的空间。

s->num=n;

s->next=top;

top=s;

return top;

}

/如上个函数，要返回一个指针，否则是不能改变top的值的。因为在函数中只能修改指针指向地址的内容，而它指向的地址是不会改变的。因此要想使指针指向的地址发生变化，要重新返回一个link。出栈的数据放到x中。/

link outword(link top,int x)

{

link p;

if(pd(top)==0)

{

printf("underflow");

return top;

}

else

{

p=top;

x=top->num;

top=top->next;

free(p);

return top;

}

}

void main()

{

link top=NULL;

int n,x=(int)malloc(sizeof(int));

//top=(link)malloc(sizeof(LINK));

//empty(top);

printf("进栈\n");

scanf("%d",&n);

//top->num=n;

while(n!=-1)

{

top=create(top,n);

scanf("%d",&n);

}

printf("出栈\n");

while(pd(top)!=NULL)

{

top=outword(top,x);

printf("%d\n",x);

}

}

已经可以运行。主要问题就是出栈函数的问题，需要你仔细考虑一下。

不正确， 因为前面我们已经提到过，通过继承Vector，很大一部分功能的实现就由Vector涵盖了。Vector的详细实现我们会在后面分析。它实现了很多的辅助方法，给Stack的实现带来很大的便利。现在，我们按照自己的思路来分析每个方法的具体步骤，再和具体实现代码对比。

empty

从我们的思路来说，如果要判断stack是否为空，就需要有一个变量来计算当前栈的长度，如果该变量为0，则表示该栈为空。或者说我们有一个指向栈顶的变量，如果它开始的时候是设置为空的，我们可以认为栈为空。这部分的实现代码也很简单：

在这里，判断是否可以取栈顶元素在peek方法里实现了，也将如果栈为空则抛异常的部分包含在peek方法里面。这里有必要注意的一个细节就是，在通过peek()取到顶端的元素之后，我们需要用removeElementAt()方法将最顶端的元素移除。我们平时可能不太会留意到这一点。

为什么要移除呢？我们反正有一个elementCount来记录栈的长度，不管它不是也可以吗？

实际上，这么做在程序运行的时候会有一个潜在的内存泄露的问题。因为在java里面，如果我们普通定义的类型属于强引用类型。

比如这里vector就底层用的Object[]这个数组强类型来保存数据

。强类型在jvm中做gc的时候，只要程序中有引用到它，它是不会被回收的。这就意味着在这里，只要我们一直在用着stack，那么stack里面所有关联的元素就都别想释放了。这样运行时间一长就会导致内存泄露的问题。那么，为了解决这个问题，这里就是用的removeElementAt()方法。

顺序存储结构

#include<iostream>

typedef char ElemType;

#define MaxSize 100

using namespace std;

typedef struct

{

ElemType data[MaxSize];

int top;

}sqStack;

void InitStack(sqStack &s);//初始化栈

void ClearStack(sqStack &s);//摧毁栈

int StackLength(sqStack s);//返回栈的长度

bool StackEmpty(sqStack s);//判断栈是否为空

int Push(sqStack &s,ElemType e);//进栈

int Pop(sqStack &s,ElemType &e);//出栈

int GetTop(sqStack s,ElemType &e);//取栈顶元素

void DispStack(sqStack s);//显示栈中元素值

int main()

{

return 0;

}

void InitStack(sqStack &s)//初始化栈

{

s=new sqStack;

s->top=-1;

}

void ClearStack(sqStack &s)//摧毁栈

{

delete s;

}

int StackLength(sqStack s)//返回栈的长度

{

return (s->top+1);

}

bool StackEmpty(sqStack s)//判断栈是否为空

{

return (s->top==-1);

}

int Push(sqStack &s,ElemType e)//进栈

{

if(s->top==MaxSize-1)

return 0;

s->top++;

s->data[s->top]=e;

return 1;

}

int Pop(sqStack &s,ElemType &e)//出栈

{

if(s->top==-1)

return 0;

e=s->data[s->top];

s->top--;

return 1;

}

int GetTop(sqStack s,ElemType &e)//取栈顶元素

{

if(s->top==-1)

return 0;

e=s->data[s->top];

return 1;

}

void DispStack(sqStack s)//显示栈中元素值

{

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

cout<<s->data[i]<<" ";

cout<<endl;

}

链式存储结构

typedef char ElemType;

typedef struct linknode

{

ElemType data;

struct linknode next;

}LiStack;

void InitStack(LiStack &s);//初始化栈

void ClearStack(LiStack &s);//摧毁栈

int StackLength(LiStack s);//返回栈的长度

bool StackEmpty(LiStack s);//判断栈是否为空

void Push(LiStack &s,ElemType e);//进栈

int Pop(LiStack &s,ElemType &e);//出栈

int GetTop(LiStack s,ElemType &e);//取栈顶元素

void DispStack(LiStack s);//显示栈中元素值

int main()

{

return 0;

}

void InitStack(LiStack &s)//初始化栈

{

s=new LiStack;

s->next=NULL;

}

void ClearStack(LiStack &s)//摧毁栈

{

for(LiStack p=s->next;p;p=p->next)

{

delete s;

s=p;

p=p->next;

}

delete s;

}

int StackLength(LiStack s)//返回栈的长度

{

int i=0;

for(LiStack p=s->next;p;p=p->next)

i++;

return i;

}

bool StackEmpty(LiStack s)//判断栈是否为空

{

return (s->next==NULL);

}

void Push(LiStack &s,ElemType e)//进栈

{

LiStack p=new LiStack;

p->data=e;

p->next=s->next;

s->next=p;

}

int Pop(LiStack &s,ElemType &e)//出栈

{

LiStack p;

if(s->next==NULL)

return 0;

p=s->next;

e=p->data;

s->next=p->next;

delete p;

return 1;

}

int GetTop(LiStack s,ElemType &e)//取栈顶元素

{

if(s->next==NULL)

return 0;

e=s->next->data;

return 1;

}

void DispStack(LiStack s)//显示栈中元素值

{

LiStack p=s->next;

for(;p;p=p->next)

cout<<p->data<<" ";

cout<<endl;

}

push 1--1

push 2--2

pop 2--1

push 3--2

pop 3--1

pop 1--0

push 4--1

pop 4--0

此时栈的最短长度（上面右边数字最大者）为 2

#include

#include

#define Max 100

typedef char T;

typedef struct MyStack

{

T aa[Max];

unsigned int p;

} stack;

//创建空栈

stack createEmptyStack()

{

stack st = (stack )malloc(sizeof(stack));

int i=0;

for(i=0;i<Max;i++)

st->aa[i]=0;

st->p=0;

return st;

};

//栈判空

int isEmpty(const stack st)

{

if(st->p==0) return 1;

else return 0;

};

//求栈的大小

unsigned int size(const stack st)

{

return st->p;

};

//push *** 作

void push(stack st,const T a)

{

st->p=st->p+1;

if(st->p==Max)

{

printf("栈满\n");

st->p--;

return;

}

st->aa[st->p]=a;

};

//pop *** 作

T pop(stack st)

{

if(isEmpty(st))

{

printf("栈空");

return NULL;

}

char t=st->aa[st->p];

st->p=st->p-1;

printf("%c ",t);

return t;

};

//栈销毁

void destroy(stack st)

{

free(st);

};

int main()

{

stack st = createEmptyStack();

if(isEmpty(st)) printf("MyStack is empty\n");

else printf("MyStack is not empty\n");

push(st,'a');

push(st,'b');

push(st,'c');

push(st,'d');

push(st,'e');

printf("%d\n",size(st));

while(!isEmpty(st)) pop(st);

destroy(st);

system("pause");

return 0;

}

有错误。

StackEmpty 方法中，sbase = stop 需改为 sbase == stop。

Push 方法中，stop - sbase == sstacksize 需改为 stop - sbase == sstacksize - 1。

Pop 方法中，stop = sbase 需改为 stop == sbase。

main 方法中，else printf("栈初始化失败\n"); 需改为 else { printf("栈初始化失败\n"); return 1;} 栈初始化失败了，后面所有代码都不要执行了。

#include <stdioh>

#define MAXSIZE 100

typedef char SElemType;

typedef struct {

  SElemType  base; //栈底指针

  SElemType  top; //栈顶指针

  int stacksize; //栈可用最大容量

}

SqStack;

//初始化

int InitStack(SqStack & s) {

  sbase = new SElemType[MAXSIZE];

  if (!sbase) {

    return 0;

  }

  stop = sbase;

  sstacksize = MAXSIZE;

  return 1;

}

//判断栈是否为空

int StackEmpty(SqStack s) {

  return sbase == stop  1 : 0;

}

//求栈长度

int StackLength(SqStack s) {

  return stop - sbase;

}

//进栈

int Push(SqStack & s, SElemType e) {

  if (stop - sbase == sstacksize - 1) {

    return 0;

  }

   stop++ = e;

  return 1;

}

//出栈

int Pop(SqStack & s, SElemType & e) {

  if (stop == sbase) {

    return 0;

  }

  e =  --stop;

  return 1;

}

int main() {

  SqStack s;

  SElemType e;

  if (InitStack(s)) {

    printf("栈初始化完毕\n");

  } else {

    printf("栈初始化失败\n");

    return 1;

  }

  if (StackEmpty(s)) {

    printf("栈为空\n");

  } else {

    printf("栈不为空\n");

  }

  printf("栈的长度为：%d\n", StackLength(s));

  scanf("%c", & e);

  if (Push(s, e)) {

    printf("%c已进栈\n", e);

  } else {

    printf("%c进栈失败\n", e);

  }

  printf("栈的长度为：%d\n", StackLength(s));

  if (Pop(s, e)) {

    printf("%c已出栈\n", e);

  } else {

    printf("栈为空\n");

  }

  

  printf("栈的长度为：%d\n", StackLength(s));

  return 0;

}

/程序错误太多/ #include"stdioh"

#include"stdlibh"

#include"timeh"

#include"malloch"

#define

STACK_INIT_SIZE

10

//栈容量 typedef

struct

SqStack

{

int

top;

//栈顶当前指针

int

base;

//栈空间数组

}SqStack; void

InitStack(SqStack

&S);

//构造空栈S

int

Push(SqStack

&S,int

e);

//入栈（栈地址，入栈数据）

返回0对，-1错

int

Pop(SqStack

&S);

//出栈

（栈地址）返回栈顶数据

int

StackLength(SqStack

S);

//返回站的元素个数，即求栈长

void

Print_S(SqStack

S);

//显示栈内数据 int

main()

{

SqStack

S;

int

i=0;

int

a,e;

InitStack(S);

srand((unsigned)time(NULL));

//srand((unsigned)time(NULL))以time函数值(当前时间)作为种子

printf("随机填充5个元素为:

");

while(

i<5)

{

a

=

rand()%100;

printf("%d

",

a);

Push(S,a);

i++;

}

Print_S(S);

printf("请输入要插入栈顶的元素:");

scanf("%d",&e);

Push(S,e);

Print_S(S);

printf("再d出的栈顶元素为:%d

\n",Pop(S));

printf("栈的长度为:%d

\n",StackLength(S));

Print_S(S);

return

0;

} void

InitStack(SqStack

&S)

//构造空栈S

{

Sbase

=

(int

)malloc(STACK_INIT_SIZE

sizeof(int));

//分配组数空间，长度STACK_INIT_SIZE

if

(Sbase==NULL)

{

printf("内存分配失败!\n");

return;

}

Stop=-1;

} int

Push(SqStack

&S,int

e)

{

if(Stop>=STACK_INIT_SIZE)

{

printf("栈空间已满，入栈失败!\n");

return

-1;

}

else

{

Sbase[++Stop]=e;

return

0;

}

} int

Pop(SqStack

&S)

//返回栈顶数据

{

if

(Stop>=0)

//栈内有数据

{

return

Sbase[Stop--];

}

else

{

printf("空栈，无数据d出!\n");

return

-1;

}

} int

StackLength(SqStack

S)

{

return

Stop+1;

} void

Print_S(SqStack

S)

{

printf("\n出栈显示：");

if(Stop

==

-1)

printf("栈内无数据!\n");

else

{

while(Stop>=0

)

printf("%d

",Pop(S));

putchar('\n');

}

}

s->top-s->base没有什么意义的，只不过是将当前的栈顶地址减去栈底地址，得到一个地址的差值而已

stacksize这个成员是干什么的，应该就是栈的长度吧

如果是，那么stacksize就是你要的栈的长度

如果不是，那它应该是栈成员的个数，那么stacksizesizeof(int)就是你要的栈的长度

问题补充：那这样的话 要返回栈中此时的长度岂不是很难实现

难道还要必须在

typedef struct

{

int base;

int top;

int length;//

int stacksize;

}

这样么？

对的。

给你一个例子(不太全，但是经典)：

# include<stdlibh>

# include<stdioh>

# define STACK_INIT_SIZE 200

# define STACK_INCREMENT 20

# define OVERFLOW 0

# define OK 1

//

/The struct of sequence stack /

//

struct SqStack

{

int base;/the base pointer of the sequence stack/

int top;/the top pointer of the sequence stack/

int stacksize;/the size of the sequence stack/

int length;/the total number of the elements in the stack/

}S;

//

/Initial the stack/

//

InitStack(struct SqStack S)

{

S->base=S->top=(int )malloc(STACK_INIT_SIZEsizeof(int));

if (!S->base && !S->top) exit(OVERFLOW);

S->stacksize = STACK_INIT_SIZE;

S->length = 0;

printf("Initial the sequence stack successfully!\n");

}

//

/Push a element into the stack/

//

StackPush(struct SqStack S,int elm)

{

if(S->length >= S->stacksize)

{

S->base = (int )realloc(S->base,(S->stacksize+STACK_INCREMENT)(sizeof(int)));

if (!S->base) exit(OVERFLOW);

S->top = S->base+S->length;

S->stacksize += STACK_INCREMENT;

}

if (S->length == 0)

{

(S->base) = elm;

S->top ++;

S->length ++;

printf("The new element %d was pushed into the Stack successfully!\n",elm);

}

else

{

(S->top) = elm;

S->top++;

S->length++;

printf("The new element %d was pushed into the Stack successfully!\n",elm);

}

}

//

/Pop the element at the top in the stack/

//

StackPop(struct SqStack S)

{

int PopElm;

PopElm = (S->top-1);

if (S->length == 0)

{

printf("The stack now is empty,you can not pop again!\n");

}

if (S->length == 1)

{

S->top--;

(S->top)=(S->base)=NULL;

S->length--;

printf("Pop the element %d successfully!\n",PopElm);

}

else

{

S->top--;

(S->top)=NULL;

S->length--;

printf("Pop the element %d successfully!\n",PopElm);

}

}

//

/Judge the stack is empty or not/

//

StackEmpty(struct SqStack S)

{

if (S->length==0)

{

printf("The stack now is empty!\n");

}

else

{

printf("The stack now is not empty!\n");

PrintStack(S);

}

}

//

/Get the length of the stack/

//

StackLength(struct SqStack S)

{

printf("The length of current stack is %d\n",S->length);

}

//

/Destroy the stack and free the memory distributed at first/

//

DestroyStack(struct SqStack S)

{

free(S->base);

free(S->top);

S->length = 0;

printf("Destroy the stack successfully!\n");

}

//

/Clear all the elements in the stack/

//

ClearStack(struct SqStack S)

{

int p,count =0;

p = S->base;

while(1)

{

if (count == S->length) break;

p =NULL;

p++;

}

S->length = 0;

S->top=S->base;

printf("Clear the stack successfully!\n");

}

//

/Get the element at tbe location i /

//

GetElement(struct SqStack S,int i)

{

int p,count = 1;

p = S->base;

if (i<=0 || i>S->length)

{

printf("The location %d you input not valid!\n",i);

}

else

{

while (1)

{

if (count == i) break;

p++;

count++;

}

printf("The element at the location %d is %d\n",i,p);

}

}

//

/Find a number if or not in the stack/

//

FindElement(struct SqStack S,int elm)

{

int p,count=0,totalFind=0;

p = S->base;

while (1)

{

if(count == S->length) break;

if (p == elm)

{

totalFind++;

printf("We find %d at the location of %d in the stack!\n",elm,count+1);

}

p++;

count++;

}

if (totalFind ==0)

{

printf("We can not find %d in the stack!\n",elm);

}

else

{

printf("We totally find %d <%d> in the stack\n",elm,totalFind);

}

}

以上就是关于栈的基本运算程序全部的内容，包括:栈的基本运算程序、求栈中元素个数（StackLength）的两个算法那个正确、分别就栈的顺序存储结构和链式存储结构实现栈的各种基本 *** 作。等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！