Data Structures Algorithms 简明教程

Stack Data Structure

What is a Stack?

栈是一种将元素存储在 LIFO（后进先出）原则中的数据结构，其中插入的最后一个元素将成为要删除的第一个元素。栈是一种抽象数据类型 (ADT)，它在大多数编程语言中都备受欢迎。之所以将其称为栈，是因为它具有与现实世界中的栈类似的操作，例如卡组或盘子堆等。

A stack is a linear data structure where elements are stored in the LIFO (Last In First Out) principle where the last element inserted would be the first element to be deleted. A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages. It is named stack because it has the similar operations as the real-world stacks, for example − a pack of cards or a pile of plates, etc.

stack example

栈被认为是一种复杂的数据结构，因为它使用其他数据结构来实现，例如数组、链表等。

Stack is considered a complex data structure because it uses other data structures for implementation, such as Arrays, Linked lists, etc.

Stack Representation

栈只允许在一端执行所有数据操作。在任何给定时间，我们只能访问栈的顶部元素。

A stack allows all data operations at one end only. At any given time, we can only access the top element of a stack.

下图描绘了一个栈及其操作：

The following diagram depicts a stack and its operations −

stack representation

可以通过数组、结构、指针和链表来实现栈。栈可以是固定大小的，也可以具有动态调整大小的能力。这里，我们要使用数组来实现栈，这使其成为固定大小的栈实现。

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation.

Basic Operations on Stacks

通常会对栈 ADT 执行初始化、使用和反初始化操作。

Stack operations are usually performed for initialization, usage and, de-initialization of the stack ADT.

栈 ADT 中最基本的运算包括：push()、pop()、peek()、isFull()、isEmpty()。这些都是用于执行数据操作和检查栈状态的内置运算。

The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the stack.

栈使用始终指向栈内最顶层元素的指针，因此称为 top 指针。

Stack uses pointers that always point to the topmost element within the stack, hence called as the top pointer.

Stack Insertion: push()

push() 是一种将元素插入栈中的操作。以下是一种用更简单的方式描述 push() 操作的算法。

The push() is an operation that inserts elements into the stack. The following is an algorithm that describes the push() operation in a simpler way.

Algorithm

1. Checks if the stack is full.
2. If the stack is full, produces an error and exit.
3. If the stack is not full, increments top to point next
    empty space.
4. Adds data element to the stack location, where top
    is pointing.
5. Returns success.

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Note − 在 Java 中，我们已经使用内置方法 push() 来执行此操作。

Note − In Java we have used to built-in method push() to perform this operation.

Stack Deletion: pop()

pop() 是一种从栈中删除元素的数据操作。以下伪代码用更简单的方式描述 pop() 操作。

The pop() is a data manipulation operation which removes elements from the stack. The following pseudo code describes the pop() operation in a simpler way.

Algorithm

1. Checks if the stack is empty.
2. If the stack is empty, produces an error and exit.
3. If the stack is not empty, accesses the data element at
   which top is pointing.
4. Decreases the value of top by 1.
5. Returns success.

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Note − 在 Java 中，我们使用内置方法 pop()。

Note − In Java we are using the built-in method pop().

Retrieving topmost Element from Stack: peek()

peek() 是一种在不删除最顶层元素的情况下检索栈内最顶层元素的运算。此操作用于借助顶指针检查栈的状态。

The peek() is an operation retrieves the topmost element within the stack, without deleting it. This operation is used to check the status of the stack with the help of the top pointer.

Algorithm

1. START
2. return the element at the top of the stack
3. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Verifying whether the Stack is full: isFull()

isFull() 操作检查栈是否已满。此操作用于借助顶指针检查栈的状态。

The isFull() operation checks whether the stack is full. This operation is used to check the status of the stack with the help of top pointer.

Algorithm

1. START
2. If the size of the stack is equal to the top position of the stack,
   the stack is full. Return 1.
3. Otherwise, return 0.
4. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Verifying whether the Stack is empty: isEmpty()

isEmpty() 操作验证堆栈是否为空。此操作用于在顶部指针的帮助下检查堆栈的状态。

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the status of the stack with the help of top pointer.

Algorithm

1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Stack Complete implementation

以下是栈在各种编程语言中的完整实现 −

Following are the complete implementations of Stack in various programming languages −

Stack Implementation in C

单击可查看 Stack Program using C 的实现

Click to check the implementation of Stack Program using C