Software Developer
Stacks, queues, deques, and lists are statistics collections with items ordered in line with how they are added or removed. Once an item is added, it stays inside the equal function relative to its buddies. Because of this function, we name these collections linear data systems.
Linear structures may be the concept of as having ended, stated variously as “left” and “right”, “pinnacle” and “bottom”, or “front” and “rear”. What distinguishes one linear structure from any other is where additions and removals may additionally arise. As an example, a shape may only allow new objects to be added at one end and eliminated at some other; every other may also permit the addition or elimination from either cease.
Those variations give an upward push to some of the maximum beneficial records systems in pc technology. They appear in many algorithms and can be used to remedy a diffusion of essential troubles.
Data structure where data elements are arranged sequentially or linearly is called a linear data structure. In a linear data structure, we can traverse all the data items in a single pass. Until now, all the data structures you have learned are linear only, whether it is Array, ArrayList, or String. Stack is also a linear data structure.
FILO (First In Last Out) or LIFO (Last In First Out) order:-
Let us try to get the meaning of FILO or LIFO using an example. Consider a pile of 3 books on a table.
If you want to take out the top blue book, then you need not do anything to the pile. Just pick it from the top.
But if you want to take out the bottom pink book, then first you need to remove the books on top (blue and yellow), and then only you can get access to the third (bottom-most) book.
Also, if you want to add a book, let's say, green in color, then you can add it above the blue book only. Otherwise, you will have to disturb the remaining 3 books' ordering.
An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the data and the allowed operations without regard to how they’ll be implemented. This means that we’re only concerned with what the data represents and not with how it’ll be constructed. This level of abstraction encapsulates the data and hides implementation details from the user's view, a technique called information hiding.
A data structure is an implementation of an abstract data type and requires a physical view of the data using some collection of primitive data types and other programming constructs.
The separation of these two perspectives allows us to define complex data models for our problems without giving any details about how the model will actually be built. This provides an implementation-independent view of the data. Since there are usually many ways to implement an abstract data type, this independence allows the programmer to change implementation details without changing how the user interacts with it. Instead, the user can remain focused on the process of problem-solving.
The stack abstract data type is an ordered collection of items where items are added to and removed from the top. The interface for a stack is:
For example, if s is a newly-created, empty stack, then the table below shows the results of a sequence of stack operations. The top item is the one farthest to the right in “Stack contents”.
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations −
When data is PUSHed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks −
At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.
First we should learn about procedures to support stack functions −
peek()
Algorithm of peek() function −
begin procedure peek
return stack[top]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return stack[top];
}
isfull()
Algorithm of isfull() function −
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
Implementation of isempty() function in C programming language is slightly different. We initialize top at -1, as the index in array starts from 0. So we check if the top is below zero or -1 to determine if the stack is empty. Here's the code −
Example
bool isempty() {
if(top == -1)
return true;
else
return false;
}
Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
Implementation of this algorithm in C, is very easy. See the following code −
Example
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
Algorithm for Pop Operation
A simple algorithm for Pop operation can be derived as follows −
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Implementation of this algorithm in C, is as follows −
Example
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}