栈基本操作

栈和队列的基本操

作是线性表操作的子集，是限定性（操作受限制）的数据结构。第三章栈和队列

数

据

结

构

之

栈

和

队

列

23. 1 栈

¾定义：是限定仅在表尾进行插入或删除操作

的线性表。(后进先出线性表LIFO)

¾栈底指针(base) :是线性表的基址；

¾栈顶指针(top):指向线性表最后一个元素的后面。

¾当top=base 时，为空栈。

¾基本操作：

InitStack(&S), DestroyStack(&S),

StackEmpty(S) , ClearStack(&S),

GetTop(S ,&e), StackLength(S) ,

Push(&S, e): 完成在表尾插入一个元素e.

Pop(&S,&e): 完成在表尾删除一个元素。

数

据结构之栈

和

队

列

3¾栈的表示和实现

¾顺序栈：是利用一组地址连续的存储单元

依次存放自栈底到栈顶的数据元素；栈满

之后，可再追加栈空间即为动态栈。

¾顺序栈的结构类型定义：

typedef int SElemType;

typedef struct{

SElemType *base; /* 栈底指针*/

SElemType *top; /* 栈顶指针*/

int stacksize; /* 栈空间大小*/

}SqStack;

数

据

结

构

之

栈

和

队

列

4¾基本算法描述

¾建立能存放50个栈元素的空栈

#define STACK_INIT_SIZE 50

#define STACKINCREMENT 10

Status InitStack_Sq(Stack &S){

S.base=(SET*)malloc(STACK_INIT_SIZE

*sizeof(SET)); /*为栈分配空间*/

if(S.base==NULL)

exit(OVERFLOW); /*存储分配失败*/

S.top=S.base;

S.stacksize = STACK_INIT_SIZE;

return OK; }

数

据结构之栈

和

队

列

5¾出栈操作算法

void pop(Sqstacks,SElemTypee)

不带头结点的链栈的基本操作

不带头结点的链栈是一种常见的数据结构，具有一些基本操作，包括入栈、出栈、获取栈顶元素和判断栈是否为空。下面将详细介绍这些基本操作。

1. 入栈操作

入栈操作是将一个元素添加到链栈的栈顶。具体步骤如下：

（1）创建一个新节点，将要入栈的元素存储在该节点中。

（2）将新节点的next指针指向当前栈顶节点。

（3）将新节点设为新的栈顶节点。

2. 出栈操作

出栈操作是将链栈的栈顶元素移除，并返回该元素的值。具体步骤如下：

（1）判断链栈是否为空，若为空则无法进行出栈操作。

（2）将当前栈顶节点的元素值保存到一个临时变量中。

（3）将栈顶节点的next指针指向下一个节点。

（4）释放原来的栈顶节点。

（5）返回保存的临时变量。

3. 获取栈顶元素

获取栈顶元素操作是返回链栈的栈顶元素的值，但不移除该元素。具体步骤如下： （1）判断链栈是否为空，若为空则无法获取栈顶元素。

（2）返回栈顶节点的元素值。

4. 判断栈是否为空

判断栈是否为空操作是检查链栈是否为空。具体步骤如下：

（1）若链栈的栈顶节点为NULL，则链栈为空，返回True；否则，返回False。

以上是不带头结点的链栈的基本操作。下面通过一个简单的示例来演示这些操作的使用。

假设有一个不带头结点的链栈，初始时为空。我们可以依次进行入栈、出栈、获取栈顶元素和判断栈是否为空的操作。

我们进行入栈操作，依次将元素1、2、3入栈。此时链栈的状态如下：

栈顶->3->2->1->NULL

然后，我们进行出栈操作，依次将栈顶的元素移除。出栈操作的结果为3、2、1。此时链栈的状态为空。

接着，我们进行获取栈顶元素的操作，发现栈为空，无法获取栈顶元素。

我们进行判断栈是否为空的操作，发现栈为空，返回True。

通过以上示例，我们可以看到不带头结点的链栈的基本操作是非常简单的。入栈操作将元素添加到栈顶，出栈操作将栈顶元素移除，获取栈顶元素操作返回栈顶元素的值，判断栈是否为空操作检查链栈是否为空。这些操作可以灵活运用，方便地实现了栈的功能。

#include

#include

#include

#define StackSize 100

typedef char DataType;

typedef struct

{ DataType data[StackSize];

int top;

}SeqStack;

void main()

{

SeqStack S;

char exp[80];

char ch;

bool status;

int i;

void InitStack(SeqStack *S);

bool StackEmpty(SeqStack S);

void Push(SeqStack *S, DataType newelem);

DataType Pop(SeqStack *S);

void PrintStack(SeqStack S);

cout<<" 输入要检验括号匹配的表达式”<

cin>>exp;

InitStack(&S);

status=true;

i=0;

ch=exp[i];

i++;

while ((ch!='\0') && status) //回车换行符

{

switch (ch)

{

case '(':

case '[':

case '{':

Push(&S,ch);

break;

case ')':

if (Pop(&S)!='(')

status=false;

break;

case ']':

if (Pop(&S)!='[') status=false;

break;

case '}':

if (Pop(&S)!='{')

status=false;

break;

default:

break;

}

ch=exp[i];

入栈和出栈的基本操作

栈是一种常见的数据结构，它具有后进先出（LIFO）的特点，即最后进入的元素最先被取出。在计算机科学中，栈被广泛应用于程序的运行、内存管理等方面。本文将介绍栈的基本操作——入栈和出栈。

一、入栈

入栈是指将一个元素放入栈中的操作。在栈中，新元素总是被放在栈顶，而原有的元素则依次向下移动。入栈操作可以用以下伪代码表示：

```

push(Stack, element)

Stack[top] = element

top = top + 1

```

其中，Stack表示栈，element表示要入栈的元素，top表示栈顶指针。入栈操作的实现过程是将元素放入栈顶，然后将栈顶指针向上移动一位。

二、出栈

出栈是指将栈顶元素取出的操作。在栈中，只有栈顶元素可以被取出，而其他元素则不能被访问。出栈操作可以用以下伪代码表示：

```

pop(Stack)

top = top - 1

element = Stack[top]

return element

```

其中，Stack表示栈，top表示栈顶指针，element表示要取出的元素。出栈操作的实现过程是将栈顶指针向下移动一位，然后将栈顶元素取出并返回。

三、应用

栈的入栈和出栈操作在计算机科学中有着广泛的应用。以下是一些常见的应用场景：

1. 程序调用栈

在程序运行时，每个函数都会被压入一个调用栈中。当函数执行完毕后，它会从栈中弹出，控制权会返回到调用该函数的位置。程序调用栈的实现依赖于栈的入栈和出栈操作。

2. 表达式求值

在表达式求值中，栈可以用来存储操作数和运算符。当遇到运算符时，可以将它入栈，当遇到操作数时，可以将它出栈并进行计算。表达式求值的实现依赖于栈的入栈和出栈操作。

3. 内存管理

在内存管理中，栈可以用来存储函数的局部变量和参数。当函数被调用时，它的局部变量和参数会被压入栈中，当函数执行完毕后，它们会从栈中弹出。内存管理的实现依赖于栈的入栈和出栈操作。