Circular Doubly List

Skip list in DS

DS Stack

DS Stack

← prev next →

Stack Organisation
Understanding Stack
A stack stores data using the LIFO principle. The last item added is the first one to
be removed, like a pile of plates.
Implementing a stack can be achieved using various programming constructs
Stack Implementation and data structures.
A stack is a memory structure in a computer that updates its pointer (SP) when
elements are added or removed. The stack can grow upwards or downwards in 1. Array-based Stack implementation:
memory. In an upward-growing stack, the stack pointer is incremented when an A stack data structure is a collection that conveniently stores a group of elements,
element is pushed and decremented when it's popped. In a downward-growing allowing for easy addition and removal from the end of the array. Despite its user-
stack, the stack pointer is decremented when an element is pushed and friendly design, the size of the stack is predetermined, resulting in a limited
incremented when it's popped. capacity for element additions. Adding new elements to the stack might result in
stack overflow consequent to program crashes and unexpected behaviour.

Advantages:

Simple implementation.

Efficient memory usage when the maximum size is known.

Disadvantages:

Fixed size, which can lead to overflow or underflow.

Inefficient resizing if the array becomes full.

2. Linked List-based Stack implementation:
A stack is a vital data structure in computer science that efficiently manages
memory and resizes data. It uses a linked list to represent each element as a node
and stores elements in a specific order. When a new element is added, it becomes
the top of the stack. Similarly, when an element needs to be removed, the top
node is taken off. The stack is an essential tool for programmers looking to
optimize their code.

Advantages:

Dynamic size: memory usage grows as needed.

No fixed capacity limitations.

Disadvantages:

Slightly more complex implementation compared to array-based.

Slightly more memory overhead due to node references. In computer science, a stack is an abstract data type that serves as a collection of
elements with two principal operations:
Stack Operations:
Push: This operation adds an element to the collection. It places a new
item on the top of the stack.

Pop: This operation removes the most recently added element that was
not yet removed. It removes an element from the top position.

The stack follows the Last-In-First-Out (LIFO) concept, meaning the element
inserted last comes out first. It only has one pointer, the top pointer, which points
to the stack's topmost member.

Some additional operations can be performed on a stack:

Top/Peek: Returns the top element of the stack.

isEmpty: Returns true if the stack is empty, else false.

Size: Returns the size of the stack.

Stack Organisation classification

There are two main types of stack organisation in computer architecture: register
stack and memory stack.

Register Stack
A register stack is a stack of memory words or registers placed on top of each
other. A binary number, the address of the element at the top of the pile, is stored
in the stack pointer register. The top element is removed from the stack by
reading the memory word at the address held by the stack pointer and decreasing
the stack pointer by one. A new comment can be added by increasing the stack
pointer and inserting a word in the newly expanded location.

The advantages of stack organisation are:

Efficient computation of complex arithmetic expressions, as the

operands are automatically arranged in the correct order of evaluation.

Fast execution of instructions, as the operand data are stored in

consecutive memory locations and accessed by a single register.

Short and straightforward instructions, as they do not have address

fields and only contain the opcode.

The disadvantages of stack organisation are:

Memory Stack Limited parallelism, as the instructions can only operate on the top
elements of the stack and not on other data in the system.
Create a memory stack in attached RAM by assigning a portion of memory and
keeping its pointer in a processor register for a stack operation. The starting Increased memory access, as the stack operations require frequent read
memory location of the stack is specified by the processor register as the stack and write operations to the memory.
pointer. The stack pointer first points at a specific address, and then the stack Reduced flexibility, as the stack operations are fixed and cannot be
grows with decreasing addresses. The data inserted into the stack is obtained modified or optimised for different situations.
from the Data Register, which reads the data retrieved from the stack.