数据结构中的 LIFO 方法

2025年3月17日 | 阅读16分钟

LIFO代表**后进先出**，在此原则下我们将数据元素输入到数据结构中。这里，我们将弹出最新添加的数据元素。这意味着最后一个进入的元素将是第一个被弹出的。

例如：

堆叠在一起的书籍数量

另一个最佳的现实生活示例是**汉诺塔。**这是一个有趣的游戏，完全基于后进先出的原则。

基于LIFO原则的数据结构是栈。
在栈数据结构中，我们将执行两个主要操作：第一个是**压入(push)**，另一个是**弹出(pop)**。
最近被压入栈的数据元素将首先被弹出；反之亦然，最初被压入栈的数据元素将最后被弹出，直到我们弹出其之前存在的所有元素。
栈只有一个端点，或者我们可以说它只有一个开口。
大多数程序都基于LIFO的概念。
对于各种表达式的求值，如后缀转中缀、中缀转前缀以及前缀转后缀，栈都扮演着非常重要的角色。
它的主要应用是**递归**的实现。递归用于更有效地解决问题。
此外，LIFO原则还用于堆中，以及在程序执行时填充程序的激活记录。
为了实现下推自动机以检查字符串是否被机器接受，使用了栈数据结构。
它主要基于LIFO原则，在此原则下，我们根据需要将输入字符串逐一压入栈中，并以同样的方式弹出相同数量的字符串，以便我们能够轻松计算给定字符串中字母的数量，并识别它是否属于所提及的上下文无关文法。

基于LIFO原则的数据结构是**栈**。我们主要对其执行两个操作：**压入(push)**和**弹出(pop)**。压入操作用于将数据元素压入栈中，弹出操作用于从栈中弹出数据元素。

在栈数据结构中，我们有一个名为top的指针，它指向栈顶的值。最初，当栈为空时，它指向空指针；因此这种情况被称为**下溢条件。**在栈中，我们给定栈的容量，比如**n**。我们需要将数据值逐一插入栈中，直到栈顶达到栈的容量。如果达到容量，则这种情况被称为**上溢。**

让我们借助一个例子来理解LIFO的概念，

如果我们有一个容量为10个盘子的容器，我们需要将盘子逐一放入其中，那么我们可以使用后进先出原则来完成，

盘子编号从1到10，我们被要求按递增顺序将所有盘子推入容器中

最初，容器是空的；因此我们称之为下溢条件。
我们将盘子1放入容器中。
容器的顶部将指向盘子1；之后，我们将盘子2压入容器中。
然后，现在顶部指针将指向盘子2；类似地，我们将所有盘子压入容器中。
最后，当容器的顶部指向盘子10时，这将表明上溢条件；因此在我们弹出一个盘子之前，我们不能再放入其他盘子。
如果我们要从容器中取出盘子5，我们必须从容器中取出盘子，直到我们取出盘子5。
首先，我们将弹出最近推入的盘子，即盘子10，从容器中。
之后，我们将从容器中弹出盘子9。
然后是8，然后是7，然后是6，最后容器的顶部将指向盘子5。
我们将从容器中弹出盘子5。

从上面的例子中，我们已经了解了后进先出原则的工作原理。

现在，让我们在程序中用栈实现LIFO原则。

在程序中使用栈实现LIFO原则

为了使用栈实现LIFO方法，我们提供了一个具有最大容量限制的栈。对于栈，我们有一个名为top的指针，它被初始化为-1，表示栈的下溢条件，这意味着我们无法从栈中弹出数据元素，因为它是空状态，但我们可以将数据元素输入其中。我们将数据元素逐一输入栈中，直到达到栈的容量限制；一旦达到栈的限制，即top == capacity - 1，我们就不能再输入更多数据元素到栈中，这意味着栈的溢出条件。要向栈中输入更多数据元素，我们需要通过应用弹出操作从栈中移除数据元素。

通过这种方式，我们将使用栈实现LIFO原则。

在C编程语言中使用栈实现LIFO方法

// Using stack implementation LIFO approach in C //
// Here we will use a stack of the capacity mentioned by the user, it has a pointer //
// named as top, which points the data element present at the top of the stack //
// Initially the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   
#include<stdio.h>
int stack [ 100 ] , x , top = -1 , n , i ;
void push()
{
	if ( top >= n - 1 )           // Checking the overflow condition of the stack //
	{
		printf ( "Stack is overflow !! \n " ) ;
	}
	else
	{
		printf ( "Enter value to be pushed : " ) ;
		scanf ( "%d" , &x ) ;
		top = top + 1 ;
		stack [ top ] = x ;
	}
}
void pop()
{
	if ( top == -1 )            // Checking the underflow condition of the stack //
	{
		printf ( "Stack is underflow !! \n " ) ;
	}
	else
	{
        printf ( "The popped element is %d \n " , stack [ top ] ) ;
        top = top - 1 ;
    }
}
void traverse()
{
	if ( top == -1 )
	{
		printf ( "Stack is empty !! \n " ) ;
	}
	else
	{
		for ( i = top ; i >= 0 ; i-- )
		{
			printf ( "%d \n " , stack [ i ] ) ;
		}
	}
}
int menu()
{
	int ch ;
	printf ( " \t \t \t 1. PUSH OPERATION \n " ) ;
	printf ( " \t \t \t 2. POP OPERATION \n " ) ;
	printf ( " \t \t \t 3. TRAVERSE OPERATION \n " ) ;
    printf ( " \t \t \t 4. EXIT \n " ) ;
    printf ( "Enter your choice: " ) ;
    scanf ( "%d" , &ch ) ;
    return ch ;
}
void main()
{
	printf ( "Enter size of stack : " ) ;
	scanf ( "%d" , &n ) ;
	while ( 1 )
	{
		switch ( menu() )
		{
			case 1 :
				push (  ) ;
				break ;
			case 2 :
				pop (  ) ;
				break ;
			case 3 :
				traverse (  ) ;
				break ;
			case 4 :
				exit( 0 ) ;
				break ;
		}	}
}

上述程序的输出

在C++编程语言中使用栈实现LIFO方法

// Using stack implementation LIFO approach in C++ //
// Here we will use a stack of the capacity mentioned by the user, it has a pointer //
// named as top, which points the data element present at the top of the stack //
// Initially the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   
#include<iostream>
using namespace std ;
int stack [ 100 ] , x , top = - 1, n , i ;

void push( )
{
	if ( top >= n - 1 )           // Checking the overflow condition of the stack //
	{
		cout << "Stack is overflow !! " << endl ;
	}
	else
	{
		cout << "Enter value to be pushed : " ;
		cin >> x ;
		top = top + 1 ;
		stack [ top ] = x ;
	}
}
void pop( )
{
	if ( top == -1 )            // Checking the underflow condition of the stack //
	{
		cout << "Stack is underflow !! " << endl ;
	}
	else
	{
        cout << "The popped element is " << stack [ top ] << endl ;
        top = top - 1 ;
    }
}
void traverse( )
{
	if ( top == -1 )
	{
		cout << "Stack is empty !! " << endl ;
	}
	else
	{
		for ( i = top ; i >= 0 ; i-- )
		{
			cout << stack [ i ] << endl ;
		}
	}
}
int menu()
{
	int ch ;
	cout << " \t \t \t 1. PUSH OPERATION " << endl ;
	cout << " \t \t \t 2. POP OPERATION " << endl ;
	cout << " \t \t \t 3. TRAVERSE OPERATION " << endl ;
    cout << " \t \t \t 4. EXIT " << endl ;
    cout << "Enter your choice: " << endl ;
    cin >> ch ;
    return ch ;
}
int main()
{
	
	cout << "Enter size of stack : " ;
	cin >> n ;
	while ( 1 )
	{
		switch ( menu() )
		{
			case 1 :
				push ( ) ;
				break ;
			case 2 :
				pop ( ) ;
				break ;
			case 3 :
				traverse ( ) ;
				break ;
			case 4 :
				exit( 0 ) ;
				break ;
		}
	}
}

上述程序的输出

在JAVA编程语言中使用栈实现LIFO方法

// Using stack implementation LIFO approach in JAVA //
// Here we will use a stack of the capacity mentioned by the user, it has a pointer //
// named as top, which points the data element present at the top of the stack //
// Initially the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   
import java.io.*;
import java.util.*;

class Main {
	// Pushing element on the top of the stack
	static void Push(Stack<Integer> s)
	{
		for (int i = 0; i < 5; i++) {
			s.push(i);
		}
	}

	// Popping element from the top of the stack
	static void Pop(Stack<Integer> s)
	{
		System.out.println("Pop :");

		for (int i = 0; i < 5; i++) {
			Integer x = (Integer)s.pop();
			System.out.println(x);
		}
	}

	// Displaying element on the top of the stack
	static void Peek(Stack<Integer> s)
	{
		Integer info = (Integer)s.peek();
		System.out.println("Element on the top of the stack is : " + info);
	}

	// Searching element in the stack
	static void Search(Stack<Integer> stack, int data)
	{
		Integer pos = (Integer)stack.search(data);

		if (pos == -1)                 // Checking the underflow condition of the stack //
			System.out.println("Element not found");
		else
			System.out.println("Element is found at position " + pos);
	}

	public static void main(String[] args)
	{
		Stack<Integer> stack = new Stack<Integer>();

		Push(stack);
		Pop(stack);
		Push(stack);
		Peek(stack);
		Search(stack, 1);
		Search(stack, 7);
	}
}

上述程序的输出

在Python编程语言中使用栈实现LIFO方法

# Using stack implementation LIFO approach in Python #
# Here, we will use a stack of the capacity mentioned by the user; it has a pointer #
# named as top, which points to the data element present at the top of the stack #
# Initially, the top pointer of the stack points to the -1, which indicates #
# the underflow condition. #   

# Pushing element on the top of the stack
def Push(s):
  for i in range(5):
    s.append(i)
  return s

# Popping element from the top of the stack
def Pop(s):
  print("Pop :")

  for i in range(5):
    y = s[-1]
    s.pop()
    print(y)
  return s

# Displaying element on the top of the stack
def Peek(s):
  data = s[-1]
  print("Element present on the top of the stack is :", data)

# Searching element in the stack
def Search(s , data ):
  pos = -1
  count = 0
  while(len(s) > 0):
    count = count + 1
    if(s[-1] == data):
      pos = count
      break
    s.pop()

  if (pos == -1):
    print( "Element not found")
  else:
    print("Element is found at position", pos)

Stack = []
Push(Stack)
Pop(Stack)
Push(Stack)
Peek(Stack)
Search(Stack, 3)
Search(Stack, 7)

上述程序的输出

在C#编程语言中使用栈实现LIFO方法

// Using stack implementation LIFO approach in C# //
// Here, we will use a stack of the capacity mentioned by the user; it has a pointer //
// named as top, which points to the data element present at the top of the stack //
// Initially, the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   
using System;
using System.Collections.Generic;

class JTP
{
	// Pushing element on the top of the stack
	static void sPush(Stack<int> s)
	{
		for (int i = 0; i < 5; i++)
		{
			s.Push(i);
		}
	}

	// Popping element from the top of the stack
	static void sPop(Stack<int> s)
	{
		Console.WriteLine("Pop :");

		for (int i = 0; i < 5; i++)
		{
			int y = (int)s.Pop();
			Console.WriteLine(y);
		}
	}

	// Displaying element on the top of the stack
	static void sPeek(Stack<int> s)
	{
		int data = (int)s.Peek();
		Console.WriteLine("Element present on the top of the stack is : " + data);
	}
	// Searching element in the stack
	static void Search(Stack<int> s, int data)
	{
		bool pos = s.Contains(data);
		if (pos == false)
			Console.WriteLine("Element not found");
		else
			Console.WriteLine("Element is found at position " + pos);
	}
	public static void Main(String[] args)
	{
		Stack<int> stack = new Stack<int>();
		sPush(stack);
		sPop(stack);
		sPush(stack);
		sPeek(stack);
		Search(stack, 2);
		Search(stack, 6);
	}
}

上述程序的输出

Pop:
4
3
2
1
0
Element on stack top: 4
Element is found at position 3
Element not found

在JavaScript编程语言中使用栈实现LIFO方法

// Using stack implementation LIFO approach in JavaScript //
// Here, we will use a stack of the capacity mentioned by the user; it has a pointer //
// named as top, which points to the data element present at the top of the stack //
// Initially, the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   

<script>
// Pushing element on the top of the stack
function Push(s)
{
    for (var i = 0; i < 5; i++)
    {
        s.push(i);
    }
    return s;
}
 
// Popping element from the top of the stack
function Pop(s)
{
    document.write(  "Pop :<br>");
 
    for (var i = 0; i < 5; i++)
    {
        var y = parseInt(s[s.length-1]);
        s.pop();
        document.write( y + "<br>");
    }
    return s;
}
 
// Displaying element on the top of the stack
function Peek(s)
{
    var element = parseInt(s[s.length-1]);
    document.write( "Element on stack top : " + element +
    "<br>");
}
// Searching element in the stack
function Search( s ,  info )
{
    var pos = -1,count = 0;
    while(s.length > 0)
    {
        count++;
        if(s[s.length-1] == info)
        {
            pos = count;
            break;
        }
        s.pop();
    }
    if (pos == -1)
        document.write( "Element not found" + "<br>");
    else
        document.write("Element is found at position "
        + pos + "<br>");
}
    s=[] ;
 
    s = Push(s);
    s = Pop(s);
    s = Push(s);
    Peek(s);
    Search(s, 2);
    Search(s, 6);
 
</script>

上述程序的输出

Pop:
4
3
2
1
0
Element on stack top: 4
Element is found at position 3
Element not found

在C编程语言中使用结构实现栈的LIFO方法

// Using stack implementation using the structure for implementing  LIFO approach in C //
// Here, we will use a stack of the capacity mentioned by the user; it has a pointer //
// named as top, which points to the data element present at the top of the stack //
// Initially, the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   

#include<stdio.h>
struct arraystack
{
	int top ;
	int capacity ;
	int *array ;
} ;
struct arraystack* createstack ( int ) ;

struct arraystack* createstack ( int cap )
{
	struct arraystack* stack ;
	stack = ( struct arraystack* ) malloc ( sizeof ( struct arraystack ) ) ; // it returns the void pointer that would be typecast into arraysrack
    stack->top = -1 ;
    stack->capacity = cap ;
    stack->array = malloc ( sizeof (int)*stack->capacity ) ;
    return stack;	 
}
int isfull ( struct arraystack* stack )
{
	int cap ;
//	cap = stack->capacity ;
	if ( stack->top == ( stack->capacity ) - 1 )
	return ( 1 ) ;
	else
	return ( 0 ) ;
}
int isempty ( struct arraystack* stack )
{
	if ( stack->top == -1 )
	return ( 1 ) ;
	else
	return ( 0 ) ;
}
void push ( struct arraystack* stack, int item )
{
	if ( !isfull(stack) )
	{
		stack->top++ ;
		stack->array[stack->top] = item ;
	}
}
int pop ( struct arraystack* stack )
{
	int item ;
	if ( !isempty ( stack ) )
	{
	     item = stack->array [ stack->top ] ;
	     stack->top-- ;
	     return item ;
	}
	return -1 ;
}
int peek ( struct arraystack *stack )
{
	int n ;
    if ( stack->top == -1 )
    return -1 ;
    else
    n = stack->array [ stack->top ] ;
    return n ;
 
}
void traverse ( struct arraystack *stack )
{
	int i ;
	if ( stack->top == -1 )
	printf ( "Stack is empty!! \n " ) ;
	else
	printf ( "Stack elements are: \n " ) ;
	for ( i = 0 ; i <= stack->top ; i++ )
	{
		printf ( "%d \n " , stack->array [ i ] ) ;
	}
}
void main()
{
	int n , item ;
	struct arraystack* stack ;
	stack = createstack ( 2 ) ;
	printf ( " \t\t\t 1. Push operation \n " ) ;
	printf ( " \t\t\t 2. Pop operation \n " ) ;
	printf ( " \t\t\t 3. Traverse operation \n " ) ;
	printf ( " \t\t\t 4. Peek operation \n " ) ;
	printf ( " \t\t\t 5. Exit \n " ) ;
	while ( 1 )
	{
		printf ( "Enter your choice: " ) ;
		scanf ( "%d" , &n ) ;
		switch ( n )
		{
			case 1 :
				if ( isfull ( stack ) )
				printf ( "Stack is overflow!! \n " ) ;
				else
				{
					printf ( "Enter data: " ) ;
					scanf ( "%d" , &item ) ;
					push ( stack , item ) ;
				}
				break ;
			case 2 :
				item = pop ( stack ) ;
				if ( item == -1 )
				printf ( "Stack is underflow!! \n " ) ;
				else
				{
					printf ( "Poped element: %d \n " , item ) ;
				}
				break ;
			case 3 :
				traverse ( stack ) ;
				break ;
			case 4 :
				item = peek ( stack ) ;
				if ( item == -1 )
				printf ( "Stack is empty \n " ) ;
				else
				printf ( "Peek value is: %d \n " , item ) ;
				break ; 
			case 5 :
				exit ( 0 ) ;
				break ;
		}
	}	
}

上述程序的输出

在C++编程语言中使用结构实现栈的LIFO方法

// Using stack implementation using structure for implementing  LIFO approach in C++ Language //
// Here, we will use a stack of the capacity mentioned by the user; it has a pointer //
// named as top, which points to the data element present at the top of the stack //
// Initially, the top pointer of the stack points to the -1, which indicates //
// the underflow condition. //   

#include<iostream>
#include<stdlib.h>
using namespace std ;
struct arraystack
{
	int top ;
	int capacity ;
	int *array ;
} ;
struct arraystack* createstack ( int ) ;

struct arraystack* createstack ( int cap )
{
	struct arraystack* stack ;
	stack = ( struct arraystack* ) malloc( sizeof ( struct arraystack ) ) ; // it returns the void pointer that would be typecast into arraysrack
    stack->top = -1 ;
    stack->capacity = cap ;
    stack->array = (int*)malloc(sizeof(int)*stack->capacity) ;
    return stack;	 
}
int isfull ( struct arraystack* stack )
{
	int cap ;
//	cap = stack->capacity ;
	if ( stack->top == ( stack->capacity ) - 1 )
	return ( 1 ) ;
	else
	return ( 0 ) ;
}
int isempty ( struct arraystack* stack )
{
	if ( stack->top == -1 )
	return ( 1 ) ;
	else
	return ( 0 ) ;
}
void push ( struct arraystack* stack, int item )
{
	if ( !isfull(stack) )
	{
		stack->top++ ;
		stack->array[stack->top] = item ;
	}
}
int pop ( struct arraystack* stack )
{
	int item ;
	if ( !isempty ( stack ) )
	{
	     item = stack->array [ stack->top ] ;
	     stack->top-- ;
	     return item ;
	}
	return -1 ;
}
int peek ( struct arraystack *stack )
{
	int n ;
    if ( stack->top == -1 )
    return -1 ;
    else
    n = stack->array [ stack->top ] ;
    return n ;
 
}
void traverse ( struct arraystack *stack )
{
	int i ;
	if ( stack->top == -1 )
	cout << "Stack is empty!! "  << endl ;
	else
	cout << "Stack elements are: " << endl ;
	for ( i = 0 ; i <= stack->top ; i++ )
	{
		cout << stack->array [ i ] << endl ;
	}
}
int main()
{
	int n , item ;
	struct arraystack* stack ;
	stack = createstack ( 12 ) ;
	cout << " \t\t\t 1. Push operation " << endl ;
	cout << " \t\t\t 2. Pop operation " << endl ;
	cout << " \t\t\t 3. Traverse operation " << endl ;
	cout << " \t\t\t 4. Peek operation " << endl ;
	cout << " \t\t\t 5. Exit " << endl ;
	while ( 1 )
	{
		cout << "Enter your choice: " ;
		cin >> n ;
		switch ( n )
		{
			case 1 :
				if ( isfull ( stack ) )
				cout << "Stack is overflow!! " << endl ;
				else
				{
					cout << "Enter data: " ;
					cin >> item ;
					push ( stack , item ) ;
				}
				break ;
			case 2 :
				item = pop ( stack ) ;
				if ( item == -1 )
				cout << "Stack is underflow!! " << endl ;
				else
				{
					cout << "Poped element: " << item << endl ;

				}
				break ;
			case 3 :
				traverse ( stack ) ;
				break ;
			case 4 :
				item = peek ( stack ) ;
				if ( item == -1 )
				cout << "Stack is empty " << endl ;
				else
				cout << "Peek value is: " << item << endl ;
				break ; 
			case 5 :
				exit ( 0 ) ;
				break ;
		}
	}
}

上述程序的输出

下一主题数据结构中的波兰表示法

数据结构中的 LIFO 方法

在程序中使用栈实现LIFO原则

在C编程语言中使用栈实现LIFO方法

在C++编程语言中使用栈实现LIFO方法

在JAVA编程语言中使用栈实现LIFO方法

在Python编程语言中使用栈实现LIFO方法

在C#编程语言中使用栈实现LIFO方法

在JavaScript编程语言中使用栈实现LIFO方法

在C编程语言中使用结构实现栈的LIFO方法

在C++编程语言中使用结构实现栈的LIFO方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的 LIFO 方法

在程序中使用栈实现LIFO原则

在C编程语言中使用栈实现LIFO方法

在C++编程语言中使用栈实现LIFO方法

在JAVA编程语言中使用栈实现LIFO方法

在Python编程语言中使用栈实现LIFO方法

在C#编程语言中使用栈实现LIFO方法

在JavaScript编程语言中使用栈实现LIFO方法

在C编程语言中使用结构实现栈的LIFO方法

在C++编程语言中使用结构实现栈的LIFO方法

相关帖子

给定数字的小于或等于的元素数量

最大化硬币，使根到叶子路径和为正

动态数据结构

如何在 C++ 中使用 Qdebug 打印字符串字面量和 Qstring

单词阶梯

后缀数组 nLogN 算法

合并两个二叉最大堆

添加元素以使范围内的所有元素都存在于数组中

结构化数据与非结构化数据

查找二叉树节点层级的公式

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器