Page 129 - DCAP407_DATA_STRUCTURE

Data Structure

7.3 Representing Stacks in Memory

Stacks are represented in main memory by using one-dimensional arrays or by using a singly linked
list.
Array Representation of Stacks
First, a memory block of sufficient size is allocated to accommodate the full capacity of the stack. The
items of the stack are stored in a sequential manner.

Using C language, stack is declared as an array of variable
int stack[Max_STACK_SIZE];
or
char stack[Max_STACK_SIZE];
where Max_STACK_SIZE is the maximum number of elements that can be inserted in a stack.
Max_STACK_SIZE should be defined by an appropriate value.

In C language, we can define constants using #define statement. The stack size
with a capacity of storing 6 elements can be defined as
#define MAX_STACK_SIZE 6
Linked List Representation of Stacks

The array representation of stacks is easy and convenient. However, it allows the representation of only
fixed sized stacks. The size of the stack varies during program application for different applications.
Representing stack using linked list can solve this problem. A singly linked list can be used to represent
any stack. In a singly linked list, the data field represents the ITEM and the LINK field points to the
next item. Figure 7.4 shows the linked representation of the stack.

Figure 7.4: Linked List Representation
of a Stack

In figure 7.4, the INFO field of the nodes holds the elements of the stack. The LINK field holds pointers
to the next element in the stack. The START pointer of the linked list is the Top pointer variable of
stack.
7.4 Stack Implementation using Arrays
A stack is a sequence of data elements. To implement a stack structure, an array can be used as it is a
storage structure. Each element of the stack occupies one array element. Static implementation of stack
can be achieved using arrays. The size of the array, once declared, cannot be changed during the
program execution. Memory is allocated according to the array size. The memory requirement is
determined before the compilation. The compiler provides the required memory. This is suitable when
the exact number of elements is known. The static allocation is an inefficient memory allocation
technique because if fewer elements are stored than declared, the memory is wasted and if more
elements need to be stored than declared, the array cannot expand. In both the cases, there is inefficient
use of memory.

122 LOVELY PROFESSIONAL UNIVERSITY