logo图片
数据结构与算法

堆栈

堆栈是一种抽象数据类型 (ADT),通常用于大多数编程语言。它被命名为堆栈,因为它的行为类似于现实世界的堆栈,例如-一副纸牌或一堆盘子等。
堆栈示例
现实世界的堆栈只允许在一端进行操作。例如,我们只能从堆栈顶部放置或移除卡片或盘子。同样,堆栈 ADT 仅允许在一端进行所有数据操作。在任何给定时间,我们只能访问堆栈的顶部元素。
此功能使其成为 LIFO 数据结构。 LIFO 代表后进先出。在这里,最后放置(插入或添加)的元素首先被访问。在堆栈术语中,插入操作称为 PUSH操作,移除操作称为 POP操作。

堆栈表示

下图描述了堆栈及其操作-
堆栈表示
堆栈可以通过数组、结构、指针和链表来实现。堆栈可以是固定大小的,也可以是动态调整大小的。在这里,我们将使用数组来实现堆栈,这使它成为一个固定大小的堆栈实现。

基本操作

堆栈操作可能涉及初始化堆栈、使用它然后取消初始化它。除了这些基本的东西,堆栈用于以下两个主要操作-
push()-将元素压入(存储)堆栈。 pop()-从堆栈中移除(访问)一个元素。
当数据被压入堆栈时。
为了有效地使用堆栈,我们还需要检查堆栈的状态。出于同样的目的,堆栈中添加了以下功能-
peek()-获取堆栈的顶部数据元素,而不删除它。 isFull()-检查堆栈是否已满。 isEmpty()-检查堆栈是否为空。
在任何时候,我们都会维护一个指向堆栈上最后一个 PUSHed 数据的指针。因为这个指针总是代表栈顶,因此命名为 toptop 指针提供堆栈的顶部值而不实际删除它。
首先我们应该了解支持堆栈函数的过程-

peek()

peek() 函数的算法-
begin procedure peek
   return stack[top]
end procedure
C语言中peek()函数的实现-
示例
int peek() {
   return stack[top];
}

isfull()

isfull() 函数的算法-
begin procedure isfull
   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure
C语言实现isfull()函数-
示例
bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

isempty()

isempty() 函数的算法-
begin procedure isempty
   if top less than 1
      return true
   else
      return false
   endif
   
end procedure
isempty() 函数在 C 编程语言中的实现略有不同。我们将顶部初始化为-1,因为数组中的索引从 0 开始。因此我们检查顶部是否低于零或-1 以确定堆栈是否为空。这是代码-
示例
bool isempty() {
   if(top ==-1)
      return true;
   else
      return false;
}

Push操作

将新数据元素放入堆栈的过程称为Push操作。Push操作涉及一系列步骤-
第 1 步-检查堆栈是否已满。 第 2 步-如果堆栈已满,则产生错误并退出。 第 3 步-如果堆栈未满,则递增 top 以指向下一个空白空间。 第 4 步-将数据元素添加到堆栈位置,顶部指向的位置。 第 5 步-返回成功。 堆栈Push操作
如果使用链表来实现栈,那么在第3步,我们需要动态分配空间。

PUSH 操作算法

可以推导出一个简单的Push操作算法如下-
begin procedure push: stack, data
   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data
end procedure
用 C 语言实现这个算法非常容易。请参阅以下代码-
示例
void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Pop操作

在从堆栈中删除内容的同时访问内容,称为Pop操作。在 pop() 操作的数组实现中,数据元素实际上并没有被删除,而是将 top 递减到堆栈中的较低位置以指向下一个值。但在链表实现中,pop() 实际上是删除数据元素并释放内存空间。
Pop 操作可能涉及以下步骤-
第 1 步-检查堆栈是否为空。 第 2 步-如果堆栈为空,则产生错误并退出。 第 3 步-如果堆栈不为空,则访问 top 指向的数据元素。 第 4 步-将 top 的值减 1、 第 5 步-返回成功。 堆栈Pop操作

Pop操作算法

Pop 操作的简单算法可以推导出如下-
begin procedure pop: stack
   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top-1
   return data
end procedure
该算法在C中的实现,如下-
示例
int pop(int data) {
   if(!isempty()) {
      data = stack[top];
      top = top-1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4