For a stack data structure, stack in and out of stack are the two basic operations. In computer science, stacks are often used to handle function calls, expression evaluation, bracket matching, and so on.
stacksDefinition
A stack is a basic data structure that manages data on a last-in-first-out (lifo) basis. A stack can be thought of as a collection of elements that can be inserted and deleted at only one end of the stack, often referred to as the top. The other end of the stack is called the bottom. In a stack, the last element inserted is the first element to be deleted, a feature that gives the stack a certain order.
stacksabstract data type
A stack can be abstracted into a data type, called an abstract data type (ADT) of the stack. ADT defines the basic operations of the stack, including pushing elements into the stack (push), leaving the stack (pop), and obtaining the top element (top) of the stack. This abstract definition makes the stack more flexible in its implementation and use, and can be applied in different programming languages.
stacksbasic characteristics
Last-in, first-out (LIFO):The stack follows a last-in-first-out principle, with the last inserted element being removed first.
Only inProceed at the top of the stackInsert and Delete Operations:Inserting and deleting elements can only be done at the top of the stack, and elements at the bottom of the stack can only be accessed when the entire stack is emptied.
Commonly seen in recursive and function calls:The nature of the stack makes it widely used in recursion and function calls.
stacksimplementation
There are two main implementations of stacks: array-based sequential stacks and linked list-based chain stacks.
Array-based orderstacks
Sequential stacks use arrays as the underlying data structure, identifying the position of the top element of the stack by maintaining a top of the stack pointer. At the end of the array, perform stack and stack operations on elements, including:
intostacks（push）：Inserts the new element into the top of the stack and updates the top of the stack pointer.
outstacks（pop）：Delete the top of the stack element and update the top of the stack pointer.
GetstacksTop element:Returns the value of the element at the position of the top of the stack pointer.
The array-based sequential stack implementation is simple and efficient, but its capacity needs to be determined at initialization and is not easy to scale dynamically.
Linked list-based chainingstacks
Chained stacks use linked lists to store elements, with each node containing a data element and a pointer to the next node. Chained stacks are more flexible than sequential stacks and can dynamically allocate and release memory without capacity limitations. Operations for the chained stack include:
intostacks（push）：Insert a new node at the head of the linked list to become the new top of the stack.
outstacks（pop）：Delete the linked list header node and update the top stack pointer.
GetstacksTop element:Returns the element value of the node at the head of the linked list.
Chained stacks are suitable for dynamic memory allocation, but may take up more memory space than sequential stacks.
In the stack data structure, the basic operations mainly include pushing in the stack, leaving the stack (pop), and obtaining the top element (top). These operations are at the core of the stack implementation and application, and are discussed in detail below and how they are implemented.
intostacksOperation
A stacking operation is when a new element is added to the top of the stack, making it the new top element of the stack. This process involves updating the stack top pointer so that it points to the newly inserted element. The steps to enter the stack are as follows:
Tell if the stack is full (for array-based sequential stacks).
If the stack is not full, place the new element at the top of the stack.
Update the stack top pointer to point to the newly inserted element.
Array-based orderstacksofstacksImplementation
For array-based sequential stacks, the implementation of the stack is relatively straightforward. Here's an example of a simplified on-stack implementation (in Python):
class arraystack:
def __init__(self, capacity):
self.capacity = capacity
self.stack = [none] *capacity
self.top = -1 initializes the top of the stack pointer to -1
def is_full(self):
return self.top == self.capacity - 1
def push(self, item):
if not self.is_full():
self.top += 1
self.stack[self.top] = item
print(f"The stack is successful")
else:print("The stack is full, and the stack ingress fails")
Example. stack = arraystack(5)
stack.push(1) 1 is successfully put into the stack.
stack.push(2) 2 The stack is successful.
stack.push(3) 3 The stack is successful.
stack.push(4) 4 Stack entry successful.
stack.push(5) 5 Successful incoming.
stack.push(6) The stack is full, and the stack entry fails.
Linked list-based chainingstacksofstacksImplementation
For linked list-based chain stacks, the implementation of on-stack is equally intuitive. Here's an example of a simplified chained stack implementation into stack:
class node:
def __init__(self, data=none):
self.data = data
self.next = none
class linkedstack:
def __init__(self):
self.top = none initializes the top stack pointer to be empty.
def push(self, item):
new_node = node(item)
new_node.next = self.top
self.top = new_node
print(f"The stack is successful")
Example. linked_stack = linkedstack()
linked_stack.push(1) 1 is successfully put into the stack.
linked_stack.push(2) 2 The stack is successful.
linked_stack.push(3) 3 The stack is successful.
The implementation of the on-stack operation can be adapted to the specific programming language and actual needs, but the core idea is to add new elements to the top of the stack and update the top of the stack pointer.
outstacksOperation
An off-stack operation is when an element is removed from the top of the stack so that it is no longer part of the stack. This process also involves updating the top of the stack pointer so that it points to the new top element. The steps to perform the e-stack operation are as follows:
Determine whether the stack is empty.
If the stack is not empty, remove the top element of the stack.
Update the top of the stack pointer to point to the new top of the stack element.
Array-based orderstacksoutstacksImplementation
For array-based sequential stacks, the implementation of the stack is also relatively intuitive. Here's an example of a simplified out-of-stack implementation:
class arraystack:
# ..The previous definition is omitted).
def is_empty(self):
return self.top == -1
def pop(self):
if not self.is_empty():
item = self.stack[self.top]
self.top -= 1
print(f"The stack is successful")
return item
else:print("The stack is empty, and the stack exit fails")
Example. stack = arraystack(5)
stack.push(1)
stack.push(2)
stack.pop() 2 is out of the stack successfully.
stack.pop() 1 is successfully out of the stack.
stack.The pop() stack is empty, and the egress stack fails.
Linked list-based chainingstacksoutstacksImplementation
For linked list-based chain stacks, the implementation of the e-stack is equally intuitive. Here's an example of a simplified chained stack-out implementation:
class linkedstack:
# ..The previous definition is omitted).
def is_empty(self):
return self.top is none
def pop(self):
if not self.is_empty():
item = self.top.data
self.top = self.top.next
print(f"The stack is successful")
return item
else:print("The stack is empty, and the stack exit fails")
Example. linked_stack = linkedstack()
linked_stack.push(1)
linked_stack.push(2)
linked_stack.pop() 2 is out of the stack successfully.
linked_stack.pop() 1 is successfully out of the stack.
linked_stack.The pop() stack is empty, and the egress stack fails.
Off-stack operations also need to be adapted to specific programming languages and actual needs, but the core idea is to remove an element from the top of the stack and update the top of the stack pointer.
GetstacksTop element
Get a top-of-stack element is a query operation that returns the value of the element at the current top of the stack, but does not move it off the stack. This can help us understand the current state of the stack.
Array-based orderstacksof acquisitionsstacksTop element implementation
For array-based sequential stacks, the implementation of getting the top element of the stack is also simple. Here's an example of a simplified implementation:
class arraystack:
# ..The previous definition is omitted).
def get_top(self):
if not self.is_empty():
item = self.stack[self.top]
print(f"The current top element of the stack is")
return item
else:print("The stack is empty and the top element of the stack cannot be obtained")
Example. stack = arraystack(5)
stack.push(1)
stack.push(2)
stack.get top() is currently 2 for the top element of the stack
stack.pop()
stack.get top() is currently 1 at the top of the stack
Linked list-based chainingstacksof acquisitionsstacksTop element implementation
For linked list-based chained stacks, the implementation of getting the top element of the stack is just as simple. Here's an example of a simplified implementation:
class linkedstack:
# ..The previous definition is omitted).
def get_top(self):
if not self.is_empty():
item = self.top.data
print(f"The current top element of the stack is")
return item
else:print("The stack is empty and the top element of the stack cannot be obtained")
Example. linked_stack = linkedstack()
linked_stack.push(1)
linked_stack.push(2)
linked_stack.get top() is currently 2 for the top element of the stack
linked_stack.pop()
linked_stack.get top() is currently 1 at the top of the stack
The Get Top Stack Element operation can help us understand what's going on in the current stack, but it doesn't affect the actual structure of the elements in the stack.