1. Expression evaluation and syntax parsing
Calculators employing reverse Polish Notation use a stack structure to hold values. Expressions can be represented in prefix, post fix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines.
2. Runtime memory management
A number of programming languages are stack oriented , meaning they define most basic operations (adding two numbers, printing a character) as taking their arguments from the stack, and placing any return values back on the stack. For example, Post Script has a return stack and an operand stack, and also has a graphics state stack and a dictionary stack.
3. SecuritySome computing environments use stacks in ways that may make them vulnerable to security breaches and attacks. Programmers working in such environments must take special care to avoid the pitfalls of these implementations.
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))]
No. A stack is a LIFO (Last In First Out) data structure.A queue is a FIFO (First In First Out) data structure.
Explain The merits of using a deque to implement a stack in data structure
no answer
stack data structure.
stack is a linear data structure in which data item is either inserted or deleted at one end there are mainly two operations performed on stack.they're push poppush:writing a value to the stack is push or moving the stack pointer up to accomodatethe new item. pop:reading a value from stack or moving the stack pointer down.
No. A stack is a LIFO (Last In First Out) data structure.A queue is a FIFO (First In First Out) data structure.
Explain The merits of using a deque to implement a stack in data structure
no answer
stack data structure.
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where elements are added and removed from the same end called the top. Elements can only be added or removed from the top of the stack, making it a simple and efficient data structure for storing and accessing data.
stack is a linear data structure in which data item is either inserted or deleted at one end there are mainly two operations performed on stack.they're push poppush:writing a value to the stack is push or moving the stack pointer up to accomodatethe new item. pop:reading a value from stack or moving the stack pointer down.
stack is the basic data structure needed to convert infix notation to postfix
stack
Stack is a data structure which is closed at one end. last in first outhi
LIFO stands for Last In First Out. Ex: Stack
Stack is an abstract data type that allows you to input and output data in a way that the first data which was placed in the stack will be the last one to get out. We use physical examples of stack in our daily lives such as the stack of dishes or stack of coins where you only add or remove objects from the top of the stack. You can see the implementation in c++ in related links, below.
No. A stack is a data structure that allows insertion and removal at the top. A circular list allows insertion and removal anywhere in the list. The two types of data structure are too different to be reasonably implementable in terms of each other.