Stack

Stack is one of the elementary data structure in which elements are added and deleted using Last-In-First-Out (LIFO) principle. To understand LIFO principle, let us consider a teacher is checking the examination paper. After checking each paper, he/she keeps the papers by his/her side such that the first paper checked, remained at the bottom and the last paper checked, remained at the top. So, the paper is inserted at the top of the pile of paper. While distributing the examination paper, the first paper to be removed, is the one which was on the top of the pile. This is known as LIFO principle.

Loading
(a) Stack S has 4 elements and its top element is 9. (b) Stack S after STACK_PUSH(S, 17) and STACK_PUSH(S, 3). (c) Stack S after STACK_POP(S). [Source: Introduction to Algorithms]

Here, we will see the implementation of stack using an array. Let, S[1…n] be the array. The stack has an attribute, S.top which gives index of the most recently added element. The stack is empty if S.top = 0. The insert and delete operation in the stack has special names, push and pop respectively. If we try to push an element in the stack containing n elements, an error occurs which is known as stack overflow. Similarly, if we try to pop an empty stack, stack underflow occurs. Now, let’s see the operations in the stack.

STACK_EMPTY(S)

if S.top == 0
    return True
else
    return False

STACK_PUSH(S, x)

if S.top == n
    Error “Stack Overflow”
else
    S.top = S.top + 1
    S[S.top] = x

STACK_POP(S)

if STACK_EMPTY(S)
    Error “Stack Underflow”
else
    S.top = S.top – 1
    return S[S.top + 1]

If we analyze the running time of each operation, we can see that each of the operations take O(1) time. O(1) time simply means that the time required is constant and it does not change even if the size of the array is made large. Every modern programming languages have the library facility to implement stack. For example, in C++, you can use Standard Template Library (STL) to implement stack. Now, let’s consider a simple operation in which we can use stack. Suppose we have to take the input from the user and print it in reverse form. Then, we can use stack to store the input then, pop the value from the stack. Algorithm to print the input from the user in reverse form

while (input != newline)
    Store input in variable x
    STACK_PUSH (S, x)
while(!STACK_EMPTY)  
    x = STACK_POP (S)             //pops value from the stack and store it in variable x
    Output x

In the above algorithm, if the input is in the sequence 1 2 3 4 5 then, the output will be 5 4 3 2 1.

Reference book:
Introduction to Algorithms by CLRS

Comments

Post a Comment

Popular posts from this blog

Binary Search

Image
Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i]. At first, let’s see how do we locate an element in an array using linear or sequential approach. LINEAR-SEARCH (T[1…n], x) for i = 1 to n if T[i] > x return i return n + 1 From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of...
Read more

System Bus

Image
Have you ever wondered how the microprocessor communicates with the devices connected to it? Well, there are a group of wires (communication path) between microprocessor and its peripherals (and memory) to carry bits which are known as system bus. The system bus performs the following steps to communicate with the peripheral: i.         Identify the peripheral or the memory location (with its address). ii.       Transfer data and instructions in the form of bits. iii.     Provide timing and synchronization signals. According to the above functions, system bus can be classified into three types which are described below: Address Bus: It is a set of wires that is used to transmit address from the microprocessor to its peripheral devices (or memory. It is unidirectional. Each peripheral or memory is identified by its address. This is similar to the postal address of the house. For example...
Read more

Differences between hardwired and micro-programmed control unit

S.N. Hardwired Control Unit Micro-programmed Control Unit 1. It is implemented through the use of sequential logic circuit. Its input logic signals are transformed into a set of output logic signals which are control signals. It is implemented through the use of micro-programs. Micro-programs (control information) are organized as a sequence of micro-instructions stored in a special control memory. 2. This design uses a fixed architecture so, it require changes in wiring if the instruction set is modified. It is easy to reconfigure and modify instruction set. 3. It is difficult to build a circuit that satisfies all the operations. It is simple in structure. 4. It has faster mode of operation. It is comparatively slower. 5. It is comparatively expensive. It is cheaper. 6. It is preferred for less number of instruction sets. I...
Read more