A stack is an Abstract Data Type (ADT) that is found in almost all computer languages. It is called a stack because it performs like real-world stacking, such as a deck of cards or perhaps a pile of dishes.
A real-world stack can only perform operations at one end. For instance, we can only place or take a card or plate from the top of the stack. Similarly, Stack ADT permits all data operations at only one end. We can only access the top element of a stack at any given time.
Because of this feature, it has a LIFO data structure. LIFO is an abbreviation for Last-in-First-Out. The piece that was placed (inserted or added) last is accessed first in this case. In stack terminology, an insertion operation is referred to as a PUSH operation, whereas a removal activity is referred to as a POP operation.
Stack Representation
Array, Structure, Pointer, and Linked List can all be used to implement a stack. Stacks can be either fixed in size or dynamically resized.
Basic Operations
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 −
- push() − Pushing (storing) an element on the stack.
- pop() − Removing (accessing) an element from the stack.
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 −
- peek() − get the top data element of the stack, without removing it.
- isFull() − check if stack is full.
- isEmpty() − check if stack is empty.
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 the top value of the stack without actually removing it.
peek()
Algorithm of peek() function −
begin procedure peek return stack[top] end procedure
isfull()
Algorithm of isfull() function −
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
isempty()
Algorithm of isempty() function −
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
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 −
- Step 1 − Checks if the stack is full.
- Step 2 − If the stack is full, produces an error and exit.
- Step 3 − If the stack is not full, increments top to point next empty space.
- Step 4 − Adds data element to the stack location, where top is pointing.
- Step 5 − Returns success.
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
Pop Operation
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 elements and deallocates memory space.
A Pop operation may involve the following steps −
- Step 1 − Checks if the stack is empty.
- Step 2 − If the stack is empty, produces an error and exit.
- Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
- Step 4 − Decreases the value of top by 1.
- Step 5 − Returns success.
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
