DataStructures Series — 5
N.B. This article would make more sense if you read previous articles in this series.
In case you missed last week on the data-structures series here.
We discussed the array ADT and looked at Java’s implementation of the array ADT and how to use it. We also discussed the best time to use arrays: you could save and retrieve values in constant time if you know the index in the array you want to insert and fetch respectively.
This week we would be discussing the Stack ADT.
The Stack ADT
The stack ADT allows operations only at one end, adding or removing elements is usually performed at a single position which is known as the top.
That means new elements are added to the top of a stack and an element is removed from the top of the stack. In a stack, the insertion and deletion operation are performed based on the LIFO (last in, first out) principle.
Stack Operations:
- Push Element
- Pop Element
- Peek Element
Push Element — This would insert an element into the stack.
Pop Element — This would remove the element on top of the stack.
Peek Element — This would fetch and not remove the element on top of the stack
Implementation
One way to implement the stack data structure is to use an array.
Below is a pseudocode implementation:
- new array {size}- currentIndex = 0;- insert(element): set array[currentIndex] = element,
currentIndex++;- pop(): value = array[currentIndex - 1],
set array[currentIndex - 1] = null, currentIndex--,
return value;- peek(): if (currentIndex == 0), return null
otherwise: return array[currentIndex - 1];
This implementation is pretty straight forward but would give problems when the array size is full, that would mean we need to create another array with a bigger size and then transfer all data from the previous one to the new one. This could be very expensive depending on the size of the data in question, hence, it is not advisable to use an array for the stack ADT implementation, we would discuss other alternatives as we proceed in this series.
Applications
- Browser tab history management — while displaying a webpage on a tab, the browser pushes the current address into a stack, clicking the back button pops this address and uses the next address in the stack.
- Undo/Redo in text editors — we could have a stack each for undo and redo, the undo stack would add snapshot elements for each action performed in the editor, the undo action would pop the element at the top and insert in the redo stack.
Next week we would be discussing another interesting abstract data type, the Queue ADT.
REFERENCES:
