0
In modern computer languages, the stack is usually implemented with more operations than just "push" and "pop". The length of a stack can often be returned as a parameter. Another helper operation top (also known as peek and peak) can return the current top element of the stack without removing it from the stack. This section gives pseudocode for adding or removing nodes from a stack, as well as the length and top functions. Throughout we will use null to refer to an end-of-list marker or sentinel value, which may be implemented in a number of ways using pointers. In modern computer languages, the stack is usually implemented with more operations than just "push" and "pop". The length of a stack can often be returned as a parameter. Another helper operation top[1] (also known as peek and peak) can return the current top element of the stack without removing it from the stack. This section gives pseudocode for adding or removing nodes from a stack, as well as the length and top functions. Throughout we will use null to refer to an end-of-list marker or sentinel value, which may be implemented in a number of ways using pointers. record Node {
data // The data being stored in the node
next // A reference to the next node; null for last node
}
record Stack {
Node stackPointer // points to the 'top' node; null for an empty stack
}
function push(Stack stack, Element element) { // push element onto stack
new(newNode) // Allocate memory to hold new node
newNode.data := element
newNode.next := stack.stackPointer
stack.stackPointer := newNode
}
function pop(Stack stack) { // increase the stack pointer and return 'top' node
// You could check if stack.stackPointer is null here.
// If so, you may wish to error, citing the stack underflow.
node := stack.stackPointer
stack.stackPointer := node.next
element := node.data
return element
}
function top(Stack stack) { // return 'top' node
return stack.stackPointer.data
}
function length(Stack stack) { // return the amount of nodes in the stack
length := 0
node := stack.stackPointer
while node not null {
length := length + 1
node := node.next
}
return length
}
As you can see, these functions pass the stack and the data elements as parameters and return values, not the data nodes that, in this implementation, include pointers. A stack may also be implemented as a linear section of memory (i.e. an array), in which case the function headers would not change, just the internals of the functions. Implementation
A typical storage requirement for a stack of n elements is O(n). The typical time requirement of O(1) operations is also easy to satisfy with a dynamic array or (singly) linked list implementation. C++'s Standard Template Library provides a "stack" templated class which is restricted to only push/pop operations. Java's library contains a Stack class that is a specialization of Vector. This could be considered a design flaw because the inherited get() method from Vector ignores the LIFO constraint of the Stack. Here is a simple example of a stack with the operations described above (but no error checking) in Python. class Stack(object):
def __init__(self):
self.stack_pointer = None
def push(self, element):
self.stack_pointer = Node(element, self.stack_pointer)
def pop(self):
e = self.stack_pointer.element
self.stack_pointer = self.stack_pointer.next
return e
def peek(self):
return self.stack_pointer.element
def __len__(self):
i = 0
sp = self.stack_pointer
while sp:
i += 1
sp = sp.next
return i
class Node(object):
def __init__(self, element=None, next=None):
self.element = element
self.next = next
if __name__ == '__main__':
# small use example
s = Stack()
[s.push(i) for i in xrange(10)]
print [s.pop() for i in xrange(len(s))]
The above is admittedly redundant as Python supports the 'pop' and 'append' functions to lists.
Still curious? Ask our experts.
Chat with our AI personalities
Beau
Coach
SteveA stack is one of the basic data structures, implementing a last-in-first-out (LIFO) container. Pretty much like a stack of plates, the item last entered (put on top of the stack) will be the first one removed (pulled off the top of the stack), while the item first entered (put onto the empty stack) will be the last one removed.
The main operations of a stack are:
1. push - To insert the element into the stack
2. pop - To remove an element from the stack
Other additional functions can also be performed:
3. top - To display the element at the top of the stack
4. size - To display the size of the stack
5. isempty - To determine whether the stack if empty or not
Add your answer:
Earn +20 pts
Design an algorithm to show the different operations on a stack?
Design an algorithm to show the different operations on a stack?
What is time complexity of stack?
All major queue operations (push, pop and front) are constant time operations.
What is the most common method for illustrating the operations of a networking stack?
The OSI Model
What is the meaning of stack underflow?
Stack underflow occurs when an operation is attempted on an empty stack, resulting in an attempt to access a nonexistent element at the top of the stack. This can lead to errors or unexpected behavior in programs that rely on stack data structures. To prevent stack underflow, it is important to check the stack's current size before performing operations that could potentially lead to underflow.
Can stack be as a pointer?
A stack is a data structure in which last item inserted is taken out first . That's why they are known as LIFO (last in first out). Inserting an item in stack is termed as push and taking an item out from stack I s termed as pop. Stack pointer is the pointer that points to the top of the stack or that points the item at the top of the stack and help in adding or deleting the item from the top of stack.
