Stacks
Definition:-
A Stack is an ordered collection of items which are arranged
in the Last In First Out manner(LIFO).
Allows access to only the last item inserted.
An item is inserted or removed from the stack from one end
called the “top” of the stack.
This mechanism is called Last-In-First-Out (LIFO).
Placing a data item on the top is called “pushing”, while removing an item from the top is called “popping” it. push and pop are the primary stack operations. Some of the applications are : microprocessors, some older calculators etc.
Primitive operations on a Stack 1) Create:- This operation creates a new stack, which is empty. 2) Push:- Adds an element to the stack. The push operation inserts a new element at the top of the stack. Top points the the new element. 3) Pop:- Removes the topmost element from the stack. The next element now becomes the topmost element. 4) IsEmpty:- checks whether a stack is empty. This operation returns TRUE if the stack is empty and false otherwise. This is required for the pop operation because we cannot pop from an empty stack. Popping from an empty stack causes an Underflow.
) IsEmpty:- checks whether a stack is empty. This operation returns TRUE if the stack is empty and false otherwise. This is required for the pop operation because we cannot pop from an empty stack. Popping from an empty stack causes an Underflow. 5)IsFull:- Checks whether a stack is full. This operation returns TRUE if the stack is full and false otherwise. This is required for the Push operation because we cannot push into a full stack. Pushing into a full stack causes an Overflow
Stack presentation A stack can be represented or implemented in two ways:
1) Static implementation using array. A stack implemented using an array will require: 1) An array to store stack elements 2) An integer called top which stores the index or position of the topmost element. Limitations of static implementation Since array is a static data structure, the size has to be declared at the beginning. The size remains fixed. Even if the stack is empty, memory remains allocated.
2) Dynamic implementation using linked list. To overcome the problems of static representation, the stack can be implemented using dynamic representation. In this method, we use dynamic memory allocation so that memory can be allocated only when an element is pushed and released when an element is popped. In this case, the elements will not occupy consecutive memory locations. Hence, the elements must be linked to one another. This is a linked structure.
Operations on Dynamic Implementation of stack 1) Create:-Since only the topmost element can be accessed, the first node in the list can be accessed by a pointer called top. Initially, the stack is empty, hence top is initialized to NULL. 2) Push:- To push an element in the stack, we must create a new node. The new node is inserted at the beginning of the list and top will point to this node. 3) Pop:- for pop , the element from the first node is popped and its next node becomes topmost node of the stack. 4) Isempty:- If top contains NULL, it indicates that there are no nodes and the stack is empty. 5) IsFull:- Since we are using dynamic memory allocation, the stack can grow to any size. Thus this condition does nott have to be checked.
Applications Of stack 1) Handling function calls, Recursion. 2) Interrupt handling in processors. 3) Expression conversion and evaluation(Infix, Postfix, and prefix expression) 4) Non recursive traversal of tree and graph 5) Checking whether parentheses are matching in an expression. 6) Backtracking algorithm. 7) Games.
In the linked organization of stack 1) The stack can grow to any size. 2) we need not have prior knowledge of the number of elements. 3) when an element is popped, the memory can be freed.Thus memory is not unnecessarily occupied.
Queues Queue is an ADT data structure similar to stack, except that the first item to be inserted is the first one to be removed. This mechanism is called First-In-First-Out (FIFO). Placing an item in a queue is called “insertion or enqueue”, which is done at the end of the queue called “rear”. Removing an item from a queue is called “deletion or dequeue”, which is done at the other end of the queue called “front”. Some of the applications are : printer queue, keystroke queue, etc.
Circular Queue When a new item is inserted at the rear, the pointer to rear moves upwards. Similarly, when an item is deleted from the queue the front arrow moves downwards. After a few insert and delete operations the rear might reach the end of the queue and no more items can be inserted although the items from the front of the queue have been deleted and there is space in the queue.To solve this problem, queues implement wrapping around. Such queues are called Circular Queues. Both the front and the rear pointers wrap around to the beginning of the array. It is also called as “Ring buffer”. Items can inserted and deleted from a queue in O(1) time.
Queue Types Normal queue (FIFO) Circular Queue (Normal Queue) Double-ended Queue (Deque) Priority Queue Deque It is a double-ended queue. Items can be inserted and deleted from either ends. More versatile data structure than stack or queue. E.g. policy-based application (e.g. low priority go to the end, high go to the front).
Priority Queues More specialized data structure. Similar to Queue, having front and rear. Items are removed from the front. Items are ordered by key value so that the item with the lowest key (or highest) is always at the front. Items are inserted in proper position to maintain the order.
Infix to postfix Read ch from input until empty If ch is arg , output = output + arg If ch is “(“, push ‘(‘; If ch is op and higher than top push ch If ch is “)” or end of input, output = output + pop() until empty or top is “(“ Read next input
Postfix evaluation 5 + 2 * 3 -> 5 2 3 * + Algorithm While input is not empty If ch is number , push (ch) Else Pop (a) Pop(b) Eval (ch, a, b)
Placing a data item on the top is called “pushing”, while removing an item from the top is called “popping” it. push and pop are the primary stack operations. Some of the applications are : microprocessors, some older calculators etc.
 |
| Stacks and Queues in C |
Primitive operations on a Stack 1) Create:- This operation creates a new stack, which is empty. 2) Push:- Adds an element to the stack. The push operation inserts a new element at the top of the stack. Top points the the new element. 3) Pop:- Removes the topmost element from the stack. The next element now becomes the topmost element. 4) IsEmpty:- checks whether a stack is empty. This operation returns TRUE if the stack is empty and false otherwise. This is required for the pop operation because we cannot pop from an empty stack. Popping from an empty stack causes an Underflow.
) IsEmpty:- checks whether a stack is empty. This operation returns TRUE if the stack is empty and false otherwise. This is required for the pop operation because we cannot pop from an empty stack. Popping from an empty stack causes an Underflow. 5)IsFull:- Checks whether a stack is full. This operation returns TRUE if the stack is full and false otherwise. This is required for the Push operation because we cannot push into a full stack. Pushing into a full stack causes an Overflow
Stack presentation A stack can be represented or implemented in two ways:
1) Static implementation using array. A stack implemented using an array will require: 1) An array to store stack elements 2) An integer called top which stores the index or position of the topmost element. Limitations of static implementation Since array is a static data structure, the size has to be declared at the beginning. The size remains fixed. Even if the stack is empty, memory remains allocated.
2) Dynamic implementation using linked list. To overcome the problems of static representation, the stack can be implemented using dynamic representation. In this method, we use dynamic memory allocation so that memory can be allocated only when an element is pushed and released when an element is popped. In this case, the elements will not occupy consecutive memory locations. Hence, the elements must be linked to one another. This is a linked structure.
Operations on Dynamic Implementation of stack 1) Create:-Since only the topmost element can be accessed, the first node in the list can be accessed by a pointer called top. Initially, the stack is empty, hence top is initialized to NULL. 2) Push:- To push an element in the stack, we must create a new node. The new node is inserted at the beginning of the list and top will point to this node. 3) Pop:- for pop , the element from the first node is popped and its next node becomes topmost node of the stack. 4) Isempty:- If top contains NULL, it indicates that there are no nodes and the stack is empty. 5) IsFull:- Since we are using dynamic memory allocation, the stack can grow to any size. Thus this condition does nott have to be checked.
Applications Of stack 1) Handling function calls, Recursion. 2) Interrupt handling in processors. 3) Expression conversion and evaluation(Infix, Postfix, and prefix expression) 4) Non recursive traversal of tree and graph 5) Checking whether parentheses are matching in an expression. 6) Backtracking algorithm. 7) Games.
In the linked organization of stack 1) The stack can grow to any size. 2) we need not have prior knowledge of the number of elements. 3) when an element is popped, the memory can be freed.Thus memory is not unnecessarily occupied.
Queues Queue is an ADT data structure similar to stack, except that the first item to be inserted is the first one to be removed. This mechanism is called First-In-First-Out (FIFO). Placing an item in a queue is called “insertion or enqueue”, which is done at the end of the queue called “rear”. Removing an item from a queue is called “deletion or dequeue”, which is done at the other end of the queue called “front”. Some of the applications are : printer queue, keystroke queue, etc.
Circular Queue When a new item is inserted at the rear, the pointer to rear moves upwards. Similarly, when an item is deleted from the queue the front arrow moves downwards. After a few insert and delete operations the rear might reach the end of the queue and no more items can be inserted although the items from the front of the queue have been deleted and there is space in the queue.To solve this problem, queues implement wrapping around. Such queues are called Circular Queues. Both the front and the rear pointers wrap around to the beginning of the array. It is also called as “Ring buffer”. Items can inserted and deleted from a queue in O(1) time.
Queue Types Normal queue (FIFO) Circular Queue (Normal Queue) Double-ended Queue (Deque) Priority Queue Deque It is a double-ended queue. Items can be inserted and deleted from either ends. More versatile data structure than stack or queue. E.g. policy-based application (e.g. low priority go to the end, high go to the front).
Priority Queues More specialized data structure. Similar to Queue, having front and rear. Items are removed from the front. Items are ordered by key value so that the item with the lowest key (or highest) is always at the front. Items are inserted in proper position to maintain the order.
Infix to postfix Read ch from input until empty If ch is arg , output = output + arg If ch is “(“, push ‘(‘; If ch is op and higher than top push ch If ch is “)” or end of input, output = output + pop() until empty or top is “(“ Read next input
Postfix evaluation 5 + 2 * 3 -> 5 2 3 * + Algorithm While input is not empty If ch is number , push (ch) Else Pop (a) Pop(b) Eval (ch, a, b)