欢迎来到军工软件开发人才培养基地——学到牛牛

数据结构之栈

时间:2024-05-06 07:01:10 来源:学到牛牛

 

1.简介

栈(stack)又名堆栈,它是一种访问受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。故栈又称为先进后出(FILO—first in last out)线性表。

 

 

栈包含的基本操作:

1.入栈操作:在栈顶插入数据

2.出栈操作:在栈顶删除数据

3.栈中没有元素时,称为空栈

4.栈中存储达到预定上限,称为满栈

栈可以使用数组或链表作为物理存储结构,使用数组实现的队列称为顺序栈,使用链表实现的队列称为链式栈。本文针对最常用的顺序栈进行代码实现。

2.顺序栈

顺序栈的实现依赖数组作为底层物理存储结构,其特点是内存连续,并且数组的大小一般在初始时固定(如果使用动态内存可以修改)。

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

 

struct Stack {

int* buf;

int top;

int maxSize;

};

 

// 栈初始化

void init(struct Stack* st, int size)

{

st->top = 0;

st->maxSize = size;

st->buf = (int*)malloc(sizeof(int) * size);

}

 

// 栈内存释放

void destroy(struct Stack* st)

{

free(st->buf);

st->buf = NULL;

}

// 遍历栈

void display(struct Stack* st)

{

printf("stack size = %d, val = ", st->top);

int i = 0;

while (i < st->top) {

printf("%d ", st->buf[i]);

i++;

}

printf("\n");

}

// 判断栈是否为满

int isfull(struct Stack* st)

{

return st->top == st->maxSize;

}

// 判断栈是否为空

int isempty(struct Stack* st)

{

return st->top == 0;

}

// 入栈

int push(struct Stack* st, int val)

{

if (isfull(st)) {  // 栈满,无法入栈,返回-1

return -1;

}

st->buf[st->top] = val;

return st->top++; // 返回入栈的位置

}

// 出栈

int pop(struct Stack* st)

{

if (isempty(st)) {

return -1;

}

return --st->top;

}

 

// 栈空:返回-1; 栈不空:返回0,pval执行的变量存储获取的栈顶元素

int getTop( struct Stack *st, int *pval )

{

if( isempty( st ) ){

return -1;   // 无栈顶元素

}

*pval = st->buf[st->top - 1];

return 0;

}

 

int main()

{

struct Stack stack;

init(&stack, 5);

display(&stack);

push(&stack, 10);

push(&stack, 20);

push(&stack, 30);

push(&stack, 40);

push(&stack, 50);

display(&stack);

printf("push ret = %d\n", push(&stack, 70));   // 栈满,无法入栈,返回-1

pop(&stack);

pop(&stack);

display(&stack);

printf("push ret = %d\n", push(&stack, 70));

display(&stack);

destroy(&stack);

return 0;

}